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 ( ) formula is one of the form , where is quantifier-free. An existential ( ) formula is of the dual form . Let be a substructure of , and let .
(a) Show that if and is existential, then . And if and is universal, then .
(b) Conclude that the sentence is not logically equivalent to any universal sentence, nor to any existential sentence.
Remark: Part (a) says (when 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 is a sentence that is always preserved under substructures, then 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 , then for every , , implying, in particular, that for every , . Now, is quantifier free, and for all other parameters (including the equality) we have , , and are restrictions of , , and , correspondingly, meaning that their values or logical values are the same for any points in . This implies that for every , , or, equivalently, .
Now, for the first part, assume that holds but does not. Then, , which is, by definition, logically equivalent to . This latter expression is logically equivalent to (formally, we would need to rewrite each as and then argue that we can cancel double negations). Now, by the part we already proved (noting that is also quantifier-free), this implies , which is again logically equivalent to . 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 , where , . is a model of . Suppose that is logically equivalent to a universal sentence . Then, consider the substructure of . Note, that , therefore, is not a model of , however, according to (a), must be a model of . Hence, and are not logically equivalent.
Now, consider the sentence and suppose that it is logically equivalent to an existential sentence . Note, that , and is a model of . So, it should be a model of as well. At the same time, is not a model of , while, according to (a), must be a model of . We again conclude that and are not logically equivalent.