Section 2.2: Problem 27 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 that the parameters of the language are
and a two-place predicate symbol
. List all of the non-isomorphic structures of size 2. That is, give a list of structures (where the universe of each has size 2) such that any structure of size 2 is isomorphic to exactly one structure on the list.
I actually already did something similar in Exercise 2. Consider the structure
where
varies. There are 16 possibilities, 10 being essentially different (there are no automorphisms between any two of them).
Given any structure
of size 2, we determine
, the number of pairs in
. If
, any bijective function
will work as an isomorphism. Similarly for
and
. If
, then either we have
or
in
, or
or
in
. Correspondingly, there is an isomorphism of
onto
or
. If
, then let
be the number of pairs in
of the form
. If
, then
, and we are in case
. If
, then we have one such pair, say,
, and one more either
or
, correspondingly we are in case
or
. If
, then
, and we are in case
. Finally, if
, then there is one pair missing in
, and if
, we are in case
, otherwise,
, and we are in case
. Here “we are in case
” means that there is an obvious bijective correspondence
between
and
such that
preserves
.