(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$ , $\alpha$ 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 $$\begin{eqnarray*} \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 & v_{1}=0\\ & \wedge & v_{1}\le v_{1}\wedge v_{1}\le v_{2}\wedge\neg v_{2}\le v_{1}\wedge v_{2}\le v_{2}\\ & \wedge & v_{1}+v_{1}=v_{1}\wedge v_{1}+v_{2}=v_{2}\\ & \wedge & v_{2}+v_{1}=v_{2}\wedge v_{2}+v_{2}=v_{1}) \end{eqnarray*}$$ 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: $$\begin{eqnarray*} b\le b\wedge b\le a & \wedge & \neg a\le b\wedge a\le a\\ b+b=b\wedge b+a=a & \wedge & a+b=a\wedge a+a=b \end{eqnarray*}$$ 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.