(a) We can show it either by removing dependent wffs from the set, or by induction. Let us use the induction principle. If $\Sigma=\emptyset$ then it is vacuosly independent (indeed, it does not contain any formula, not to say the one that would be tautologically implied by the others) and equivalent to itself. A more interesting case to consider is when $\Sigma=\{\alpha\}$ , i.e. it has one formula only. If $\alpha$ is not a tautology, then $\Sigma$ is independent and equivalent to itself. Now, if $\alpha$ is a tautology, then the empty subset of $\Sigma$ is independent. For any wff $\beta$ , $\emptyset\vDash\beta$ iff for any truth assignment $v$ , $\overline{v}(\beta)=T$ iff for any truth assignment $v$ , $\overline{v}(\alpha)=\overline{v}(\beta)=T$ iff for any truth assignment such that $\overline{v}(\alpha)=T$ , $\overline{v}(\beta)=T$ (this “such that” does not actually restrict the choice of $v$ ) iff $\Sigma\vDash\beta$ . That is, $\emptyset$ is equivalent to $\Sigma$ . The induction step. Assume that we have $n>1$ wffs in $\Sigma$ and that for all lower numbers of wffs in $\Sigma$ we have already shown the existence of an independent equivalent subset. If all wffs in $\Sigma$ are not tautologically implied by the others, then $\Sigma$ is independent and equivalent to itself. Suppose, now, that $\alpha\in\Sigma$ is tautologically implied by $\Sigma-\alpha$ . Then, by assumption, there is an independent subset $\Sigma'$ of $\Sigma-\alpha$ which is equivalent to $\Sigma-\alpha$ . We need to show that it is also equivalent to $\Sigma$ . For a wff $\beta$ , $\Sigma'\vDash\beta$ iff $\Sigma-\alpha\vDash\beta$ iff for any truth assignment $v$ that satisfies $\Sigma-\alpha$ , $\overline{v}(\beta)=T$ iff for any truth assignment $v$ that satisfies $\Sigma$ , $\overline{v}(\beta)=T$ (again, by saying this, we do not restrict the choice of $v$ , as $v$ satisfies $\Sigma-\alpha$ iff it satisfies $\Sigma$ ) iff $\Sigma\vDash\beta$ .

The fact that we repeatedly used here is that if $\Sigma\vDash\alpha$ , then $\Sigma\vDash\beta$ iff $\Sigma;\alpha\vDash\beta$ . The other solution we indicated uses this fact to show that by removing dependent formulas one by one we still have a subset which is equivalent to the initial set.

(b) Remark: Whether we prove (a) by induction, as we did, or by removing dependent formulas one by one, the proof would not work in the infinite case. The induction principle shows a statement for finite numbers (I am not talking about the generalized induction principle, which is not applicable in this case), and the second method would leave us with an infinite subset after each step.

Of course, we could have tried to generalize the statement at the end of (a) to the following, if $\Sigma'\vDash\Sigma''$ then $\Sigma'\vDash\beta$ iff $\Sigma';\Sigma''\vDash\beta$ , and then consider the subset $\Sigma''$ of all dependent wffs in $\Sigma$ , and take $\Sigma'=\Sigma-\Sigma''$ . This is something that we did for the case where there is one formula in $\Sigma$ only. In general, however, there are at least two problems with this. First, there might be wffs in $\Sigma''$ that are dependent on each other. For example, if there are two tautologically equivalent wffs in $\Sigma$ , then both will be included to $\Sigma''$ leaving nothing tautologically implying either one in $\Sigma'$ . But even if we take special care of this case, there is a more general problem. It might happen, that there is an infinite sequence of wffs in $\Sigma$ such that each wff in the sequence is dependent on the following, leaving us with no subset (finite or infinite) that would be independent and that would tautologically imply the rest.

The simplest example, I can think of, is when $\Sigma=\{\alpha_{1},\alpha_{2},\ldots\}$ , where $\alpha_{1}=A_{1}$ , and $\alpha_{n}=(\alpha_{n-1}\wedge A_{n})$ . Each $\alpha_{n}$ is tautologically implied by $\alpha_{n+1}$ (and any $\alpha_{k}$ for $k>n$ ). At the same time, the only independent subsets of $\Sigma$ are the empty set and $\Sigma_{n}=\{\alpha_{n}\}$ . The empty subset does not tautologically imply any $\alpha_{n}$ , while $\Sigma_{n}$ does not tautologically imply $\alpha_{n+1}$ . And, of course, it is clear that if $\Sigma_{1}$ and $\Sigma_{2}$ are equivalent, then each tautologically implies any formula in the other one.

(c) Here we consider the infinite case, the finite case is covered in (a). However, now we don’t have the subset restriction. Therefore, we may combine $\sigma_{k}$ ’s to form new formulas. So, suppose we have $\Sigma'=\{\alpha_{1},\alpha_{2},\ldots\}$ which is equivalent to $\Sigma$ and independent. The fact that it is equivalent to $\Sigma$ implies that all $\alpha_{n}$ ’s are true iff all $\sigma_{k}$ ’s are true. The independence means that for any $n$ there should be a truth assignment $v_{n}$ such that $\overline{v}_{n}(\alpha_{n})=F$ while $\overline{v}_{n}(\alpha_{m})=T$ for all $m\neq n$ .

Looking at the example in (b), we note that $\Sigma$ is satisfied by one truth assignment only, namely, the one that sets all sentence symbol values to $T$ . This suggests, that as $\Sigma'$ we could have simply consider $\{A_{1},A_{2},\ldots\}$ . However, there are too many ways to obtain the sequence $\{A_{1},A_{2},\ldots\}$ from the initial one, so it by itself does not provide a further clue.

But let us try something similar. First, for each formula $\alpha_{n}$ we want to ensure that it is not tautologically implied by the others, this means that there should be a truth assignment $v_{n}$ such that $\overline{v}_{n}(\alpha_{n})=F$ while all other $\overline{v}_{n}(\alpha_{m})=T$ . This is necessary and sufficient to show the independence of $\Sigma'$ . Second, to show the equivalence of $\Sigma$ and $\Sigma'$ , we need to ensure that all wffs in $\Sigma'$ are evaluated to $T$ iff all wffs in $\Sigma$ are evaluated to $T$ . Let us try to make the first requirement stronger, that is, for every truth assignment $v$ such that $\overline{v}(\alpha_{n})=F$ , we require $\overline{v}(\alpha_{m})=T$ for $m\neq n$ . Note, that this is equivalent to the requirement that whenever $\overline{v}(\alpha_{n})=F$ , $\overline{v}(\alpha_{m})=T$ for all $m>n$ . Indeed, in this case, if we assume that two formulas are evaluated to $F$ , then one index should be larger than the other one, meaning that the corresponding formula should have been evaluated to $T$ . Of course, this, by itself, is not enough to ensure that $\Sigma'$ is independent, as we would further have to assume that for every $n$ there is at least one truth assignment $v_{n}$ such that $\overline{v}_{n}(\alpha_{n})=F$ . Given this new requirement, for equivalence, we require that if all wffs in $\Sigma$ are evaluated to $T$ , then all wffs in $\Sigma'$ are evaluated to $T$ , but if there is at least one wff in $\Sigma$ that is evaluated to $F$ , then there is exactly one wff in $\Sigma'$ that is evaluated to $F$ . To pick which one is evaluated to $F$ , we may try to require that it is the one with the minimum index $n$ such that $\sigma_{n}$ is evaluated to $F$ .

To sum up, given wffs $\sigma_{n}\in\Sigma$ , we want to construct a sequence $\alpha_{n}$ such that the condition (*) holds: given any truth assignment $v$ , $\overline{v}(\alpha_{n})=F$ if and only if $\overline{v}(\sigma_{n})=F$ and $\overline{v}(\sigma_{m})=T$ for all $m<n$ . It is easy to see that this requirement is sufficient to guarantee the equivalence of $\Sigma'$ and $\Sigma$ and independence of $\Sigma'$ , as long as for each $n$ there is at least one truth assignment $v$ such that $n=\inf\{m|\overline{v}(\sigma_{m})=F\}$ . We will get to this latter condition later. Given the condition (*), $\alpha_{1}$ is evaluated to $F$ iff $\sigma_{1}$ is evaluated to $F$ , i.e. we can try to take $\alpha_{1}=\sigma_{1}$ . Next, $\alpha_{2}$ is evaluated to $F$ iff $\sigma_{2}$ is evaluated to $F$ and $\sigma_{1}$ is evaluated to $T$ , i.e. we take $\alpha_{2}=(\sigma_{1}\rightarrow\sigma_{2})$ . Next, $\alpha_{3}$ is evaluated to $F$ iff $\sigma_{3}$ is evaluated to $F$ and both $\sigma_{1}$ and $\sigma_{2}$ are evaluated to $T$ , i.e. we take $\alpha_{3}=((\sigma_{1}\wedge\sigma_{2})\rightarrow\sigma_{3})$ . Continuing this way, we conclude that our approach leads to $\alpha_{n}=((((\sigma_{1}\wedge\sigma_{2})\wedge\ldots)\wedge\sigma_{n-1})\rightarrow\sigma_{n})$ . Note that for any assignment $v$ , $\overline{v}(\alpha_{n})=F$ iff $\overline{v}((((\sigma_{1}\wedge\sigma_{2})\wedge\ldots)\wedge\sigma_{n-1}))=T$ and $\overline{v}(\sigma_{n})=F$ iff $\overline{v}(\sigma_{m})=T$ for $m<n$ , and $\overline{v}(\sigma_{n})=F$ iff the condition (*) holds. This by itself guarantees the equivalence of $\Sigma$ and $\Sigma'$ . As was noted above, we need something more to guarantee the independence of $\Sigma'$ . The problem is that $\alpha_{n}$ might never be evaluated to $F$ , meaning that whenever all previous $\alpha_{m}$ ’s are true, $\alpha_{n}$ is true as well. The problem here may come from two different issues. First, it could be the case that $\sigma_{n}$ is tautological. Second, it could be the case that whenever $\sigma_{n}$ is false, for some $k<n$ , $\sigma_{k}$ is false. Overall, we do not have to consider each different case separately. Indeed, we just note that in this case $\alpha_{n}$ (as constructed) is tautological. Further, for any set of wffs $\Sigma$ and any set $C$ of tautologies, $\Sigma$ is tautologically equivalent to $\Sigma;C$ ($\Sigma;C\vDash\beta$ iff $\Sigma\vDash(C\rightarrow\beta)$ , similar to Exercise 4(a), where $C\rightarrow\beta$ is $F$ iff all wffs in $C$ are $T$ and $\beta$ is $F$ , iff $\Sigma\rightarrow\beta$ , since $C$ is a tautology). Now, we can simply exclude all tautologies $\alpha_{n}\in\Sigma'$ . Note, that in this case a) there is at least one truth assignment $v$ such that $\overline{v}(\alpha_{n})=F$ , and, hence, for $m\neq n$ , $\overline{v}(\alpha_{m})=T$ , b) if all $\sigma_{n}$ ’s are $T$ then all $\alpha_{n}$ ’s are $T$ , c) if $n$ is the least index such that $\sigma_{n}$ is $F$ , then the initial $\alpha_{n}$ is not a tautology, hence, not excluded, and is evaluated to $F$ . Therefore, we have independence and equivalence.

Two special cases to consider, just for fun. First, the example of (b). After obvious transformations we get $\alpha_{n}=(((A_{1}\wedge\ldots)\wedge A_{n-1})\rightarrow((A_{1}\wedge\ldots)\wedge A_{n}))$ , which takes the form of $(A\rightarrow(A\wedge A_{n}))$ and is evaluated to $F$ iff $A$ is evaluated to $T$ while $(A\wedge A_{n})$ is evaluated to $F$ , implying that $\alpha_{n}$ is just tautologically equivalent to $(((\neg A_{1}\vee\ldots)\vee\neg A_{n-1})\vee A_{n})$ , something different from what we came up in (b) using different reasoning. Note, that unlike our solution in (b), here, if one formula is false, then all others are true. Second, suppose that there is $\sigma_{n}$ such that no truth assignment satisfies it. Then, for every $m>n$ , $\alpha_{m}$ is a tautology, i.e. excluded. Hence, we may assume that $n$ is the lowest index with the property. Since $\sigma_{n}$ is never satisfied, by itself, it tautologically implies any other formula (p. 23), moreover, due to this, $\Sigma$ also tautologically implies any other formula, hence, one way to obtain an equivalent independent set of wffs is to just take one formula $\Sigma'=\{\sigma_{n}\}$ . $\Sigma'$ is independent, as $\sigma_{n}$ is not tautologically implied by the empty set, and it is equivalent to $\Sigma$ as both tautologically imply any formula. Note, that in this case $\Sigma'\subseteq\Sigma$ . However, our method may produce a more complicated system of equations. For example, suppose that $\sigma_{1}$ is not a tautology and is satisfied by at least some truth assignments, and $\sigma_{2}=(A_{1}\wedge(\neg A_{1}))$ . As we noted, we can just consider $\Sigma'=\{\sigma_{2}\}$ , in which case $\Sigma'\subset\Sigma$ . However, according to our more general method, all $\alpha_{n}$ ’s are removed from $\Sigma'$ for $n>2$ , and $\alpha_{1}=\sigma_{1}$ , $\alpha_{2}=\sigma_{1}\rightarrow\sigma_{2}$ . Since $\sigma_{2}$ is not satisfied by any truth assignments, $\alpha_{2}$ is tautologically equivalent to $(\neg\sigma_{1})$ . That is, essentially, we obtain an equivalent set of wffs $\{\sigma_{1},(\neg\sigma_{1})\}$ , which is, as $\Sigma$ , not satisfied by any truth assignments (hence, tautologically implies any formula, and is equivalent to $\Sigma$ ), and independent, since we assumed that $\sigma_{1}$ is not a tautology and is satisfied by at least one truth assignment. Note that $\Sigma'\not\subseteq\Sigma$ (assuming that $\alpha_{2}\notin\Sigma$ ).