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