# 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.