« Section 2.2: Problem 18 Solution

Section 2.2: Problem 20 Solution »

Section 2.2: Problem 19 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
An formula is one of the form , where is universal.
(a) Show that if an sentence in a language not containing function symbols (not even constant symbols) is true in , then it is true in some finite substructure of .
(b) Conclude that is not logically equivalent to any sentence.
(a) Let where is quantifier-free. Then iff for every , iff for every , there are s.t. . So, fix some and so that the latter expression holds ( may have less than distinct elements), and let be defined as Then, implies (the only variables that can be free in are , so the values at all other variables do not matter, Theorem 22A). Consider being the restriction of to . Well, here is where we have to assume that not only is constant- and function-free, but so is (that is the language as well). Otherwise, there might be, for example, a function that would not have any closed restriction to any finite subset, that is there would not be any finite substructure of at all. Since there are no constant or function symbols in our language, with all the predicates restricted to is a substructure of . Hence, according to Exercise 18(a), by noting that the way we constructed its range is exactly , we have . Now note, that , hence, , and , i.e. . Since is a sentence, as long as it is true in with one assignment , it is true in with any , i.e. where is a finite substructure of .
(b) Let . Then, is a model of . If is logically equivalent to an sentence , then is a model of as well. Note, that does not have any constant or function symbols, so that there is a finite subset of , s.t. restricted to is a model of (according to (a)). However, there is no finite substructure of such that is true in it, as for any finite domain there would be the maximum element such that , or logically equivalently, , implying , i.e. . In particular, is not a model of , and and are not logically equivalent.