Part (a)

Problem

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.

Solution

Let \(S\) be the set of wffs for which \(\overline{v}_1\) and \(\overline{v}_2\) agree. Since \(\overline{v}_i\) is an extension of \(v_i\), and since \(v_1(A_k) = v_2(A_k)\) for all sentence symbols \(A_k\) in \(\alpha\), all the sentence symbols in \(\alpha\) are contained in \(S\). Consider \(\beta\) and \(\gamma\) some wffs in \(S\).

Notice that, by the rules established for the extensions \(\overline{v}_i\), we must have that \begin{gather}\overline{v}_1((\lnot\beta)) = \begin{cases} T & \text{if} & \overline{v}_1(\beta) = F \ F & \text{if} & \overline{v}_1(\beta) = T\end{cases}\end{gather} and similarly, \begin{gather}\overline{v}_2((\lnot\beta)) = \begin{cases} T & \text{if} & \overline{v}_2(\beta) = F \ F & \text{if} & \overline{v}_2(\beta) = T\end{cases}\end{gather} But since \(\overline{v}_1(\beta) = \overline{v}_2(\beta)\), these functions must coincide so that \(\overline{v}_1((\lnot\beta)) = \overline{v}_2((\lnot\beta))\) Thus, \((\lnot\beta)\in S\).

By the same process and logic, we also have that \((\beta\square\gamma)\in S\) where \(\square\) is one of \(\land,\lor,\to,\leftrightarrow\), so that \(S\) is closed under the sentence building operations. By the induction principle, \(S\) contains all wffs made from the sentence symbols in \(\alpha\). Namely, \(S\) contains \(\alpha\), so that \(\overline{v}_1(\alpha)=\overline{v}_2(\alpha)\).

Part (b)

Problem

Let \(S\) be a set of sentence symbols that includes those in \(\Sigma\) and \(\tau\) (and possibly more). Show that \(\Sigma\vDash\tau\) if and only if every truth assignment for \(S\) which satisfies every member of \(\Sigma\) also satisfies \(\tau\).

Solution

First, let \(S'\) denote the set of sentence symbols that appear in \(\Sigma\) and \(\tau\), and no more. So \(S'\subseteq S\).

”\(\Rightarrow\)” For the forwards direction, we assume that \(\Sigma\vDash\tau\). Now, let \(v\) be a truth assignment for \(S\) which satisfies every member of \(\Sigma\). The domain of \(v\) can be restricted to \(S'\subseteq S\), call this new assignment \(v_0\). Since \(v_0\) still satisfies every member of \(\Sigma\) and \(\Sigma\vDash\tau\), we have that \(v_0\) satisfies \(\tau\). Now since \(v\) and \(v_0\) agree on all the sentence symbols in \(\tau\), by part (a) we have that \(\overline{v}(\tau)=\overline{v}_0(\tau)= T\). Thus, \(v\) satisfies \(\tau\).

”\(\Leftarrow\)” Now I prove the backwards direction. Let \(v\) be a truth assignment for \(S'\) which satisfies \(\Sigma\). Extend the domain of \(v\), calling the new assignment \(v'\), to take on all the symbols of \(S\) by the following: \begin{gather}v’(A) = \begin{cases} v(A) & \text{if} & A\in \Sigma\cup{\tau} \ T & \text{otherwise} & \end{cases}\end{gather} Notice that since \(v'\) and \(v\) agree on all sentence symbols in \(\Sigma\), \(\overline{v}'\) and \(\overline{v}\) agree on every member of \(\Sigma\) (by part (a)). Since \(v\) satisfies \(\Sigma\). By our assumption \(v'\) must also satisfies \(\tau\). Since \(v\) and \(v'\) agree on all sentence symbols in \(\tau\), we must have that \(\overline{v}(\tau)=\overline{v}'(\tau) = T\) (by part (a)). Since \(v\) was an arbitrary truth assignment, we have that \(\Sigma\vDash\tau\).