# Section 2.2: Problem 19 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

An
formula is one of the form
, where
is universal.

(a) Show that if an
sentence in a language not containing function symbols (not even constant symbols) is true in
, then it is true in some finite substructure of
.

(b) Conclude that
is not logically equivalent to any
sentence.

(a) Let
where
is quantifier-free. Then
iff for every
,
iff for every
, there are
s.t.
. So, fix some
and
so that the latter expression holds (
may have less than
distinct elements), 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
. Well, here is where we have to assume that not only
is constant- and function-free, but so is
(that is the language as well). Otherwise, there might be, for example, a function that would not have any closed restriction to any finite subset, that is there would not be any finite substructure of
at all. Since there are no constant or function symbols in our language,
with all the predicates 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.
where
is a finite substructure of
.

(b) Let
. Then,
is a model of
. If
is logically equivalent to an
sentence
, then
is a model of
as well. Note, that
does not have any constant or function symbols, so that there is a finite subset
of
, s.t.
restricted to
is a model
of
(according to (a)). However, there is no finite substructure of
such that
is true in it, as for any finite domain there would be the maximum element
such that
, or logically equivalently,
, implying
, i.e.
. In particular,
is not a model of
, and
and
are not logically equivalent.