# Section 2.5: Problem 8 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 (with equality) has just the parameters
and
, where
is a two-place predicate symbol. Let
be the structure with
, the set of integers (positive, negative, and zero) and with
iff
. Thus
looks like an infinite graph:
Show that there is an elementarily equivalent structure
that is not connected. (Being connected means that for every two members of
, there is a path between them. A path — of length
— from
to
is a sequence
with
and
and
for each
.)

*Suggestion*: Add constant symbols and . Write down sentences saying and are far apart. Apply compactness.
I think this is a really neat exercise. At first, it seems that this is impossible. Indeed,
is a “model” of the following sentence “
such that
is a path connecting
and
” (where we can formally write down what the last part means). Hence, every structure “equivalent” to
must be a model of this sentence as well, meaning that it must be connected (as the sentence is simply the definition of connectedness). However, what breaks here, is that the sentence is not a first-order sentence. The problem is that it involves the existence of an arbitrary number of variables, which may be different for different
and
, and, more importantly, it can be greater than any fixed
(so, for example, if
were finite, every elementarily equivalent structure would be connected). What is implicitly missing in the sentence, is
, but this is not a valid part of the first-order language. Therefore, we cannot express connectedness in one or, equivalently, any finite number of sentences. We know, that for any pair
and
, it will satisfy all but finite number of wffs saying that
and
are connected by a path of length at most
, but there is always a pair that does not satisfy any particular such wff. Therefore,
fails to be a model of the generalization of any such sentence.

We can look at the problem from the other direction. Namely, as we said, the existence of an elementarily equivalent
which is not connected is due to
being an infinite structure. Therefore, for any sentence
saying that there are points
and
that are not connected by any path of length
(which is just the negation of the generalizations of the sentences mentioned in the previous paragraph), i.e. for any
being
, where
is
is a model. And
is a model of the set
of all such sentences.

Now, as suggested, we extend the language by adding constant symbols
and
, so that each
is now a sentence of the language (
and
are now constant symbols rather than variables, and
’s are not wffs in the new language). The structure
, which is
with
and
, is a model of
iff
. Moreover,
is a model of a sentence
not using constant symbols
and
iff
is a model of
(this can be shown directly, by induction). Therefore, if we consider the set of sentences
(
was introduced in Exercise 26 of Section 2.2, and is formally defined on page 148), then every finite subset
of
has a model (we just find the maximum
such that
and take
). By the compactness theorem,
has a model,
. Let
be the restriction of
to the original language. Now, 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
. Vice versa, if
, then
,
,
. Overall,
and
are elementarily equivalent (another way is just to use Exercise 26(a) of Section 2.2 by noting that
models
).

To see that
is not connected, we note that it is connected iff
is connected (the connectedness has nothing to do with constant symbols, and deals only with the underlying structure, i.e. the universe and relation
), and if
and
were connected by a path of length
,
would not be a model of
.