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 , the theory of the rational numbers with their standard ordering, admits elimination of quantifiers. Suggestion: Compare " " and " ."
Let . According to Theorem 31F, we only need to show that for a formula of the form , where each is atomic or the negation of an atomic formula, there is a quantifier-free formula such that .
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 ( and where we can regroup the terms and use the fact that iff ). 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 where each variable can be .
- If there is an atomic formula that contains on both sides, then, if the formula itself is used in the conjunction then , and if its negation is used then we can safely omit this negation.
- If there is an atomic formula that does not contain , then we can safely move it out of the scope of the quantifier symbol, as and . Indeed, , where does not contain , is logically equivalent to , and we can use Example Q2a, page 121.
- If all the remaining atomic formulas have on the same side and the negations of atomic formulas have on the other side, i.e. and , or and , then , as is unbounded.
- If there are two atomic formulas containing on the right side, i.e. and , then . Indeed, if is a model of and , then iff for some , iff for some , either and , or and iff .
- Similarly, if there are two atomic formulas containing on the left side, i.e. and , then .
- Similar to cases 4 and 5, we consider cases of two formulas of the form and ; and (4); and ; and and (5).
- The last case is when there are only two formulas left in the expression , which is now or or . In the first two cases, , and in the third case . Indeed, if is a model of and , then iff for some , iff for some , and iff (density, see page 159) iff . The other two cases are similar.
Example. (intended to say ) becomes becomes becomes becomes . This last formula can, of course, be simplified to corresponding to its initial meaning.