Section 2.4: Problem 8 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
(Q2b) Assume that does not occur free in . Show that . Also show that, under the same assumption, we have Q3a: .
By Rule T, it is sufficient to show both and .
The first one, by deduction, contraposition and MP rules, is “equivalent” to . Now, by axiom group 2 and MP, . Further, and are tautologies. By MP, we have both and . By the generalization theorem, . Since tautologically implies , by Rule T, we have what we need.
The second one, by deduction, contraposition and MP rules, is “equivalent” to . For this formula, using the generalization theorem based on the fact that does not occur free in , it is sufficient to show , which, by contraposition, deduction and MP rules, is “equivalent” to . By MP rule, it is sufficient to show , or, by deduction, , or, by contraposition and MP, , which is an axiom of group 2.
By substituting for and for , and using contraposition tautologies among other things, we obtain . Well, this approach is taken from the text, where it was used in a similar example on pages 121-122. However, it seems not completely fair, as among other things we would need to use the contraposition tautology inside the quantified formula . Of course, we could easily argue that by substituting tautologically equivalent subformulas we obtain formulas that can be proved from each other, but I don’t think there was a theorem saying this.
Alternatively, by using instead of and their negations, what we need to show is and . Now, we can use the contraposition tautology for those prime formulas that are outside of any quantified subformulas, obtaining and . So, given what we have already proved, if we show that , we are done (this formula also illustrates the point that we need to use the contraposition tautology inside quantified formulas). By using deduction and contraposition theorems, as well as MP, it is sufficient to show that . By axiom group 3, MP and generalization theorem, it is sufficient to show that , which is a tautology (we were able to get rid of all quantifiers to use axiom group 1).