« Section 3.1: Problem 6 Solution

# Section 3.1: Problem 7-A 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
(Additional) Show that $\mbox{Th}(\mathbb{Q};<)$ , the theory of the rational numbers with their standard ordering, admits elimination of quantifiers. Suggestion: Compare "$\exists x(u " and "$u ."
Let $T=\mbox{Th}(\mathbb{Q};<)$ . According to Theorem 31F, we only need to show that for a formula $\phi$ of the form $\exists x(\alpha_{0}\wedge\ldots\wedge\alpha_{n})$ , where each $\alpha_{i}$ is atomic or the negation of an atomic formula, there is a quantifier-free formula $\psi$ such that $T\vDash\phi\leftrightarrow\psi$ .
I am not sure whether the equality symbol is assumed to be a part of the language, but in any case, we can assume that the language does not have the equality symbol ($T\vDash t_{1}=t_{2}\leftrightarrow\neg t_{1} and $T\vDash t_{1}\neq t_{2}\leftrightarrow t_{1} where we can regroup the terms and use the fact that $\exists x(\alpha\vee\beta)$ iff $\exists x\alpha\vee\exists x\beta$ ). In fact, instead of removing the equality symbol, it would be more convenient to get rid of the negations of atomic formulas instead (see Exercise 4 of Section 3.2), but, as I said, we are not explicitly given that the language has the equality symbol. There are also no function or constant symbols in the language. Therefore, each atomic formula is of the form $v_{i} where each variable can be $x$ .
1. If there is an atomic formula that contains $x$ on both sides, then, if the formula itself is used in the conjunction then $\vDash\phi\leftrightarrow x , and if its negation is used then we can safely omit this negation.
2. If there is an atomic formula that does not contain $x$ , then we can safely move it out of the scope of the quantifier symbol, as $\vDash\exists x(v_{i} and $\vDash\exists x(\neg v_{i} . Indeed, $\exists x(\alpha\wedge\phi')$ , where $\alpha$ does not contain $x$ , is logically equivalent to $\neg\forall x(\alpha\rightarrow\neg\phi')$ , and we can use Example Q2a, page 121.
3. If all the remaining atomic formulas have $x$ on the same side and the negations of atomic formulas have $x$ on the other side, i.e. $v_{i} and $\neg x , or $x and $\neg v_{j} , then $T\vDash\phi'\leftrightarrow\neg x , as $\mathbb{Q}$ is unbounded.
4. If there are two atomic formulas containing $x$ on the right side, i.e. $v_{i} and $v_{j} , then $T\vDash\exists x(v_{i} $\leftrightarrow(v_{i} . Indeed, if $\mathfrak{A}$ is a model of $T$ and $s:V\rightarrow|\mathfrak{A}|$ , then $\vDash_{\mathfrak{A}}\exists x(v_{i} iff for some $d\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}v_{i} iff for some $d\in|\mathfrak{A}|$ , either $\in<^{\mathfrak{A}}$ and $\vDash_{\mathfrak{A}}v_{j} , or $\notin<^{\mathfrak{A}}$ and $\vDash_{\mathfrak{A}}v_{i} iff $\vDash_{\mathfrak{A}}(v_{i} .
5. Similarly, if there are two atomic formulas containing $x$ on the left side, i.e. $x and $x , then $T\vDash\exists x(x $\leftrightarrow(v_{i} .
6. Similar to cases 4 and 5, we consider cases of two formulas of the form $\neg x and $v_{j} ; $\neg x and $\neg x (4); $\neg v_{i} and $x ; and $\neg v_{i} and $\neg v_{j} (5).
7. The last case is when there are only two formulas left in the expression $\phi'$ , which is now $\exists x(v_{i} or $\exists x(\neg x or $\exists x(\neg x . In the first two cases, $T\vDash\phi'\leftrightarrow v_{i} , and in the third case $T\vDash\phi'\leftrightarrow v_{i} . Indeed, if $\mathfrak{A}$ is a model of $T$ and $s:V\rightarrow|\mathfrak{A}|$ , then $\vDash_{\mathfrak{A}}\exists x(v_{i} iff for some $d\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}v_{i} iff for some $d\in|\mathfrak{A}|$ , $s(v_{i}) and $d iff (density, see page 159) $s(v_{i}) iff $\vDash_{\mathfrak{A}}v_{i} . The other two cases are similar.
Example. $\exists x(x=v_{1}\wedge v_{2} (intended to say $v_{2} ) becomes $\exists x(\neg x becomes $v_{2} becomes $v_{2} $\vee(\neg v_{1} becomes $\vee(\neg v_{1} . This last formula can, of course, be simplified to corresponding to its initial meaning.