Equivalence of Definitions of Semantic Equivalence for Predicate Logic

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathbf A, \mathbf B$ be WFFs of predicate logic.


The following definitions of the concept of Semantic Equivalence (Predicate Logic) are equivalent:

Definition 1

Then $\mathbf A$ and $\mathbf B$ are equivalent if and only if:

$\mathbf A \models_{\mathrm{PL_A}} \mathbf B$ and $\mathbf B \models_{\mathrm{PL_A}} \mathbf A$

that is, each is a semantic consequence of the other.


That is to say, $\mathbf A$ and $\mathbf B$ are equivalent if and only if, for all structures $\mathcal A$ and assignments $\sigma$:

$\mathcal A, \sigma \models_{\mathrm{PL_A}} \mathbf A$ iff $\mathcal A, \sigma \models_{\mathrm{PL_A}} \mathbf B$

where $\models_{\mathrm{PL_A}}$ denotes the models relation.


Definition 2

Then $\mathbf A$ and $\mathbf B$ are equivalent if and only if:

$\mathbf A \iff \mathbf B$ is a tautology

where $\iff$ is the biconditional connective.


Proof

Let $\mathcal A$ be a structure for predicate logic.

Let $\sigma$ be an assignment for $\mathbf A \iff \mathbf B$ in $\mathcal A$.


Then the value of $\mathbf A \iff \mathbf B$ under $\sigma$ is given by:

$f^\leftrightarrow \left({ \mathop{ \operatorname{val}_{\mathcal A} \left({\mathbf A}\right) } \left[{\sigma}\right], \mathop{ \operatorname{val}_{\mathcal A} \left({\mathbf B}\right) } \left[{\sigma}\right] }\right)$

and from the definition of $f^\leftrightarrow$ we see that $\mathcal A, \sigma \models_{\mathrm{PL_A}} \mathbf A \iff \mathbf B$ iff:

$\mathop{ \operatorname{val}_{\mathcal A} \left({\mathbf A}\right) } \left[{\sigma}\right] = \mathop{ \operatorname{val}_{\mathcal A} \left({\mathbf B}\right) } \left[{\sigma}\right]$

Because the possible values are just $T$ and $F$, this is equivalent to:

$\mathop{ \operatorname{val}_{\mathcal A} \left({\mathbf A}\right) } \left[{\sigma}\right] = T$ iff $\mathop{ \operatorname{val}_{\mathcal A} \left({\mathbf B}\right) } \left[{\sigma}\right] = T$

which by definition of $\mathrm{PL_A}$-model amounts to:

$\mathcal A, \sigma \models_{\mathrm{PL_A}} \mathbf A$ iff $\mathcal A, \sigma \models_{\mathrm{PL_A}} \mathbf B$


Because $\mathcal A$ and $\sigma$ were arbitrary, the above equivalence holds for all such $\mathcal A$ and $\sigma$.

The result follows by definition of tautology.

$\blacksquare$