« Section 3.3: Problem 3 Solution

Section 3.3: Problem 5 Solution »

Section 3.3: 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 in the proof preceding Theorem 33L, formula (4) is logically implied by the set consisting of formulas (1), (2), and (3).
Let us recall that we show that is representable if , and are (functionally) representable (by , and , respectively). We let be , and argue that for every , imply
To show (4), by the generalization (DG) theorem, it is sufficient to show .
Now, is logically equivalent to (the prenex normal form, see Section 2.6), and to show it is sufficient to show that for some terms and substitutable for and , respectively. So, let . Then, by the deduction (DD) and contraposition (DC) theorems, it is sufficient to show that . By using deduction axiom group 2 (DA2), we can get rid of quantifiers in equations (1)-(3) and substitute for , hence, Equation (5), by DA1 and modus ponens (DMP), implies , and equations (6) and (7), by DA5, DA2, DA1 and DMP, imply and .
To show , by DD and DG, it is sufficient to show that . From (5), by DA1 and DMP, . Further, by DA2, DA1 and DMP, equations (2) and (3) imply and , respectively. Moreover, by DA6, and , from which, by using DA2 and substituting for and for , we obtain and . Overall, by DMP, we have .