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.