For any set of formulas in propositional logic, there is an equivalent and independent set

Question

A set of formulas is independent if no proper subset is logically equivalent to it.

Note that this exercise appears in Enderton 1.2 10(c) and is marked as star.

Answer 1

For an infinite $S$ we cannot stick to getting an equivalent and independent subset of $S$. An example that shows this is $$ \begin{align} S =\{ & A_1 ,\\ & A_1 \land A_2 ,\\ & A_1 \land A_2 \land A_3 ,\\ & A_1 \land A_2 \land A_3 \land A_4 , \ldots \} \end{align} $$ for propositional variables $A_i$. No set that contains two of these formulas is independent, and on the other hand, no singleton implies everything here.

However, let's enumerate the original set $S=\{\varphi_0,\varphi_1,\ldots,\varphi_n,\ldots\}$ (this is possible because there are only countably many possible wffs), and then consider $$ \begin{align} T_0 =\{ & \varphi_0 ,\\ & \varphi_0 \to \varphi_1 ,\\ & (\varphi_0\land\varphi_1)\to\varphi_2 ,\\ & (\varphi_0\land\varphi_1\land\varphi_2)\to\varphi_3 , \ldots \} \end{align} $$ and let $T$ consist of those formulas in $T_0$ that are not tautologies.

Clearly $S$ implies $T_0$ and vice versa, and $T_0$ is equivalent to $T$, so $T$ is equivalent to $S$. We must show that $T$ is independent.

Let $\psi_n \equiv (\varphi_0\land\cdots\land\varphi_{n-1})\to\varphi_n$ be an arbitrary element of $T$. We will show that $\psi_n$ is not implied by the other formulas in $T$.

By construction $\psi_n$ was not a tautology, so there is some valuation that makes it false. This is only possible if the valuation makes $\varphi_0$ upto $\varphi_{n-1}$ true (which makes all of the earlier $\psi$s true) and $\varphi_n$ false (which makes all of the later $\psi$s true). So this valuation is a witness that $$ T\setminus\{\psi_n\}\cup\{\neg\psi_n\} $$ is consistent, or in other words that $\psi_n$ is not implied by the rest of $T$, Q.E.D.

Answer 2

The proof for any finite set of formulas is easy enough:

Assume set of formulas $S$ is not itself an independent set (if it is, then clearly $S$ meets the condition of the theorem since $S$ is obviously equivalent to itself). Let the number of formulas in $S$ be $n_0$.

Since $S$ is not an independent set, there is some proper subset $T_1 \subset S$ which is logically equivalent to $S$. If $T_1$ is independent, then $T_1$ demonstrates that $S$ meets the condition of the formula. Let $n_1$ be the number of formulas in $T_1$.

If $T_1$ is not independent, then again there is some proper subset $T_2 \subset T_1 \subset S$ which is logically equivalent to $T_1$. Since $T_2 \subset S$, if $T_2$ is independent, then $T_2$ demonstrates that $S$ meets the condition of the formula. If not, let $n_2$ be the number of formulas in $T_2$. Since $T_2$ is a proper subset, $n_2 < n_1$.

This reasoning repeats for any non-empty $T_i$. So if $S$ does not meet the condition of the theorem, the sequence $\left\{ n_i \right\}$ is a sequence of decreasing non-negative integers of arbitrary length, starting from the finite $n_0$. Such a sequence does not exist, so $S$ meets the condition of the theorem.

The problem is much more difficult if we allow for infinte sets of formulas.