# 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 $\forall$ ) is a two-place predicate symbol $P$ . Show that if $\mathfrak{A}$ is finite and $\mathfrak{A}\equiv\mathfrak{B}$ , then $\mathfrak{A}$ is isomorphic to $\mathfrak{B}$ . Suggestion: Suppose the universe of $\mathfrak{A}$ has size $n$ . Make a single sentence $\sigma$ of the form $\exists v_{1}\ldots\exists v_{n}\theta$ that describes $\mathfrak{A}$ “completely.” That is, on the one hand, $\sigma$ must be true in $\mathfrak{A}$ . And on the other hand, any model of $\sigma$ must be exactly like (i.e., isomorphic to) $\mathfrak{A}$ .
$^{∗}$ (b) Show that the result of part (a) holds regardless of what parameters the language contains.
(a) Suppose $|\mathfrak{A}|$ is a singleton, $|\mathfrak{A}|=\{a\}$ . Then, $P$ is either empty or $\{(a,a)\}$ . In the first case, we let $\sigma$ be $\exists v_{1}(\forall v_{2}v_{2}=v_{1}\wedge\neg Pv_{1}v_{1})$ , and in the second case, $\exists v_{1}(\forall v_{2}v_{2}=v_{1}\wedge Pv_{1}v_{1})$ . Any model $\mathfrak{B}$ of $\sigma$ must have the universe with a single element $b$ only such that $Pbb$ holds iff $Paa$ holds in $\mathfrak{A}$ . Therefore, $h(x)=b$ is an isomorphism of $\mathfrak{A}$ onto $\mathfrak{B}$ .
If $|\mathfrak{A}|=\{a,b\}$ , then there are 4 possible binary relations on $|\mathfrak{A}|$ . We create a sentence $\sigma$ of the form $\exists v_{1}\exists v_{2}(v_{1}\neq v_{2}\wedge\forall v_{3}(v_{3}=v_{1}\vee v_{3}=v_{2})\wedge\beta)$ , where $\beta$ is the conjunction of all requirements on $P$ , for example, $Pv_{1}v_{1}\wedge Pv_{1}v_{2}\wedge\neg Pv_{2}v_{1}\wedge Pv_{2}v_{2}$ (corresponding to $a=1$ , $b=2$ and $\le$ ). Again, for any model $\mathfrak{B}$ of $\sigma$ , the first part of $\sigma$ ensures that $|\mathfrak{B}|$ has exactly 2 elements, and the second part ensures that there is a one-to-one correspondence $h$ between elements of $|\mathfrak{A}|$ and $|\mathfrak{B}|$ such that $h$ preserves $P$ . Since $P$ is the only parameter to preserve, $h$ is an isomorphism of $\mathfrak{A}$ onto $\mathfrak{B}$ .
In general, if there are $n$ elements in $\mathfrak{A}$ , we create a sentence $\sigma$ of the form $\exists v_{1}\ldots\exists v_{n}(\alpha\wedge\beta)$ such that for every model $\mathfrak{B}$ of $\sigma$ , is true iff $|\mathfrak{B}|$ has $n$ elements, and $\beta$ ensures that there is a one-to-one correspondence $h$ between $|\mathfrak{A}|$ and $|\mathfrak{B}|$ that preserves $P$ . Then $h$ is an isomorphism of $\mathfrak{A}$ onto $\mathfrak{B}$ .
(b) In the general case, a homomorphism must preserve predicates, constants and functions. For a finite $\mathfrak{A}$ such that $|\mathfrak{A}|$ has $n$ elements, we create a sentence $\sigma$ of the form $\exists v_{1}\ldots\exists v_{n}(\alpha\wedge\beta)$ such that for any model $\mathfrak{B}$ of $\sigma$ , $\alpha$ ensures that there are exactly $n$ elements in $|\mathfrak{B}|$ , and $\beta$ is the conjunction of all the requirements on predicates, constants and functions. For example, suppose that $\mathfrak{A}$ is $(\{0,1\};\le,0,+)$ . Then $\sigma$ may take the form In this case, for any model $\mathfrak{B}=(|\mathfrak{B}|;P^{\mathfrak{B}},c^{\mathfrak{B}},f^{\mathfrak{B}})$ of $\sigma$ , $|\mathfrak{B}|$ must have exactly to elements, say $|\mathfrak{B}|=\{a,b\}$ , such that if, say, $c^{\mathfrak{B}}=b$ , then the following must hold: and there is an isomorphism $h$ of $\mathfrak{A}$ onto $\mathfrak{B}$ such that $h(0)=b$ and $h(1)=a$ that is bijective and preserves predicates, constants and functions.