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 .