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. .