Section 1.7: 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
Let be a set of wffs such that (i) every finite subset of is satisfiable, and (ii) for every wff , either or . Define the truth assignment : for each sentence symbol . Show that for every wff , iff . (This is part of the proof of the compactness theorem.) Suggestion: Use induction on .
The statement is true for all sentence symbols, as for a sentence symbol , either or is in , and iff . Now, suppose it is true for any two wffs and (that is, the evaluation of each one is or , depending on whether it or its negation is in , respectively). Then, iff , hence, iff iff , and, according to (ii), iff . Now, for , let be if (iff ) and otherwise (iff ). Note, that iff , i.e. and . Similarly we define . Then, , where means either or its negation depending on which one is in (according to (ii), one of them is in ), is a finite subset of , therefore, by (i), it must be satisfiable. Now, for every truth assignment , is uniquely determined by and which are uniquely determined by and . In particular, every truth assignment that satisfies must satisfy , because if one such truth assignment satisfy it, so do all others (again, is uniquely determined by and ). Since satisfies both and , it must satisfy , i.e. if , or if , in which case . So, iff . By the induction principle, we conclude that for every wff , iff .