# Section 2.5: Problem 7 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
The completeness theorem tells us that each sentence either has a deduction (from $\emptyset$ ) or has a counter-model (i.e., a structure in which it is false). For each of the following sentences, either show there is a deduction or give a counter-model.
(a) $\forall x(Qx\rightarrow\forall yQy)$
(b) $(\exists xPx\rightarrow\forall yQy)\rightarrow\forall z(Pz\rightarrow Qz)$
(c) $\forall z(Pz\rightarrow Qz)\rightarrow(\exists xPx\rightarrow\forall yQy)$
(d) $\neg\exists y\forall x(Pxy↔\neg Pxx)$
(a) This sentence is not valid. Let $\mathfrak{A}=(\{0,1\};Q)$ where $Q^{\mathfrak{A}}=\{<1>\}$ . Then, for any $s:V\rightarrow|\mathfrak{A}|$ , $\not\vDash_{\mathfrak{A}}Qx[s(x|0)]$ and $\vDash_{\mathfrak{A}}Qx[s(x|1)]$ , therefore, $\not\vDash_{\mathfrak{A}}\forall yQy[s]$ , $\not\vDash_{\mathfrak{A}}Qx\rightarrow\forall yQy[s(x|1)]$ , and $\not\vDash_{\mathfrak{A}}\forall x(Qx\rightarrow\forall yQy)[s]$ .
(b) This sentence is valid. We need to show that $\vdash(\exists xPx\rightarrow\forall yQy)\rightarrow\forall z(Pz\rightarrow Qz)$ . By the deduction and generalization theorems, it is sufficient to show that $\exists xPx\rightarrow\forall yQy;Pz\vdash Qz$ . By axiom group 2, MP and contraposition, it is sufficient to show that $Pz;\neg\forall yQy\vdash\neg(\exists xPx\rightarrow\forall yQy)$ . By MP and contraposition rules, using the axiom of group 2 $\vdash\forall x\neg Px\rightarrow\neg Pz$ , we have $Pz\vdash\exists xPx$ . And, using the axiom of group 1 $\vdash\exists xPx\rightarrow\neg\forall yQy\rightarrow\neg(\exists xPx\rightarrow\forall yQy)$ and MP, we have $Pz;\neg\forall yQy\vdash\neg(\exists xPx\rightarrow\forall yQy)$ .
(c) This sentence is not valid. The example of a structure in which it is false is the same as in (a) where $P^{\mathfrak{A}}=Q^{\mathfrak{A}}$ . For any $s:V\rightarrow|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}Pz\rightarrow Qz[s]$ , $\vDash_{\mathfrak{A}}\neg Px[s(x|0)]$ , $\not\vDash_{\mathfrak{A}}\neg Px[s(x|1)]$ , $\not\vDash_{\mathfrak{A}}Qx[s(x|0)]$ and $\vDash_{\mathfrak{A}}Qx[s(x|1)]$ , therefore, $\vDash_{\mathfrak{A}}\forall z(Pz\rightarrow Qz)[s]$ , $\not\vDash_{\mathfrak{A}}\forall x\neg Px[s]$ , $\vDash_{\mathfrak{A}}\exists xPx[s]$ , $\not\vDash_{\mathfrak{A}}\forall yQy[s]$ , $\not\vDash_{\mathfrak{A}}\exists xPx\rightarrow\forall yQy[s]$ , and $\not\vDash_{\mathfrak{A}}\forall z(Pz\rightarrow Qz)\rightarrow(\exists xPx\rightarrow\forall yQy)[s]$ .
(d) This sentence is valid. We need to show that $\vdash\neg\exists y\forall x(Pxy↔\neg Pxx)$ , or, equivalently, $\vdash\forall y\neg\forall x\neg((Pxy\rightarrow\neg Pxx)\rightarrow\neg(\neg Pxx\rightarrow Pxy))$ (here we use the following definition of $\leftrightarrow$ : $\alpha\leftrightarrow\beta$ means $\neg((\alpha\rightarrow\beta)\rightarrow\neg(\beta\rightarrow\alpha))$ ). By the generalization theorem, it is sufficient to show that $\vdash\neg\forall x\neg((Pxy\rightarrow\neg Pxx)\rightarrow\neg(\neg Pxx\rightarrow Pxy))$ which we denote as $\vdash\neg\forall x\neg\gamma$ . For this, it is sufficient to show that $\vdash\gamma_{t}^{x}$ where $t$ is a term substitutable for $x$ in $\gamma$ . Indeed, by axiom group 2, $\vdash\forall x\neg\gamma\rightarrow\neg\gamma_{t}^{x}$ , and, using MP and contraposition, we have $\gamma_{t}^{x}\vdash\neg\forall x\neg\gamma$ . Now, $y$ is substitutable for $x$ in $\gamma$ , and $\gamma_{y}^{x}$ is simply $(Pyy\rightarrow\neg Pyy)\rightarrow\neg(\neg Pyy\rightarrow Pyy)$ , a tautology.