# Section 2.4: 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

Show that any consistent set
of formulas can be extended to a consistent set
having the property that for any formula
, either
or
. (Assume that the language is countable. Do not use the compactness theorem of sentential logic.)

The proof of the Compactness Theorem of sentential logic (CTSL) was in two parts. First, a set
was constructed that for every wff would include either the wff or its negation. Second, a truth assignment was constructed that would satisfy all the wffs in
, and, hence, in
. Without using the theorem itself, we could follow the logic of its proof here as well.

Step 1.
is consistent. Indeed, by definition,
iff
. Note, that here we don’t use any facts about
itself. Namely, if
itself were inconsistent, it would simply mean that there does not exist any consistent set of wffs, but if we assume that a consistent set of wffs exists, this would automatically, by definition, imply that
is consistent.

Step 2. We construct
. If we assume that the language is countable, we can effectively enumerate all formulas,
. Then, let
, and for each
, we construct
, where
is either
or
depending on which one keeps
consistent (if both, we just add
). We then take
.

Step 3. We need to verify that
is well-defined, i.e. that we can always construct
. This would not be possible only if both
and
were inconsistent, but then, by RAA,
and
, implying that
is inconsistent. So, by induction, we can show that, since
is consistent, for every
,
can be constructed and
is consistent (by its definition).

Step 4. We verify that
satisfies the conditions. It is clear that a)
, and b) for every wff
, exactly one of
and
holds. Indeed, at least one of them should hold, as if
then
, and, hence,
, contains at least one of
and
, but they both cannot be in
, as this would imply that they are both in some finite
contradicting its consistency. Similarly, we can argue that every finite subset of
is consistent.

We now only need to address consistency of
. We show that
iff
. From this, it follows that
is consistent (if
, then the finite inconsistent set
). If
then the deduction
from
proves
. Now, suppose that
. We show by induction that
. Indeed, if
or
then
. Now, by induction, if
is derived from
and
where
, then, since
is inconsistent (
and
), it cannot be a finite subset of
, but
, therefore, not
but
is in
.