Section 1.7: 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
Show that whenever
, then there exists a deduction from
, the last component of which is
. Remark: This result is called “completeness”; the concepts in Exercises 5–7 will reappear in Section 2.4.
Using the Corollary 17A, if
, then there is a finite
such that
. We start the deduction by listing all wffs
,
. Then, suppose that
and
are already listed in the deduction, then we can add the tautology
, then, using rule (c),
, and, using it again,
. This way we can add
, then
etc. Finally, we have
which is satisfied by a truth assignment
iff
is satisfied by
. Hence,
is a tautology which can be further added, followed by
(using again (c)).