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

Consider a language with a two-place predicate symbol
, and let
be the structure consisting of the natural numbers with their usual ordering. Show that there is some
elementarily equivalent to
such that
has a descending chain. (That is, there must be
in
such that
for all
.)

*Suggestion*: Apply the compactness theorem.*Remark*: The point of this exercise is to demonstrate that in this language, one can

*not*express, “There is no descending chain.”

Similar to Exercise 8 of Section 2.5, and the method discussed in this section, we extend the language to include an infinitely countable number of new constant symbols
,
,
,
. For every
, consider the message
saying that
. For every
, there is a model
in the new language of the sentences
. We just take
, and let
, for
. Hence, every finite subset of
is satisfiable. By the compactness theorem, there is a structure
that satisfies
. The restriction
of
to the initial language is a model of
. Indeed, if
is a model of a sentence
(which does not use constant symbols) then
and
. Then, there is a deduction of
from
which does not use constant symbols (for example, we can proof this using rule EI), and, hence,
proves
, implying
. By Exercise 26(a) of Section 2.2,
models
implies
(another way is just to see that, similarly, if
, then
,
,
).

To see that there is an infinite descending chain in
, we note that
iff
, and
.

Note. This is another way to argue the Example on page 152.