# Section 2.2: Problem 20 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 the language has equality and a two-place predicate symbol
. Consider the two structures
and
for the language.

(a) Find a sentence true in one structure and false in the other.

(b) Show that any
sentence (as defined in the preceding exercise) true in
is also true in
.

*Suggestion*: First, for any finite set of real numbers, there is an automorphism of taking those real numbers to natural numbers. Secondly, by Exercise 18, universal formulas are preserved under substructures.
(a)
, true in
but not in
.

(b) This exercise is similar to 19(a). Let
where
is quantifier-free. Then
iff for every
,
iff for every
, there are
s.t.
. So, fix some
and
,
iff
, so that the latter expression holds (
may have less than
distinct elements, so we sort all distinct values and name them
), and let
be defined as
Then,
implies
(the only variables that can be free in
are
, so the values at all other variables do not matter, Theorem 22A). Consider
being the restriction of
to
where
. Since there are no constant or function symbols in our language,
with
being
restricted to
is a substructure of
. Hence, according to Exercise 18(a), by noting that the way we constructed
its range is exactly
, we have
. Now note, that
, hence,
, and
, i.e.
. Since
is a sentence, as long as it is true in
with one assignment
, it is true in
with any
, i.e.
. It remains to notice that
defined by
is an isomorphism of
onto
, as
iff
. Hence, according to the Homomorphism Theorem,
.