# Section 1.5: Problem 3 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 $\{\neg,\#\}$ is not complete.
Just to remind, $\#$ is the majority connective so that $\#ABC$ is tautologically equivalent to $(A\wedge B)\vee(A\wedge C)\vee(B\wedge C)$ . If the set $\mathcal{C}=\{\neg,\#\}$ is not complete, then one cannot represent all binary connectives using just these connective symbols, in particular, one cannot represent either $\downarrow$ or $\vert$ , as otherwise the set would be complete. There are two ways to show that these connectors can’t be expressed using $\mathcal{C}$ .
First, consider any wff using just two sentence symbols $A$ and $B$ and connective symbols from $\mathcal{C}$ only (we do not have to consider any wffs using more sentence symbols in their construction, as we try to represent a binary connective $A\square B$ , and all other sentence symbols can be ignored, according to Exercise 4, Section 1.1). Looking at the construction tree from the bottom up, let us find all nodes that use only negation below them. Then, each such node has a wff that is tautologically equivalent to one of the four wffs: $A$ , $B$ , $\neg A$ and $\neg B$ (for example, $\neg\neg A$ is tautologically equivalent to the first one etc.). Now, consider the first node that uses $\#$ . If two children of $\#$ are tautologically equivalent to the same wff, then the result of $\#$ by the majority rule is also tautologically equivalent to the same wff. If all three operands of $\#$ are different, then two of them are tautologically equivalent to either $A$ and $\neg A$ , or $B$ and $\neg B$ . In either case, for any truth assignment, the values of these two operands are opposite, meaning that the third operand decides the value of $\#$ . Again, we have that $\#$ is tautologically equivalent to one of its operands. Hence, the $\#$ node is equivalent to one of its children, i.e. one of the four wffs listed above. We conclude that every wff that has two sentence symbols and connective symbols from $\mathcal{C}$ only, is tautologically equivalent to $A$ , $B$ , $\neg A$ or $\neg B$ . More formally, we could have proved this by induction. It is true for sentence symbols. Now, if it is true for $\alpha$ , $\beta$ and $\gamma$ , then it is true for $\neg\alpha$ and $(\#\alpha\beta\gamma)$ by the argument outlined above.
Second, we may note that both $\downarrow$ and $\vert$ are such that $T\square F=F\square T$ . In particular, this implies that $\alpha\square\beta$ is not tautologically equivalent to $\neg(\neg\alpha\square\neg\beta)$ . In other words, neither $\downarrow$ nor $\vert$ satisfies the property that “if we change all truth values assigned to sentence symbols to their opposites, the result will change to the opposite as well”. However, both $\neg$ and $\#$ satisfy this property. Moreover, by induction, we see that, since all sentence symbols satisfy this property, and if $\alpha$ , $\beta$ and $\gamma$ satisfy this property, so do $\neg\alpha$ and $\#\alpha\beta\gamma$ , any wff based on $\mathcal{C}$ only satisfies the property. Hence, using connective symbols from $\mathcal{C}$ only, no wff can represent $\downarrow$ or $\vert$ (or any other connective that does not satisfy the property, for example, $\bot$ , $\top$ , $\wedge$ , $\vee$ , $\rightarrow$ , $\leftrightarrow$ , $\leftarrow$ , $+$ , $<$ and $>$ ).