Section 2.2: Problem 18 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

A universal ( $\forall_{1}$ ) formula is one of the form $\forall x_{1}\ldots\forall x_{n}\theta$ , where $\theta$ is quantifier-free. An existential ( $\exists_{1}$ ) formula is of the dual form $\exists x_{1}\ldots\exists x_{n}\theta$ . Let $\mathfrak{A}$ be a substructure of $\mathfrak{B}$ , and let $s:V\rightarrow|\mathfrak{A}|$ .

(a) Show that if $\vDash_{\mathfrak{A}}\psi[s]$ and $\psi$ is existential, then $\vDash_{\mathfrak{B}}\psi[s]$ . And if $\vDash_{\mathfrak{B}}\phi[s]$ and $\phi$ is universal, then $\vDash_{\mathfrak{A}}\phi[s]$ .

(b) Conclude that the sentence $\exists xPx$ is not logically equivalent to any universal sentence, nor $\forall xPx$ to any existential sentence.

Remark: Part (a) says (when $\phi$ is a sentence) that any universal sentence is “preserved under substructures.” Being universal is a syntactic property — it has to do with the string of symbols. In contrast, being preserved under substructures is a semantic property — it has to do with satisfaction in structures. But this semantic property captures the syntactic property up to logical equivalence (which is all one could ask for). That is, if $\sigma$ is a sentence that is always preserved under substructures, then $\sigma$ is logically equivalent to a universal sentence. (This fact is due to Łoś and Tarski.)

(a) We show first the second part, as it involves the universal symbol, which is defined directly, unlike the existential symbol. So, assume $\vDash_{\mathfrak{B}}\forall x_{1}\ldots\forall x_{n}\theta[s]$ , then for every $d_{1},\ldots,d_{n}\in|\mathfrak{B}|$ , $\vDash_{\mathfrak{B}}\theta[s(x_{i}|d_{i})_{i=1}^{n}]$ , implying, in particular, that for every $d_{1},\ldots,d_{n}\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{B}}\theta[s(x_{i}|d_{i})_{i=1}^{n}]$ . Now, $\theta$ is quantifier free, and for all other parameters (including the equality) we have $=^{\mathfrak{A}}$ , $P_{i}^{\mathfrak{A}}$ , $c_{i}^{\mathfrak{A}}$ and $f_{i}^{\mathfrak{A}}$ are restrictions of $=^{\mathfrak{B}}$ , $P_{i}^{\mathfrak{B}}$ , $c_{i}^{\mathfrak{B}}$ and $f_{i}^{\mathfrak{B}}$ , correspondingly, meaning that their values or logical values are the same for any points in $|\mathfrak{A}|$ . This implies that for every $d_{1},\ldots,d_{n}\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}\theta[s(x_{i}|d_{i})_{i=1}^{n}]$ , or, equivalently, $\vDash_{\mathfrak{A}}\forall x_{1}\ldots\forall x_{n}\theta[s]$ .

Now, for the first part, assume that $\vDash_{\mathfrak{A}}\exists x_{1}\ldots\exists x_{n}\theta[s]$ holds but $\vDash_{\mathfrak{B}}\exists x_{1}\ldots\exists x_{n}\theta[s]$ does not. Then, $\not\vDash_{\mathfrak{B}}\exists x_{1}\ldots\exists x_{n}\theta[s]$ , which is, by definition, logically equivalent to $\vDash_{\mathfrak{B}}\neg\exists x_{1}\ldots\exists x_{n}\theta[s]$ . This latter expression is logically equivalent to $\vDash_{\mathfrak{B}}\forall x_{1}\ldots\forall x_{n}\neg\theta[s]$ (formally, we would need to rewrite each $\exists x$ as $\neg\forall x\neg$ and then argue that we can cancel double negations). Now, by the part we already proved (noting that $\neg\theta$ is also quantifier-free), this implies $\vDash_{\mathfrak{A}}\forall x_{1}\ldots\forall x_{n}\neg\theta[s]$ , which is again logically equivalent to $\not\vDash_{\mathfrak{A}}\exists x_{1}\ldots\exists x_{n}\theta[s]$ . Contradiction.

(b) If two sentences are logically equivalent then a model of one of them is a model of the other, and vice versa. Consider the structure $\mathfrak{A}=(\{0,1\};Z,O)$ , where $Z=\{0\}$ , $O=\{1\}$ . $\mathfrak{A}$ is a model of $\sigma=\exists xZx$ . Suppose that $\sigma$ is logically equivalent to a universal sentence $\tau$ . Then, consider the substructure $\mathfrak{A}'=(\{1\};Z)$ of $\mathfrak{A}$ . Note, that $Z^{\mathfrak{A}'}=\emptyset$ , therefore, $\mathfrak{A}'$ is not a model of $\sigma$ , however, according to (a), $\mathfrak{A}'$ must be a model of $\tau$ . Hence, $\sigma$ and $\tau$ are not logically equivalent.

Now, consider the sentence $\sigma=\forall xOx$ and suppose that it is logically equivalent to an existential sentence $\tau$ . Note, that $O^{\mathfrak{A}'}=\{1\}$ , and $\mathfrak{A}'$ is a model of $\sigma$ . So, it should be a model of $\tau$ as well. At the same time, $\mathfrak{A}$ is not a model of $\sigma$ , while, according to (a), $\mathfrak{A}$ must be a model of $\tau$ . We again conclude that $\sigma$ and $\tau$ are not logically equivalent.

Subpages

Section 2.2: Problem 18 Solution

Section 2.2: Problem 18 Solution