# 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 $\Gamma$ of formulas can be extended to a consistent set $\Delta$ having the property that for any formula $\alpha$ , either $\alpha\in\Delta$ or $(\neg\alpha)\in\Delta$ . (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 $\Delta\supseteq\Gamma$ 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 $\Delta$ , and, hence, in $\Gamma$ . Without using the theorem itself, we could follow the logic of its proof here as well.
Step 1.$\Gamma\cup\Lambda$ is consistent. Indeed, by definition, $\Gamma\cup\Lambda\vdash\{\phi,\neg\phi\}$ iff $\Gamma\vdash\{\phi,\neg\phi\}$ . Note, that here we don’t use any facts about $\Lambda$ itself. Namely, if $\Lambda$ 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 $\Lambda$ is consistent.
Step 2. We construct $\Delta$ . If we assume that the language is countable, we can effectively enumerate all formulas, $\phi_{1},\phi_{2},\ldots$ . Then, let $\Gamma_{0}=\Gamma\cup\Lambda$ , and for each $i\ge1$ , we construct $\Gamma_{i}=\Gamma_{i-1};\alpha$ , where $\alpha$ is either $\phi_{i}$ or $\neg\phi_{i}$ depending on which one keeps $\Gamma_{i}$ consistent (if both, we just add $\phi_{i}$ ). We then take $\Delta=\cup_{i\ge0}\Gamma_{i}$ .
Step 3. We need to verify that $\Delta$ is well-defined, i.e. that we can always construct $\Gamma_{i}$ . This would not be possible only if both $\Gamma_{i-1};\phi_{i}$ and $\Gamma_{i-1};\neg\phi_{i}$ were inconsistent, but then, by RAA, $\Gamma_{i-1}\vdash\neg\phi_{i}$ and $\Gamma_{i-1}\vdash\phi_{i}$ , implying that $\Gamma_{i-1}$ is inconsistent. So, by induction, we can show that, since $\Gamma_{0}=\Gamma\cup\Lambda$ is consistent, for every $i\ge1$ , $\Gamma_{i}$ can be constructed and $\Gamma_{i}$ is consistent (by its definition).
Step 4. We verify that $\Delta$ satisfies the conditions. It is clear that a) $\Gamma\subseteq\Gamma_{0}\subseteq\Delta$ , and b) for every wff $\alpha$ , exactly one of $\alpha\in\Delta$ and $\neg\alpha\in\Delta$ holds. Indeed, at least one of them should hold, as if $\alpha=\phi_{i}$ then $\Gamma_{i}$ , and, hence, $\Delta$ , contains at least one of $\alpha$ and $\neg\alpha$ , but they both cannot be in $\Delta$ , as this would imply that they are both in some finite $\Gamma_{i}$ contradicting its consistency. Similarly, we can argue that every finite subset of $\Delta$ is consistent.
We now only need to address consistency of $\Delta$ . We show that $\alpha\in\Delta$ iff $\Delta\vdash\alpha$ . From this, it follows that $\Delta$ is consistent (if , then the finite inconsistent set $\{\gamma,\neg\gamma\}\subseteq\Delta$ ). If $\alpha\in\Delta$ then the deduction $<\alpha>$ from $\Delta$ proves $\alpha$ . Now, suppose that $\Delta\vdash\alpha$ . We show by induction that $\alpha\in\Delta$ . Indeed, if $\alpha\in\Delta$ or $\alpha\in\Lambda\subseteq\Delta$ then $\alpha\in\Delta$ . Now, by induction, if $\alpha$ is derived from $\beta$ and $\beta\rightarrow\alpha$ where $\beta,\beta\rightarrow\alpha\in\Delta$ , then, since $\{\neg\alpha,\beta,\beta\rightarrow\alpha\}$ is inconsistent ($<\beta,\beta\rightarrow\alpha,\alpha>$ and $<\neg\alpha>$ ), it cannot be a finite subset of $\Delta$ , but $\{\beta,\beta\rightarrow\alpha\}\subseteq\Delta$ , therefore, not $\neg\alpha$ but $\alpha$ is in $\Delta$ .