Understanding Equivalence of Sentences

[Andrei1]

I want to understand the notion of equivalence. \(\displaystyle \varphi\equiv\psi\) means that for all structure \(\displaystyle M\), \(\displaystyle M\models\varphi\) iff \(\displaystyle M\models\psi.\)
Suppose that for some structure \(\displaystyle M\) and formula \(\displaystyle \varphi\), \(\displaystyle M\models\varphi(\bar{a})\), where \(\displaystyle \bar{a}\) are all constants in \(\displaystyle \varphi.\)
What I can say then by the above definition? That \(\displaystyle M\models\psi(\bar{b})\) or \(\displaystyle M\models\psi(\bar{a})\) or \(\displaystyle M\models\psi\)?

 

[Andrei1]

I didn't formulate exactly my question. I just need to read somewhere the proof of the theorem that literal embeddings preserve quantifier-free formulas. What good sources do you know, excepting Hedman's book?

 

[Evgeny.Makarov]

I just need to read somewhere the proof of the theorem that literal embeddings preserve quantifier-free formulas. What good sources do you know, excepting Hedman's book?

This fact is quite simple and is probably not worth the effort of going to another book with its own definitions. Unfortunately, in logic there are many technical differences between textbooks even though what they say is largely equivalent.

The fact is that quantifier-free formulas are Boolean combinations of literals, and since literals are preserved by embeddings, so are quantifier-free formulas. Formally this is proved by induction on formulas. I'll consider the case of conjunction in Hedman's notation. Suppose that $\varphi(\bar{x})$ is $\psi(\bar{x})\land\theta(\bar{x})$. By induction hypothesis, $\psi(\bar{x})$ and $\theta(\bar{x})$ are preserved by $f:M\to N$, i.e.,
\begin{align}
M\models\psi(\bar{a})&\implies N\models\psi(f(\bar{a}))\\
M\models\theta(\bar{a})&\implies N\models\theta(f(\bar{a}))
\end{align}
for all tuples $\bar{a}$ from the universe of $M$. Now suppose that $M\models\varphi(\bar{a})$, i.e., $M\models\psi(\bar{a})$ and $M\models\theta(\bar{a})$. Then the implications above say that $N\models\psi(f(\bar{a}))$ and $N\models\theta(f(\bar{a}))$, i.e., $N\models\varphi(f(\bar{a}))$. This is nothing more than propositional reasoning.

The books also proves that existential formulas are preserved. Why are universal formulas not necessarily preserved? Because $N$ may have more elements than $f(M)$. If a formula is true for all elements in $M$, then in general it is true only for some subset of $N$. For example, $\forall x\;x^2\ne2$ is true in $\Bbb Q$, but not in $\Bbb R$. Here we are considering the identity function from $\Bbb Q$ to $\Bbb R$, which is a (literal) embedding.

 

[Andrei1]

In his book Hedman uses a shorter form of induction. For that he shows the property of the formula is preserved under equivalence: if the embedding preserves \(\displaystyle \psi\) and \(\displaystyle \varphi\equiv\psi\), then the embedding preserves \(\displaystyle \varphi.\) How to prove this?

Since \(\displaystyle \varphi\) and \(\displaystyle \psi\) are formulas, I use this definition of equivalence: for any structure \(\displaystyle M\), \(\displaystyle M\models\forall\bar{x}\varphi(\bar{x})\) iff \(\displaystyle M\models\forall\bar{x}\psi(\bar{x})\). It leads to nowhere.

 

[Evgeny.Makarov]

Since \(\displaystyle \varphi\) and \(\displaystyle \psi\) are formulas, I use this definition of equivalence: for any structure \(\displaystyle M\), \(\displaystyle M\models\forall\bar{x}\varphi(\bar{x})\) iff \(\displaystyle M\models\forall\bar{x}\psi(\bar{x})\). It leads to nowhere.

I have to agree: Hedman's treatment is not good here. Let's first talk about proving formula properties by induction. There are two options: either $\lor$, $\to$ and $\leftrightarrow$ are abbreviations and exist only on the metalevel, not in the concrete syntax, or they are primitive connectives, which occur in the definition of formulas. In the first case, there is no need to say that every propositional formula is equivalent to one built from $\land$ and $\neg$ because every formula is built from those two connectives; everything else is just our way of writing formulas. Then induction needs only two induction steps. In the second case, the number of induction steps equals the number of primitive connectives, but again there is no need to consider $\equiv$. In fact, I've never seen formula equivalence treated as a part of an induction step.

So the simplest fix of the proof about preservation of quantifier-free formulas by embeddings is to treat all propositional connectives as primitive and to consider all of them in the induction step.

In the following I write $\forall\varphi$ and $\exists\varphi$ for universal and existential closures of $\varphi$. The author gives the following definitions regarding formulas with free variables:

(1) $M\models\varphi$ if $M\models\forall\varphi$,
(2) $\varphi$ is satisfiable if $\forall\varphi$ is, and
(3) $\models\varphi$ if $\models\exists\varphi$ (actually, this is deduced in Exercise 2.6).

He does not explicitly define $\varphi\models\psi$ and $\varphi\equiv\psi$, though he says that these concepts apply to formulas and not only to sentences.

I think these definitions are unfortunate. For one, we lose the equivalence $\models\varphi\iff M\models\varphi$ for all $M$. Indeed, the right-hand side means $M\models\forall\varphi$ for all $M$ using (1), i.e., $\models\forall\varphi$ and not $\models\exists\varphi$, as in (3). Next, if we keep the propositional definition of $\varphi\models\psi$:
\[
(4)\qquad M\models\varphi\implies M\models\psi\text{ for all }M,
\]
then (1) implies that
\[
(5)\qquad\varphi\models\psi\iff \forall\varphi\models\forall\psi\iff {\models(\forall \varphi)\to(\forall\psi)}.
\]
Correspondingly, $\varphi\equiv\psi$ would mean $(\forall\varphi)\equiv(\forall\psi)$. You are correct that these definitions are not enough in the proof about embedding: we need a stronger condition $\varphi\equiv\psi\iff{\models\forall(\varphi\leftrightarrow\psi)}$.

Also, (4) prevents inheriting the propositional fact $\varphi\models\psi\iff {\models\varphi\to\psi}$. Indeed, the left-hand side means $\models(\forall \varphi)\to(\forall\psi)$ according to (5), while the right-hand side means $\models\exists(\varphi\to\psi)$ by (3). These formulas are not equivalent. But even of we reject (4) and define $\varphi\models\psi$ to mean $\models\exists(\varphi\to\psi)$, then $\varphi\models\psi$ and $\psi\models\varphi$ do not mean $\models\exists(\varphi\leftrightarrow\psi)$ (because $\exists x\,\theta$ and $\exists x\,\chi$ do not imply $\exists x\,(\theta\land\chi)$), and even if it did, that would not enough for the proof about embedding.

Here is how I believe these concepts are usually defined. If $\varphi$ has free variables, then $M\models\varphi$ is not defined. It is customary to consider a function $s$ from variables to the universe of $M$, and then $M\models_s\varphi$ can be defined as usual because now all variables have exact values. A formula $\varphi$ is satisfiable if $M\models_s\varphi$ for some $M$ and $s$, and $\varphi$ is a tautology, denoted by $\models\varphi$, if $M\models_s\varphi$ for all $M$ and $s$. Next, $\varphi\models\psi$ means that $M\models_s\varphi\implies M\models_s\psi$ for all $M$ and $s$, so this fact is equivalent to $\models(\varphi\to\psi)$ and to $\models\forall(\varphi\to\psi)$. Further, $\varphi\equiv\psi$ means $\varphi\models\psi$ and $\psi\models\varphi$, so $\varphi\equiv\psi\iff{\models\forall(\varphi\leftrightarrow\psi)}$. Using informal implication $\Rightarrow$, we interpret $\varphi(x)\Rightarrow\psi(x)$ not as $(\forall x\,\varphi(x))\Rightarrow (\forall x\,\psi(x))$ and certainly not as $\exists x\,(\varphi(x)\Rightarrow\psi(x))$, as in (3), but in the strongest way, as $\forall x\,(\varphi(x)\Rightarrow\psi(x))$.

Then preservation of formulas indeed respects equivalence. Suppose $f:M\to N$ preserves $\varphi$, i.e., $M\models\varphi(\bar{a})$ implies $N\models\varphi(f(\bar{a}))$ and $\varphi\equiv\psi$, i.e.,
\[
(6)\qquad\models\forall \bar{x}\,(\varphi(\bar{x})\leftrightarrow\psi(\bar{x})).
\]
Then $M\models\psi(\bar{a})$ implies $M\models\varphi(\bar{a})$ by (6), so $N\models\varphi(f(\bar{a}))$, which again implies $N\models\psi(f(\bar{a}))$ by (6).

I don't know much about currently used logic textbooks, but some people use "A mathematical Introduction to Logic" by H.B. Enderton.