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 , define to be the result of erasing all quantifiers and terms (leaving the predicate symbols and connectives), and replacing by . For example, if is then is .
(a) Show that for each logical axiom in , the formula is a tautology of sentential logic.
(b) Show that for any formula that is deducible (from the empty set), 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, becomes ). For other axiom groups, a generalization of becomes , a generalization of becomes , a generalization of becomes , a generalization of becomes , and a generalization of becomes .
(b) We can show this by induction. For a logical axiom we have already shown that is a tautology in (a). If is deduced from and where and are tautologies, then, since is , is a tautology as well.
(c) implies, by (b), that at least one of and is not deducible (from the empty set).