# 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 $\mathfrak{N}=(\mathbb{N};<)$ be the structure consisting of the natural numbers with their usual ordering. Show that there is some $\mathfrak{A}$ elementarily equivalent to $\mathfrak{N}$ such that $<^{\mathfrak{A}}$ has a descending chain. (That is, there must be $a_{0},a_{1},\ldots$ in $|\mathfrak{A}|$ such that $\in<^{\mathfrak{A}}$ for all $i$ .) 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 $c_{0}$ , $c_{1}$ , $c_{2}$ , $\ldots$ . For every $n\ge1$ , consider the message $\sigma_{n}$ saying that $c_{1} . For every $n\ge1$ , there is a model $\mathfrak{A}_{n}$ in the new language of the sentences $\mbox{Th}\mathfrak{A}\cup\{\sigma_{1},\ldots,\sigma_{n}\}$ . We just take $\mathfrak{A}$ , and let $c_{k}^{\mathfrak{A}_{n}}=n-k$ , for $k=0,\ldots,n$ . Hence, every finite subset of $\Sigma=\mbox{Th}\mathfrak{A}\cup\{\sigma_{1},\sigma_{2},\ldots\}$ is satisfiable. By the compactness theorem, there is a structure $\mathfrak{B}'$ that satisfies $\Sigma$ . The restriction $\mathfrak{B}$ of $\mathfrak{B}'$ to the initial language is a model of $\mbox{Th}\mathfrak{A}$ . Indeed, if $\mathfrak{A}$ is a model of a sentence $\sigma$ (which does not use constant symbols) then $\sigma\in\mbox{Th}\mathfrak{A}$ and $\Sigma\vdash\sigma$ . Then, there is a deduction of $\sigma$ from $\Sigma$ which does not use constant symbols (for example, we can proof this using rule EI), and, hence, $\mathfrak{B}$ proves $\sigma$ , implying $\sigma\in\mbox{Th}\mathfrak{B}$ . By Exercise 26(a) of Section 2.2, $\mathfrak{B}$ models $\mbox{Th}\mathfrak{A}$ implies $\mathfrak{B}\equiv\mathfrak{A}$ (another way is just to see that, similarly, if $\sigma\notin\mbox{Th}\mathfrak{A}$ , then $\neg\sigma\in\mbox{Th}\mathfrak{A}$ , $\neg\sigma\in\mbox{Th}\mathfrak{B}$ , $\sigma\notin\mbox{Th}\mathfrak{B}$ ).
To see that there is an infinite descending chain in $|\mathfrak{B}|$ , we note that $\in<^{\mathfrak{B}}$ iff $\in<^{\mathfrak{B}'}$ , and $\vDash_{\mathfrak{B}'}\sigma_{i}$ $\Rightarrow\vDash_{\mathfrak{B}'}c_{i+1} $\Rightarrow\in<^{\mathfrak{B}'}$ .
Note. This is another way to argue the Example on page 152.