Section 3.1: Problem 2 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
Complete the proof of Theorem 31F. Suggestion: Use induction.
Let us recall Theorem 31F.
Assume that for every formula of the form where each is an atomic formula or the negation of an atomic formula, there is a quantifier-free formula such that . Then admits elimination of quantifiers.
The proof in the text has already shown that, given the assumption of the theorem, one can find a quantifier-free equivalent for any formula of the form where is quantifier-free. It follows that has a quantifier-free equivalent as well. Now, we can use the prenex normal form (Section 2.6) to argue that every wff has a logically equivalent wff in the prenex normal form, in which we can eliminate quantifiers one-by-one.