# Section 2.2: Problem 18 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 universal (
) formula is one of the form
, where
is quantifier-free. An existential (
) formula is of the dual form
. Let
be a substructure of
, and let
.

(a) Show that if
and
is existential, then
. And if
and
is universal, then
.

(b) Conclude that the sentence
is not logically equivalent to any universal sentence, nor
to any existential sentence.

*Remark*: Part (a) says (when is a sentence) that any universal sentence is “preserved under substructures.” Being universal is a syntactic property — it has to do with the string of symbols. In contrast, being preserved under substructures is a semantic property — it has to do with satisfaction in structures. But this semantic property captures the syntactic property up to logical equivalence (which is all one could ask for). That is, if is a sentence that is always preserved under substructures, then is logically equivalent to a universal sentence. (This fact is due to Łoś and Tarski.)

(a) We show first the second part, as it involves the universal symbol, which is defined directly, unlike the existential symbol. So, assume
, then for every
,
, implying, in particular, that for every
,
. Now,
is quantifier free, and for all other parameters (including the equality) we have
,
,
and
are restrictions of
,
,
and
, correspondingly, meaning that their values or logical values are the same for any points in
. This implies that for every
,
, or, equivalently,
.

Now, for the first part, assume that
holds but
does not. Then,
, which is, by definition, logically equivalent to
. This latter expression is logically equivalent to
(formally, we would need to rewrite each
as
and then argue that we can cancel double negations). Now, by the part we already proved (noting that
is also quantifier-free), this implies
, which is again logically equivalent to
. Contradiction.

(b) If two sentences are logically equivalent then a model of one of them is a model of the other, and vice versa. Consider the structure
, where
,
.
is a model of
. Suppose that
is logically equivalent to a universal sentence
. Then, consider the substructure
of
. Note, that
, therefore,
is not a model of
, however, according to (a),
must be a model of
. Hence,
and
are not logically equivalent.

Now, consider the sentence
and suppose that it is logically equivalent to an existential sentence
. Note, that
, and
is a model of
. So, it should be a model of
as well. At the same time,
is not a model of
, while, according to (a),
must be a model of
. We again conclude that
and
are not logically equivalent.