Section 1.7: Problem 12 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
For each of the following conditions, give an example of an unsatisfiable set
of formulas that meets the condition.
(a) Each member of
is — by itself — satisfiable.
(b) For any two members
and
of
, the set
is satisfiable.
(c) For any three members
,
, and
of
, the set
is satisfiable.
(a)
.
(b)
.
(c)
.
What is the point of this exercise? Suppose we were to continue the sequence of such examples, and for every
we would find an unsatisfiable set
of wffs such that every its subset of size
is satisfiable. Then, every subset of
of size
is also satisfiable, and
can be used as an example of a set
for every
. For instance, in (a), (b) and (c), instead of providing three different sets of wffs, we could have just used the same set
. Now, the question is, then, whether we can provide just one infinite set
of wffs that would work as an example of a set
for any
. The compactness theorem says, No!