# 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.