Section 2.2: Problem 17 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) Consider a language with equality whose only parameter (aside from ) is a two-place predicate symbol . Show that if is finite and , then is isomorphic to . Suggestion: Suppose the universe of has size . Make a single sentence of the form that describes “completely.” That is, on the one hand, must be true in . And on the other hand, any model of must be exactly like (i.e., isomorphic to) .
(b) Show that the result of part (a) holds regardless of what parameters the language contains.
(a) Suppose is a singleton, . Then, is either empty or . In the first case, we let be , and in the second case, . Any model of must have the universe with a single element only such that holds iff holds in . Therefore, is an isomorphism of onto .
If , then there are 4 possible binary relations on . We create a sentence of the form , where is the conjunction of all requirements on , for example, (corresponding to , and ). Again, for any model of , the first part of ensures that has exactly 2 elements, and the second part ensures that there is a one-to-one correspondence between elements of and such that preserves . Since is the only parameter to preserve, is an isomorphism of onto .
In general, if there are elements in , we create a sentence of the form such that for every model of , is true iff has elements, and ensures that there is a one-to-one correspondence between and that preserves . Then is an isomorphism of onto .
(b) In the general case, a homomorphism must preserve predicates, constants and functions. For a finite such that has elements, we create a sentence of the form such that for any model of , ensures that there are exactly elements in , and is the conjunction of all the requirements on predicates, constants and functions. For example, suppose that is . Then may take the form In this case, for any model of , must have exactly to elements, say , such that if, say, , then the following must hold: and there is an isomorphism of onto such that and that is bijective and preserves predicates, constants and functions.