Section 1.5: Problem 6 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Show that is complete but that no proper subset is complete.
Note that is tautologically equivalent to , so that is tautologically equivalent to . Together with we have a complete system of connectives.
Now, in the previous exercises we have already listed some properties of connectives such that the set of wffs satisfying each such property is closed under connectives, but not all connectives satisfy the property, in particular, and do not. To show that no proper subset is complete, for each connective in the set we need to find such property that all the other connectives satisfy it, but not the given one. In other words, there should be something unique in each connective that makes the set complete.
is the only connective that does not satisfy the property of Exercise 5. In other words, without it every wff using connectives only satisfies the property of Exercise 5. Or, put it differently, we have already shown in Exercise 5 that even a larger set of connectives than is not complete.
is the only connective that is not evaluated to when both operands are evaluated to .
Similarly, is the only connective that is not evaluated to when both operands are evaluated to .
Note that neither nor satisfies any of these properties, but in each case the set of wffs satisfying these properties is closed under respective connectives (can be shown by induction similar to previous exercises).
Another interesting thing to note is that and are two opposite connectives in the sense that each is the negation of the other. Hence, if we add to the set, then we would be able to remove either one from the set, as it would be possible to express it via and the other one. But in fact, we would not need both, as is complete. Therefore, the set in some sense plays the role of in the complete set of connectives, where neither connective symbol can be removed (so neither one can play the role of alone), but both are not needed once is added.