# Section 2.4: Problem 15 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) $\exists x\alpha\vee\exists x\beta\leftrightarrow\exists x(\alpha\vee\beta)$ .
(b) $\forall x\alpha\vee\forall x\beta\rightarrow\forall x(\alpha\vee\beta)$ .
Note, that $\gamma\vee\delta$ is tautologically equivalent to $\neg\gamma\rightarrow\delta$ , and $\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 proves of the above equations (for example, you cannot use tautologies to substitute subformulas of quantified formulas), but rather that these connectives are defined this way.
(a) We need to show that and . By deduction and contraposition theorems, it is sufficient to show that and .
For the first one it is sufficient to show that $\forall x\neg(\neg\alpha\rightarrow\beta)\vdash\forall x\neg\alpha$ and $\forall x\neg(\neg\alpha\rightarrow\beta)\vdash\forall x\neg\beta$ (using Rule T for $\gamma,\delta\vDash\neg(\gamma\rightarrow\neg\delta)$ ). By MP, it is sufficient to show that and $\vdash\forall x\neg(\neg\alpha\rightarrow\beta)\rightarrow\forall x\neg\beta$ , and, by axiom group 3, MP and generalization theorem, it is sufficient to show that and $\vdash\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\beta$ . Both are tautologies.
For the second one, by the generalization and contraposition theorems, it is sufficient to show that $\neg\alpha\rightarrow\beta\vdash\forall x\neg\alpha\rightarrow\neg\forall x\neg\beta$ . By the deduction theorem, it is sufficient to show that $\forall x\neg\alpha;\neg\alpha\rightarrow\beta\vdash\neg\forall x\neg\beta$ . By RAA, it is sufficient to conclude that $\{\forall x\neg\alpha,\neg\alpha\rightarrow\beta,\forall x\neg\beta\}$ is inconsistent. Now, by axiom group 2, $\vdash\forall x\neg\alpha\rightarrow\neg\alpha$ and $\vdash\forall x\neg\beta\rightarrow\neg\beta$ , and, by MP, $\{\forall x\neg\alpha,\neg\alpha\rightarrow\beta,\forall x\neg\beta\}\vdash\{\beta,\neg\beta\}$ .
(b) We need to show that $\vdash(\neg\forall x\alpha\rightarrow\forall x\beta)\rightarrow\forall x(\neg\alpha\rightarrow\beta)$ . By deduction, generalization and contraposition theorems, it is sufficient to show that $\neg(\neg\alpha\rightarrow\beta)\vdash\neg(\neg\forall x\alpha\rightarrow\forall x\beta)$ . For this, it is sufficient to show that $\neg(\neg\alpha\rightarrow\beta)\vdash\neg\forall x\alpha$ and $\neg(\neg\alpha\rightarrow\beta)\vdash\neg\forall x\beta$ (using Rule T for $\gamma,\neg\delta\vDash\neg(\gamma\rightarrow\delta)$ ), or that both $\{\neg(\neg\alpha\rightarrow\beta),\forall x\alpha\}$ and $\{\neg(\neg\alpha\rightarrow\beta),\forall x\beta\}$ are inconsistent. By axiom group 2, $\vdash\forall x\alpha\rightarrow\alpha$ and $\vdash\forall x\beta\rightarrow\beta$ , and $\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\alpha$ and $\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\beta$ are tautologies, so that, by Rule T, $\{\neg(\neg\alpha\rightarrow\beta),\forall x\alpha\}\vdash\{\alpha,\neg\alpha\}$ and $\{\neg(\neg\alpha\rightarrow\beta),\forall x\beta\}\vdash\{\beta,\neg\beta\}$ .