Expressive adequacy

Question

After reading a few others posts on this site, I am still struggling in showing how sets are incomplete.

(a) Show that {$↔,\bot, ∧$} is functionally complete, but that no proper subset is.

(b) is solved! :)

(b) Assume that $c$ is a 2-place connective. Show that if either $f_c(\top, \top) = \top$ or $f_c(\bot, \bot) = \bot$, then {$c$} is not complete.

For (b), I understand that for {$\uparrow$} and {$\downarrow$}, the only functionally complete 2-place connectives, that $f_{\uparrow}(\top, \top) = \bot$ and $f_{\uparrow}(\bot, \bot) = \top$. The same results apply for $f_{\downarrow}$. I just can't see how to then apply this to prove $f_c(\top, \top) = \top$ means {$c$} is incomplete.

Answer 1

As Noah points out in the comments, you know that $c$ cannot be either the $\uparrow$ and $\downarrow$, and since those are the only two connectives that are by themselves complete, you know $c$ is not complete.

However, I doubt that this proof is 'acceptable', or at least probably not what was expected of you. Probably you had to give a more direct proof why such a $c$ is not complete. Well, think about it. Suppose you have any number of connectives $c$, applied to any number of instances of $\top$, e.g. $(\top c \top) c (\top c (\top c \top))$ ... if you evaluate this, you'll of course get $\top$ for any expression; you';ll never get $\bot$.

Now, to make that idea into a rigorous proof, use induction: prove by (strong) induction on the number of operators $c$ in any statement $\phi$ that is composed of $c$'s and $\top$, that $\phi$ will always evaluate to $\top$. I'll leave the details to you.

Answer 2

For (a), to prove that a set of connectives is functionally complete, an "induction on formulas" should be done by demonstrating that the other known connectives in the logic can be derived using our given set. In our case, the other connectives to be derived are $\{\vee,\top,\rightarrow,\neg\}$ or just $\{\vee, \top, \neg\}$ because $\rightarrow$ can be derived already using $\vee$ and $\neg$ $(p\rightarrow q=\neg p\vee q)$.

The formula $\neg p$ can be derived using $p\leftrightarrow\bot$ because when $p$ is $\top$, "$p\leftrightarrow\bot$" gives $\top\leftrightarrow\bot=\bot$ and when $p$ is $\bot$, "$p\leftrightarrow\bot$" gives $\bot\leftrightarrow\bot=\top$.

It's now obvious that $\top$ can be derived using $\bot\rightarrow\bot$.

Finally, $p\vee q$ can also be derived from $\{\leftrightarrow,\bot,\wedge\}$. Hint: De Morgan's Theorem.