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.