Section 1.7: Problem 2 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
Let
be a set of wffs such that (i) every finite subset of
is satisfiable, and (ii) for every wff
, either
or
. Define the truth assignment
:
for each sentence symbol
. Show that for every wff
,
iff
. (This is part of the proof of the compactness theorem.) Suggestion: Use induction on
.
The statement is true for all sentence symbols, as for a sentence symbol
, either
or
is in
, and
iff
. Now, suppose it is true for any two wffs
and
(that is, the evaluation of each one is
or
, depending on whether it or its negation is in
, respectively). Then,
iff
, hence,
iff
iff
, and, according to (ii),
iff
. Now, for
, let
be
if
(iff
) and
otherwise (iff
). Note, that
iff
, i.e.
and
. Similarly we define
. Then,
, where
means either
or its negation depending on which one is in
(according to (ii), one of them is in
), is a finite subset of
, therefore, by (i), it must be satisfiable. Now, for every truth assignment
,
is uniquely determined by
and
which are uniquely determined by
and
. In particular, every truth assignment that satisfies
must satisfy
, because if one such truth assignment satisfy it, so do all others (again,
is uniquely determined by
and
). Since
satisfies both
and
, it must satisfy
, i.e.
if
, or
if
, in which case
. So,
iff
. By the induction principle, we conclude that for every wff
,
iff
.