3

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?

Nagase
  • 5,467

1 Answers1

3

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.

hmakholm left over Monica
  • 286,031
  • I'm thinking about how to proceed with this (thanks for the counter-example, btw). Given that $\Sigma$ is finite, should I proceed by induction on the size of $\Sigma$ or is there a more direct way of doing it? – Nagase Mar 23 '14 at 02:40
  • @Nagase: Induction sounds good if you want to be formal. – hmakholm left over Monica Mar 23 '14 at 02:43
  • Hmm, maybe it's not necessary. Let $\Sigma$ be a finite set of wffs which is not independent. Let $\sigma \in \Sigma$ be a wff which is implied by some other in the set. Define $\Gamma = \Sigma - {\sigma}$. If $\Gamma$ is independent, we're done. If not, keep taking out wffs from $\Sigma$. The process must come to a halt, as we will eventually reach $\Sigma' = {\phi}$ (i.e. a singleton), which is obviously independent. So the whole reasoning reduces to showing that, at each step, the result set $\Gamma$ is equivalent to $\Sigma$, which shouldn't be too difficult. Right? – Nagase Mar 23 '14 at 03:00
  • @Nagase: Yes, exactly. The formal basis for that kind of reasoning is induction in the size of $\Sigma$, but usually it is not necessary to mention the magic word "induction" when writing it down informally -- what you have written there is quite sufficient to communicate the argument. – hmakholm left over Monica Mar 23 '14 at 11:18
  • 1
    @Nagase: However, it is not true that a singleton is necessarily independent. If $\phi$ is a tautology, then it follows from nothing, and ${\phi}$ is then not independent. (Just like ${0}$ is not a linearly independent set of vectors). – hmakholm left over Monica Mar 23 '14 at 11:20
  • Yes, you're right. I was led astray by my own informal translation of the notion of independence. If $\phi$ is a tautology, and $\Sigma = {\phi}$, then $\Sigma - {\phi} = \varnothing$, but $\varnothing \models \phi$, so $\Sigma$ is not independent after all. Does that mean that I need to rule out the case in which $\phi$ is a tautology in my proof? – Nagase Mar 23 '14 at 21:50
  • @Nagase: I don't see any reason why tautologies would need to be special-cased in the proof. Where do you think special-casing is necessary? – hmakholm left over Monica Mar 23 '14 at 22:14
  • Hmm, I thought that there could be a problem if we ended up with $\Sigma'= {\phi}$, with $\phi$ as a tautology. But I thought a little more about it and, if that's the case, well, we remove $\phi$ from $\Sigma'$ as well. $\varnothing$ is (vacuously) an independent subset of $\Sigma$, and, if $\phi$ is a tautology, then it is equivalent to ${\phi}$. – Nagase Mar 23 '14 at 22:30