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

Prove Theorem 33C, stating that true (in
) quantifier-free sentences are theorems of
. (See the outline given there.)

First, let
be an atomic sentence. Then,
or
where
and
are variable-free terms. But then, according to Lemma 33B, there are
and
such that
and
. Further,
iff
and
iff
(by S1 and S2), and, using this, by Lemma 33A,
iff
and
iff
. Using these facts, we can show that
iff
and
iff
, and
iff
and
iff
. For example, for
,
and
(deduction axiom group 6, DA6), and using DA2, we can deduce
and
, and, similarly for
and
.

Second, let
be a sentence of the form
or
true in
, where
is such that
iff
is true in
, and
iff
is false in
. We show that the same applies to
. Indeed, if
is true in
, then, respectively,
is false in
, and
is false or
is true in
, implying
, and
, i.e.
, otherwise
is true in
, and
is true,
is false in
, implying
, and
, i.e.
.