Say that a set \(\Sigma_1\) of wffs is equivalent to a set \(\Sigma_2\) of wffs iff for any wff \(\alpha\), we have that \(\Sigma_1\vDash\alpha\) iff \(\Sigma_2\vDash\alpha\). A set \(\Sigma\) is independent iff no member of \(\Sigma\) is tautologically implied by the remaining members in \(\Sigma\). Show that the follow hold

Part (a)

Claim: A finite set of wffs has an independent equivalent subset

To prove this, I will need to use the following lemma.

Lemma 1: If \(\Sigma=\{\sigma_1,\ldots,\sigma_n\}\not\vDash\tau\), then neither does \(\Sigma'=\{\sigma_1,\ldots,\sigma_{n-1}\}\).

Proof of lemma: Let \(v\) be a truth assignment which satisfies \(\Sigma\) but for which \(\overline{v}(\tau)=F\). Then \(v\) also satisfies \(\Sigma'\), but \(\overline{v}(\tau)=F\) so that \(\Sigma'\not\vDash\tau\).

Now I am ready to prove the original claim:

Let there be a finite set of wffs \(\Sigma_0 = \{\sigma_1,\ldots,\sigma_n\}\). Now, define \(\Sigma_{k+1}\subseteq\Sigma_k\) by \begin{gather}\Sigma_{k+1} = \begin{cases}\Sigma_k\setminus{\sigma_{k+1}} \quad\text{ if } \Sigma_k\setminus{\sigma_{k+1}}\vDash\sigma_{k+1}\ \Sigma_k\quad\quad\quad\quad\quad\text{otherwise}\end{cases}\end{gather} So we have the following chain \begin{gather}\Sigma_n\subseteq\cdots\subseteq\Sigma_{k+1}\subseteq\Sigma_k\subseteq\cdots\subseteq\Sigma_1\subseteq\Sigma_0\end{gather} I first show that \(\Sigma_n\) is independent. Suppose \(\sigma_{k+1}\in\Sigma_n\subseteq\Sigma_{k+1}\) for some \(k = 0,\ldots, n -1\), then \(\Sigma_k\setminus\{\sigma_{k+1}\}\not\vDash\sigma_k\) by our construction. Since \(\Sigma_n\setminus\{\sigma_{k+1}\}\subseteq \Sigma_k\setminus\{\sigma_{k+1}\}\), we have that \(\Sigma_n\setminus\{\sigma_{k+1}\}\not\vDash\sigma_k\) (by lemma1 ). Therefore, \(\Sigma_n\) is independent.

All that is left to show is that \(\Sigma_n\) is equivalent to \(\Sigma_0\). To show this, I will need to invoke the following lemma.

Lemma 2: Let \(\Sigma_n\subseteq\Sigma_0\) be as constructed above, and suppose that \(v\) is a truth assignment which satifies \(\Sigma_{k+1}\) for \(k = 0,\ldots,n-1\), then \(v\) also satisfies \(\Sigma_k\).

Proof of lemma 2: Let \(v\) be such a truth assignment satisfying \(\Sigma_{k+1}\) Recall that \(\Sigma_{k+1}\) is defined by \begin{gather}\Sigma_{k+1} = \begin{cases}\Sigma_k\setminus{\sigma_{k+1}} \quad\text{ if } \Sigma_k\setminus{\sigma_{k+1}}\vDash\sigma_{k+1}\ \Sigma_k\quad\quad\quad\quad\quad\text{otherwise}\end{cases}\end{gather} Obviously if \(\Sigma_{k+1}=\Sigma_k\) then \(v\) satisfies \(\Sigma_k\). Assume the other case, that is \(\Sigma_{k+1} = \Sigma_k\setminus\{\sigma_{k+1}\}\vDash\sigma_{k+1}\). Then \(v\) satisfies \(\sigma_{k+1}\). Thus, \(v\) satisfies \(\Sigma_k\setminus\{\sigma_{k+1}\}\cup\{\sigma_{k+1}\} = \Sigma_k\).

Now, we are in good shape to show that \(\Sigma_n\) is equivalent to \(\Sigma_0\).

First, let \(\alpha\) be a wff such that \(\Sigma_n\vDash\alpha\). Now, let \(v\) be a truth assignment which satisfies \(\Sigma_0\). Since \(\Sigma_n\subseteq\Sigma_0\), \(v\) also satisfies \(\Sigma_n\). Thus, \(\overline{v}(\alpha) = T\), so that \(\Sigma_0\vDash\alpha\).

On the other hand, suppose \(\alpha\) is a wff such that \(\Sigma_0\vDash\alpha\), and let \(v\) be a truth assignment which satisfies \(\Sigma_n\). By applying Lemma 2 repeatedly, we must also have that \(v\) satisfies \(\Sigma_0\), and thus \(\overline{v}(\alpha)=T\). Thus, \(\Sigma_n\vDash\alpha\).

Since \(\Sigma_n\vDash\alpha\) iff \(\Sigma_0\vDash\alpha\), the two sets are equivalent.

Therefore, \(\Sigma_n\subseteq\Sigma_0\) is the independent equivalent subset desired.

Part (b)

Claim: An infinite set need not have an independent equivalent subset

To show this, consider the following example. Let \(\Sigma = \{\alpha_1,\alpha_2,\alpha_3,\ldots\}\) where \(\alpha_1 = A_1\), \(\alpha_2 = (A_1\land A_2)\), and in general \(\alpha_{k+1} = (\alpha_{k}\land A_{k+1})\), so that \(\Sigma = \{A_1,(A_1\land A_2),((A_1\land A_2)\land A_3),\ldots\}\).

Suppose, for contradiction, that \(S\subseteq\Sigma\) is independent and equivalent. It must be that \(S\neq\varnothing\) since \(\varnothing\) is not equivalent to \(\Sigma\). This is true since \(\Sigma\vDash A_1\to A_2\), but \(\varnothing\not\vDash A_1\to A_2\).

Now, I will show that \(\lvert S\rvert = 1\). Suppose otherwise, that \(\alpha_i,\alpha_j\in S\) where \(i<j\). Then \(\alpha_j\vDash\alpha_i\), so that \(S\) is not an independent set of wffs. Thus, \(\lvert S\rvert = 1\). So \(S = \{\alpha_k\}\) for some \(k\in\mathbb{N}\). It’s obvious that \(\Sigma \vDash \alpha_{k+1}\), so we should have that \(S\vDash\alpha_{k+1}\). Let \(v\) be a truth assignment so that \(v(A_1) = v(A_2) = \cdots = v(A_k) = T\) and \(v(A_{k+1})= F\). Then \(v\) satisfies \(S = \{\alpha_k\}\), but \(\overline{v}(\alpha_{k+1}) = F\) showing that \(S\not\vDash\alpha_{k+1}\), a contradiction.

Therefore, \(\Sigma\) does not have an independent equivalent subset.

Part (c)

Let \(\Sigma = \{\sigma_0,\sigma_1,\ldots\}\); show that there is an independent equivalent set \(\Sigma'\).

I have not finished this one yet…