« Section 2.4: Problem 11 Solution

Section 2.4: Problem 13 Solution »

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 .