This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say that two sets of wffs are equivalent iff they have the same consequences. Say that a set of wffs is independent iff no member of the set is tautologically implied by the remaining members. Those exercises then ask us to show that every finite set of wffs has an independent equivalent subset (among other things, but my question is about this part). I thought about a proof, but I'm not entirely sure it goes through. The idea is roughly this (I'll be sketchy):
Let $\Sigma$ be a finite set of wffs. Let $\Delta$ be the set of wffs of $\Sigma$ which are implied by the others. Take $\Gamma = \Sigma – \Delta$. It'd seem that $\Gamma$ is the desired subset; if it's not empty, it's not difficult to show that it is independent and equivalent to $\Sigma$.
My only problem is that I can't seem to guarantee that $\Gamma \not = \varnothing$, which seems to be necessary for the proof to go through (unless $\Sigma$ itself is empty, in which case there's nothing to prove). Any thoughts?
Best Answer
That doesn't quite work. For example, if $\Sigma=\{q,p,\neg \neg p\}$, then each of the two latter wffs follow from the other, and $\Gamma=\{q\}$, which is certainly not equivalent to $\Sigma$.
Instead of trying to remove all the superfluous wffs at once, try removing one at a time. As long as $\Sigma$ is not independent, select one wff that is implied by the others, and remove that. Then continue working with the new reduced $\Sigma$. Can you show that this process will terminate eventually, and that the resulting set is equivalent to the original one?
Bonus exercise: Demonstrate that the assumption that $\Sigma$ is finite is necessary, by finding an infinite set of wffs that has no independent equivalent subset.