Are these two characterizations of two (sets of) formulas being equivalent?

47 Views Asked by At

In the first order logic system, on p121 of Ebbinghaus' Mathematical Logic

We call two sets $\Phi$ and $\Psi$ of $S$-sentences equivalent if $Mod^S\Phi = Mod^S\Psi$. Then, in particular, $\Phi \models \phi$ iff $\Phi \models \phi$ for all $\phi \in L^S$.

  1. Are $\Phi$ and $\Psi$ equivalent , if and only if $\Phi \models \phi$ iff $\Psi \models \phi$ for all $\phi \in L^S$? (The last sentence in the quote says only "only if".)

  2. Are two $S$-sentences $\phi$ and $\psi$ equivalent, if and only if $\models (\phi \leftrightarrow \psi)$? (This is used as the definition of logical equivalence between two formulas in propositional logic, on p202.)

Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER
  1. Yes. Let $\mathscr M \in Mod^S\Phi$. Since $\Psi \models \psi$ for all $\psi \in \Psi$, we have that $\Phi \models \psi$ for all $\psi\in \Psi$, and hence $\Phi \models \Psi$. Therefore, since $\mathscr M \models \Phi$, it follows that $\mathscr M \models \Psi$, so $\mathscr M \in Mod^S\Psi$ and thus $Mod^S \Phi \subseteq Mod^S\Psi$. The other direction is similar.
  2. Yes again. Note that $\models \phi \leftrightarrow \psi$ means that for any $S$-structure $\mathscr M$ we have that $\mathscr M \models \phi \leftrightarrow \psi$, i.e. for any $S$-structure $\mathscr M$, $\mathscr M \models \phi$ if and only if $\mathscr M \models \psi$. Therefore $\models \phi \leftrightarrow \psi$ is equivalent to the statement that the models of $\phi$ are exactly the same as the models of $\psi$, which is precisely the definition of $Mod^S \phi = Mod^S\psi$.