# How to prove a set of sentential connectives is incomplete?

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton（2ed),

Show that $\{\lnot, \# \}$ is not complete.

A set of connective symbols is complete, if every function $G : \{F, T\}^n \to \{F, T\}$for $n > 1$ can be realized by a wff(well-formed formula) using only the connective symbols from it. A known fact is the set $\{\lnot, \land \}$ is complete.

$\#$ is a three-place sentential connective. For three arbitary wffs, $A$, $B$ and $C$, $\#ABC$ is tautologically equilvalent to: $$(A\land B)\lor(A\land C)\lor(B\land C)$$

Here's how far I understand:

The problem can be reduced to showing, given two wffs $A$ and $B$, there is nothing tautologically equivalent to $A \land B$ by using $\lnot$ and $\#$. For simplicity, assume $A$ and $B$ are not generated by any other wffs and there exist a finite number of wffs $\{ C_i:i \leq n\}$which are not generated by other wffs either.

If the tautogocial equilvalent of $A \land B$ exists, I can't exclude the occurence of $C_i$.

I'm also trying to use induction, but I got stuck when $C_i$s are involved.

• I just corrected my answer; please check it, I had to add one more conector to deal with negations. Dec 21, 2012 at 6:33

Peter Smith’s approach is probably the best way to think about such problems in general. In this case there’s another fairly simple approach. Notice first that the connective $$\#$$ is symmetric in its three arguments: if $$XYZ$$ is any permutation of $$ABC$$, $$\#ABC$$ is equivalent to $$\#XYZ$$. From this it’s easy to see that all combinations of exactly two sentence letters $$A$$ and $$B$$ with $$\#$$ are equivalent either to $$\#AAB$$ or to $$\#ABB$$. Moreover, $$\#AAB$$ is equivalent simply to $$A$$, and $$\#ABB$$ to $$B$$; this suggests trying to show that as long as we work with at most two sentence letters, $$\#$$ essentially does nothing.

Claim: Every wff that can be constructed from the sentence letters $$A$$ and $$B$$ and the connectives $$\neg$$ and $$\#$$ is equivalent to one of $$A,B,\neg A$$, and $$\neg B$$.

Proof: The claim is easily proved by induction on the complexity of the wff. It’s certainly true for wffs with no connective: they are simply $$A$$ and $$B$$. Suppose that $$\varphi$$ has at least one connective. Then $$\varphi$$ is either $$\neg\psi$$ for some wff $$\psi$$, or $$\#\psi_0\psi_1\psi_2$$ for wffs $$\psi_0,\psi_1$$, and $$\psi_2$$. Suppose that $$\varphi=\neg\psi$$. The induction hypothesis ensures that $$\psi$$ is equivalent to one of $$A,B,\neg A$$, and $$\neg B$$, and $$\varphi$$ is therefore equivalent to one of $$\neg A,\neg B,A$$, and $$B$$, respectively.

Now suppose that $$\varphi=\#\psi_0\psi_1\psi_2$$. Again the induction hypothesis ensures that each of $$\psi_0,\psi_1$$, and $$\psi_2$$ is equivalent to one of $$A,B,\neg A$$, and $$\neg B$$. Any set of three chosen from $$\{A,B,\neg A,\neg B\}$$ necessarily contains either two copies of one of the four wffs or a wff and its negation, so $$\varphi$$ is equivalent to $$\#XXY$$ or $$\#X\neg XY$$ for some $$X,Y\in\{A,B,\neg A,\neg B\}$$. But $$\#XXY$$ is equivalent to $$X$$, and $$\#X\neg XY$$ is equivalent to $$Y$$, so in every case $$\varphi$$ is equivalent to one of $$A,B,\neg A$$, and $$\neg B$$. The claim now follows by induction. $$\dashv$$

Since $$A\land B$$ is not equivalent to $$A,B,\neg A$$, or $$\neg B$$, $$\{\neg,\#\}$$ is not complete.

(I’ve implicitly used the fact that if $$\psi_0,\psi_1$$, and $$\psi_2$$ are equivalent to $$\psi_0',\psi_1'$$, and $$\psi_2'$$, respectively, then $$\#\psi_0\psi_1\psi_2$$ is equivalent to $$\#\psi_0'\psi_1'\psi_2'$$. This is clear from consideration of the relevant truth tables.)

• This has the clear advantage over Peter Smith's approach that it actually works! Dec 21, 2012 at 14:25
• @Henning: I have to admit that I didn’t read the details of his answer; I was thinking just of the idea of using an invariant. Dec 21, 2012 at 14:27
• Yep, dunce's corner for me. Sorry about that carelessness and thanks to @HenningMakholm for the obvious objection! Dec 22, 2012 at 14:05

It sufficies to prove the case $n=2$.

Let $G_1,G_2,G_3,G_4:\{C_0,C_1\}\rightarrow\{T,F\}$ be given by $G_1(C_0)=T=G_1(C_1)$, $G_2(C_0)=T,G_2(C_1)=F$, $G_3(C_0)=F,G_3(C_1)=T$ and $G_4(C_0)=F=G_4(C_1).$

$(1)$ Let us prove by induction on formulas constructed over $\{C_0,C_1\}$ in the language $\{¬,\#,@\}$ that there is no formula equivalent to $C_0\wedge C_1$ or $¬(C_0\wedge C_1)$, where $$@ABC=(A\vee B)\wedge(A\vee C)\wedge(B\vee C).$$

You have to show that for any formulas $A,B,C$, $\#ABC$ and $@ABC$ are equivalent; (hint: $\#ABC$ is true if and only if at least two elements of $A,B,C$ are true, and the same holds for $@ABC$)

This clearly holds for atomic formulas.

Let us assume that $A,B,C$ are formulas such that the condition $(1)$ holds. Then $(1)$ holds for $¬A$. $(2)$

Suppose $\#ABC$ is equivalent to $C_0\wedge C_1$, then $G_1(\#ABC)=T$, so we may assume with no loss of generality that $G_1(A)=T$; because of the form of $\#ABC$. Also $G_i(\#ABC)=F$ for $i=2,3,4$, then by the form of $\#ABC$ it follows that $G_i(A)=F$ for $i=2,3,4$, which implies $A$ is equivalent to $C_0\wedge C_1$, contradicting the inductive hypothesis, thus $(1)$ holds for $\#ABC$.$(3)$

If $\#ABC$ was equivalent to $¬(C_0\wedge C_1)$, $@¬A¬B¬C$ would be equivalent to $C_0\wedge C_1$, then $\#¬A¬B¬C$ would be equivalent to $C_0\wedge C_1$, contradicting $(2)$ and $(3)$.

Since $\#ABC$ and $@ABC$ are equivalent, this finishes the proof.

• Overkill perhaps? ;-) Dec 21, 2012 at 8:28
• I can't understand how to determine the truth value of $G_i(X)$, when $X \notin \{ C_0, C_1\}$. Take $G_2$ as an example, is it true that iff $C_0 \vDash X$, $G_2(X)=T$? Thus I don't understand why $G_2$ assigns at least one of $A$, $B$ and $C$, to $T$. Dec 21, 2012 at 21:40
• The value of $G$ is extended to other formulas by induction on formulas, perhaps this clarifies your doubts little bit personal.kent.edu/~rmuhamma/Philosophy/Logic/Deduction/… Dec 21, 2012 at 22:51
• So you mean $A$, $B$, $C$ are soly generated by $C_0$ and $C_1$? What if $A$, $B$, $C$ are also generated by other wffs which are not generated by $C_0$ and $C_1$? Dec 21, 2012 at 23:11
• yes, for if $\{¬,\#\}$ was complete, there would be a formula $A$ whose only propositions are $C_0$ and $C_1$ such that $A$ is equivalent to $C_0\wedge C_1$ Dec 21, 2012 at 23:16

In pp.12-13 of A Concise Introduction to Mathematical Logic, by W. Rautenberg, the author points out that $\{\lnot, \# \}$ defines precisely the class of self-dual boolean functions. Thus, in this particular case it would easily follow that no non-self-dual operator (such as any essentially binary boolean operator) is definable from $\lnot$ and $\#$ alone.

• I have removed the peripheral question in this answer. Please consider asking this as a question of your own. Dec 24, 2012 at 22:43