Section 1.2: Problem 6 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

(a) Show that if $v_{1}$ and $v_{2}$ are truth assignments which agree on all the sentence symbols in the wff $\alpha$ , then $\overline{v}_{1}(\alpha)=\overline{v}_{2}(\alpha)$ . Use the induction principle.

(b) Let $S$ be a set of sentence symbols that includes those in $\Sigma$ and $\tau$ (and possibly more). Show that $\Sigma\vDash\tau$ iff every truth assignment for $S$ which satisfies every member of $\Sigma$ also satisfies $\tau$ . (This is an easy consequence of part (a). The point of part (b) is that we do not need to worry about getting the domain of a truth assignment exactly perfect, as long as it is big enough. For example, one option would be always to use truth assignments on the set of all sentence symbols. The drawback is that these are infinite objects, and there are a great many — uncountably many — of them.)

(a) Let $S$ be the set of all sentence symbols, which includes sentence symbols found in $\alpha$ . Further, let $S'$ be the set of all symbols in $\alpha,$ $S'\subseteq S$ , and let $B\subseteq\overline{S}$ be the set of all wffs $\gamma$ for which $\overline{v}_{1}(\gamma)=\overline{v}_{2}(\gamma)$ holds. Then, by assumption, $S'\subseteq B$ . Further, if $B$ contains $\gamma$ and $\beta$ then $\overline{v}_{1}(\gamma)=\overline{v}_{2}(\gamma)$ and $\overline{v}_{1}(\beta)=\overline{v}_{2}(\beta)$ , and for $i=1,2$ , $\overline{v}_{i}((\neg\gamma))$ and $\overline{v}_{i}(\gamma\square\beta)$ are calculated according to the truth tables, that is they are identical, and $(\neg\gamma),(\gamma\square\beta)\in B$ . Using the induction principle, $B=\overline{S'}$ , and $\alpha\in B$ .

(b) Let $S'\subseteq S$ be the set of sentence symbols used in $\Sigma$ and $\tau$ . $\Sigma\vDash\tau$ iff for every truth assignment $v$ on $S'$ such that for every wff $\beta\in\Sigma$ , $\overline{v}(\beta)=T$ , $\overline{v}(\tau)=T$ iff (using (a)) for every truth assignment $v$ on $S$ such that for every wff $\beta\in\Sigma$ , $\overline{v}(\beta)=T$ , $\overline{v}(\tau)=T$ iff every truth assignment for $S$ which satisfies every member of $\Sigma$ also satisfies $\tau$ .

Subpages

Section 1.2: Problem 6 Solution

Section 1.2: Problem 6 Solution