« Section 3.2: Problem 3 Solution

# Section 3.2: Problem 4 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
Show that the theory of the real numbers with its usual ordering, $\mbox{Th}(\mathbb{R};<)$ , admits elimination of quantifiers. (Assume that the language includes equality.)
Solution 1. $\mathfrak{R}_{L}=(\mathbb{R};<)\equiv\mathfrak{Q}_{L}=(\mathbb{Q};<)$ (see page 159). Now, according to Exercise 7-A of Section 3.1, $\mathfrak{Q}_{L}$ admits elimination of quantifiers, i.e. for every wff $\phi$ there is a quantifier-free wff $\psi$ such that $\mathfrak{Q}_{L}\vDash\phi\leftrightarrow\psi$ , hence, $\mathfrak{R}_{L}\vDash\phi\leftrightarrow\psi$ .
Solution 2. We can actually repeat the solution of Exercise 7-A of Section 3.1 here. This emphasizes the point that the two structures are elementarily equivalent, i.e. everything we said is true in one structure is true in the other.
Solution 3. In this exercise we are explicitly given that the language has the equality symbol, so there is no reason to get rid of the equality symbols from the conjunction to show a more general case. Instead, it will turn out to be more convenient to transform the formula so that there are no negations of atomic formulas in it, but we will do the transformation later in one of the steps. Each atomic formula in the conjunction $\phi$ is of the form $v_{i} or $v_{i}=v_{j}$ .
1. If there is an atomic formula that does not contain $x$ at all, then $\mathfrak{R}_{L}\vDash\exists x(\alpha\wedge\phi')\leftrightarrow\alpha\wedge\exists x\phi'$ , where $\alpha$ does not contain $x$ (and we continue with $\exists x\phi'$ ). Indeed, $\exists x(\alpha\wedge\phi')$ is logically equivalent to $\neg\forall x(\alpha\rightarrow\neg\phi')$ , and we can use Example Q2a, page 121.
2. If there is an atomic formula that contains $x$ on both sides, then $\mathfrak{R}_{L}\vDash\exists x(x , $\mathfrak{R}_{L}\vDash\exists x(\neg x=x\wedge\phi')\leftrightarrow x\neq x$ (and we stop here), and $\mathfrak{R}_{L}\vDash\exists x(x=x\wedge\phi')\leftrightarrow\exists x\phi'$ , $\mathfrak{R}_{L}\vDash\exists x(\neg x (continue).
3. Now, for any negation of an atomic formula we note that $\mathfrak{R}_{L}\vDash\neg t and $\mathfrak{R}_{L}\vDash\neg t=s\leftrightarrow t . We can now regroup the atomic formulas and use the fact that $\exists x(\alpha\vee\beta)$ iff $\exists x\alpha\vee\exists x\beta$ . From now on, we have atomic formulas only in $\phi$ .
4. If there is an atomic formula $x=v_{i}$ (or, equivalently, $v_{i}=x$ ), then $\mathfrak{R}_{L}\vDash\exists x(x=v_{i}\wedge\phi')\leftrightarrow(\phi')_{v_{i}}^{x}$ (stop). Indeed, for every model $\mathfrak{A}$ of $\mbox{Th}\mathfrak{R}_{L}$ and $s:V\rightarrow|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}\exists x(x=v_{i}\wedge\phi')[s]$ iff for some $d\in|\mathfrak{A}|$ , $d=s(v_{i})$ and $\vDash_{\mathfrak{A}}\phi'[s(x|d)]$ iff $\vDash_{\mathfrak{A}}\phi'[s(x|s(v_{i}))]$ iff $\vDash_{\mathfrak{A}}(\phi')_{v_{i}}^{x}[s]$ .
5. If all the remaining atomic formulas contain $x$ on the same side, that is they are all of the form $x , or all of the form $v_{j} , then $\mathfrak{R}_{L}\vDash\exists x\phi\leftrightarrow x=x$ (stop), as $\mathfrak{R}_{L}$ is unbounded.
6. Otherwise, we have $\phi=\wedge_{k=1}^{m}x , and $\mathfrak{R}_{L}\vDash\exists x\phi\leftrightarrow\wedge_{k=1,\ldots,m,l=1,\ldots,n}v_{j_{l}} (both are true in a model $\mathfrak{A}$ of $\mathfrak{R}_{L}$ with $s:V\rightarrow|\mathfrak{A}|$ iff there is some $d\in|\mathfrak{A}|$ such that $d<^{\mathfrak{A}}s(v_{i_{k}})$ for $k=1,\ldots,m$ and $s(v_{j_{l}})<^{\mathfrak{A}}d$ for $l=1,\ldots,n$ iff $s(v_{j_{l}})<^{\mathfrak{A}}s(v_{i_{k}})$ for $k=1,\ldots,m$ and $l=1,\ldots,n$ ).
Example (same as in the solution of Exercise 7-A of Section 3.1). $\exists x(x=v_{1}\wedge v_{2} (intended to say $v_{2} ) becomes $v_{2} becomes $v_{2} $\vee\exists x(x=v_{1}\wedge x becomes $v_{2} .