Section 2.4: Problem 17 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 deductions (from $\emptyset$ ) of the following formulas exist:

(a) $\forall x(\alpha\rightarrow\beta)\rightarrow(\exists x\alpha\rightarrow\exists x\beta)$ .

(b) $\exists x(Py\wedge Qx)\leftrightarrow Py\wedge\exists xQx$ .

(a) We need to show $\vdash\forall x(\alpha\rightarrow\beta)\rightarrow\neg\forall x\neg\alpha\rightarrow\neg\forall x\neg\beta$ . By deduction, it is sufficient to show that $\{\forall x(\alpha\rightarrow\beta),\neg\forall x\neg\alpha\}\vdash\neg\forall x\neg\beta$ . By contraposition, it is sufficient to show that $\{\forall x(\alpha\rightarrow\beta),\forall x\neg\beta\}\vdash\forall x\neg\alpha$ . By MP, it is sufficient to show that $\forall x(\alpha\rightarrow\beta)\vdash\forall x\neg\beta\rightarrow\forall x\neg\alpha$ . By axiom group 3 and generalization theorem, it is sufficient to show that $\forall x(\alpha\rightarrow\beta)\vdash\neg\beta\rightarrow\neg\alpha$ . By axiom group 2, $\vdash\forall x(\alpha\rightarrow\beta)\rightarrow\alpha\rightarrow\beta$ . So, that

, and, using MP for the tautology $\vdash(\alpha\rightarrow\beta)\rightarrow\neg\beta\rightarrow\neg\alpha$ , we deduct $\neg\beta\rightarrow\neg\alpha$ from $\forall x(\alpha\rightarrow\beta)$ .

(b) Note, that $\gamma\wedge\delta$ is tautologically equivalent to $\neg(\gamma\rightarrow\neg\delta)$ . By tautologically equivalent we do not imply that one uses these first-order tautologies in the proof of the above equation (for example, you cannot use tautologies to substitute subformulas of quantified formulas), but rather that these connectives are defined this way.

So, we need to show that $\vdash\neg\forall x\neg(\neg(Py\rightarrow\neg Qx))\rightarrow\neg(Py\rightarrow\forall x\neg Qx)$ and $\vdash\neg(Py\rightarrow\forall x\neg Qx)\rightarrow\neg\forall x\neg(\neg(Py\rightarrow\neg Qx))$ .

For the first formula, using the deduction, contraposition and generalization theorems, as well as axiom group 1 (for tautology $\vdash\alpha\rightarrow\neg\neg\alpha$ ), it is sufficient to show that $Py\rightarrow\forall x\neg Qx\vdash Py\rightarrow\neg Qx$ . By the deduction theorem, it is sufficient to show that $Py\rightarrow\forall x\neg Qx;Py\vdash\neg Qx$ . Now, $Py\rightarrow\forall x\neg Qx;Py\vdash\forall x\neg Qx$ and $\vdash\forall x\neg Qx\rightarrow\neg Qx$ (axiom group 2), therefore, by MP, $Py\rightarrow\forall x\neg Qx;Py\vdash\neg Qx$ .

For the second formula, using the deduction, contraposition theorems, it is sufficient to show that $\forall x\neg(\neg(Py\rightarrow\neg Qx))\vdash Py\rightarrow\forall x\neg Qx$ . Using the deduction theorem and MP, it is sufficient to show that $Py\vdash\forall x\neg(\neg(Py\rightarrow\neg Qx))\rightarrow\forall x\neg Qx$ . By axiom group 3, MP and generalization theorem, it is sufficient to show $Py\vdash\neg(\neg(Py\rightarrow\neg Qx))\rightarrow\neg Qx$ . By MP, it is sufficient to show that $\vdash Py\rightarrow\neg(\neg(Py\rightarrow\neg Qx))\rightarrow\neg Qx$ , which is a tautology.

Subpages

Section 2.4: Problem 17 Solution

Section 2.4: Problem 17 Solution