« Section 2.4: Problem 17 Solution

# Section 2.4: Problem 18-A 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
(Additional) For each formula $\phi$ , define $\phi^{*}$ to be the result of erasing all quantifiers and terms (leaving the predicate symbols and connectives), and replacing $=$ by $\top$ . For example, if $\phi$ is $(\forall xPx\rightarrow(Pgy\vee x=y))$ then $\phi^{*}$ is $(P\rightarrow(P\vee\top))$ .
(a) Show that for each logical axiom $\alpha$ in $\Lambda$ , the formula $\alpha^{*}$ is a tautology of sentential logic.
(b) Show that for any formula $\phi$ that is deducible (from the empty set), $\phi^{*}$ is a tautology of sentential logic.
(c) Show that not possible for both a formula and its negation to be deducible (from the empty set).
Remark. This additional exercise is to show that the deductive calculus is consistent (even before we have the soundness theorem of Section 2.5).
(a) Every atomic formula becomes a predicate symbol. Hence, a generalization of every tautology of group 1 axioms becomes a tautology of sentential logic (moreover, in general, it becomes a specific case of the initial tautology, for example, $Px\rightarrow Py\rightarrow Px$ becomes $P\rightarrow P\rightarrow P$ ). For other axiom groups, a generalization of $\forall x\alpha\rightarrow\alpha_{t}^{x}$ becomes $\alpha^{*}\rightarrow\alpha^{*}$ , a generalization of $\forall x(\alpha\rightarrow\beta)\rightarrow(\forall x\alpha\rightarrow\forall x\beta)$ becomes $(\alpha^{*}\rightarrow\beta^{*})\rightarrow(\alpha^{*}\rightarrow\beta^{*})$ , a generalization of $\alpha\rightarrow\forall x\alpha$ becomes $\alpha^{*}\rightarrow\alpha^{*}$ , a generalization of $x=x$ becomes $\top$ , and a generalization of $x=y\rightarrow\alpha\rightarrow\alpha'$ becomes $\top\rightarrow\alpha^{*}\rightarrow\alpha^{*}$ .
(b) We can show this by induction. For a logical axiom $\phi$ we have already shown that $\phi^{*}$ is a tautology in (a). If $\beta$ is deduced from $\alpha$ and $\alpha\rightarrow\beta$ where $\alpha^{*}$ and $(\alpha\rightarrow\beta)^{*}$ are tautologies, then, since $(\alpha\rightarrow\beta)^{*}$ is $\alpha^{*}\rightarrow\beta^{*}$ , $\beta^{*}$ is a tautology as well.
(c) $(\neg\alpha)^{*}=\neg\alpha^{*}$ implies, by (b), that at least one of $\alpha$ and $\neg\alpha$ is not deducible (from the empty set).