# 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 $\{\wedge,\leftrightarrow,+\}$ is complete but that no proper subset is complete.
Note that $A+A$ is tautologically equivalent to $\bot$ , so that $A\leftrightarrow(A+A)$ is tautologically equivalent to $\neg A$ . Together with $\wedge$ 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, $\downarrow$ and $\vert$ 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.
$\wedge$ is the only connective that does not satisfy the property of Exercise 5. In other words, without it every wff using $\{\leftrightarrow,+\}$ 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 $\{\leftrightarrow,+\}$ is not complete.
$\leftrightarrow$ is the only connective that is not evaluated to $F$ when both operands are evaluated to $F$ .
Similarly, $+$ is the only connective that is not evaluated to $T$ when both operands are evaluated to $T$ .
Note that neither $\downarrow$ nor $\vert$ 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 $\leftrightarrow$ and $+$ are two opposite connectives in the sense that each is the negation of the other. Hence, if we add $\neg$ to the set, then we would be able to remove either one from the set, as it would be possible to express it via $\neg$ and the other one. But in fact, we would not need both, as $\{\wedge,\neg\}$ is complete. Therefore, the set $\{\leftrightarrow,+\}$ in some sense plays the role of $\neg$ in the complete set of connectives, where neither connective symbol can be removed (so neither one can play the role of $\neg$ alone), but both are not needed once $\neg$ is added.