For any set of formulas in propositional logic, there is an equivalent and independent set 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.
 A: 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.
A: 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.
