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).