Section 2.2: Problem 20 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
Assume the language has equality and a two-place predicate symbol . Consider the two structures and for the language.
(a) Find a sentence true in one structure and false in the other.
(b) Show that any sentence (as defined in the preceding exercise) true in is also true in . Suggestion: First, for any finite set of real numbers, there is an automorphism of taking those real numbers to natural numbers. Secondly, by Exercise 18, universal formulas are preserved under substructures.
(a) , true in but not in .
(b) This exercise is similar to 19(a). Let where is quantifier-free. Then iff for every , iff for every , there are s.t. . So, fix some and , iff , so that the latter expression holds ( may have less than distinct elements, so we sort all distinct values and name them ), 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 where . Since there are no constant or function symbols in our language, with being 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. . It remains to notice that defined by is an isomorphism of onto , as iff . Hence, according to the Homomorphism Theorem, .