Section 1.7: Problem 1 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
Assume that every finite subset of
is satisfiable. Show that the same is true of at least one of the sets
and
. (This is part of the proof of the compactness theorem.) Suggestion: If not, then
and
are unsatisfiable for some finite
and
. Look at
.
As suggested, if
and
are finite and not satisfiable (finite unsatisfiable subsets of
must include
as
itself is finitely satisfiable), then we consider
.
is a finite subset of
, hence, there is a truth assignment
that satisfies it. Now, either
and
satisfies
, and, hence,
, or
, and, hence,
satisfies
, and, hence,
. Therefore, at least one of
and
is satisfiable. Contradiction.
Note, that this is not true that exactly one of
and
is finitely satisfiable. For example,
or even
, and
.