Logic – How to Prove a Set of Sentential Connectives is Incomplete

boolean-algebralogic

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.

Best Answer

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

Related Question