Definition:Semantic Equivalence

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\mathscr M$ be a formal semantics for a formal language $\mathcal L$.

Let $\phi, \psi$ be $\mathcal L$-WFFs.


Then $\phi$ and $\psi$ are $\mathscr M$-semantically equivalent if and only if:

$\phi \models_{\mathscr M} \psi$ and $\psi \models_{\mathscr M} \phi$

that is, iff they are $\mathscr M$-semantic consequences of one another.


Equivalently, $\phi$ and $\psi$ are $\mathscr M$-semantically equivalent if and only if, for each $\mathscr M$-structure $\mathcal M$:

$\mathcal M \models_{\mathscr M} \phi$ iff $\mathcal M \models_{\mathscr M} \psi$


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


Definition 1

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

$\mathbf A \models_{\mathrm{BI}} \mathbf B$ and $\mathbf B \models_{\mathrm{BI}} \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:

$v \left({\mathbf A}\right) = T$ if and only if $v \left({\mathbf B}\right) = T$

for all boolean interpretations $v$.


Definition 2

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

$\map v {\mathbf A} = \map v {\mathbf B}$

for all boolean interpretations $v$.


Definition 3

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

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

where $\iff$ is the biconditional connective.

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


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.


Also see