Mutual Entailment

logic

Definition

Mutual Entailment

Two formulas mutually entail each other (are equivalent) if they have the same truth value under every interpretation.

$$A\equiv B:⟺A\models B\wedge B\models A$$

Hence, there is no interpretation that makes one of them true and the other false, so we cannot distinguish them semantically. Semantic equivalence is an equivalence relation on formulas.

Proof

Mutual Entailment

Let $v$ be an arbitrary interpretation. Assume that $v(A)=\top$. Then:

$$A\vee B=\top$$

Since $A\vee B\models A\wedge B$, it follows that:

$$v(A\wedge B)=\top$$

Hence $v(B)=\top$, so $A\models B$.

Symmetrically, we can assume that $v(B)=\top$, then:

$$v(A\vee B)=\top$$

Since $A\vee B\models A\wedge B$, it follows that:

$$v(A\wedge B)=\top$$

Hence $v(A)=\top$, so $B\models A$.

We have $A\models B$ and $B\models A$. Hence, there is no interpretation that makes one of them true and the other false, so we cannot distinguish them semantically. Therefore:

$$v(A)=v(P)\text{ for all }v$$

which means:

$$A\equiv B$$

Equivalent Replacement

Definition

Equivalent Replacement

Let $A[B]$ denote a formula $A$ with one fixed occurrence of a subformula $B$, identified by a position in $A$, and let $A[B\to B^{\prime }]$ be the formula obtained by replacing that occurrence with $B^{\prime }$.

For every interpretation $I$,

$$I\models B_1\leftrightarrow B_2⟹I\models A[B_1]\leftrightarrow A[B_2].$$

Two subformulas with the same truth value under $I$ are interchangeable at a fixed occurrence: replacing one by the other leaves the truth value of the whole formula unchanged under $I$.

Link to original