proof of functional completeness of logical operators

If I know that the set of operators {∨, & , ¬} is functionally complete, how do I go about proving/disproving the functional completeness of the following set of operators?

a) $\{\vee,\neg\}$

b) $\{\to,\neg\}$

c) $\{\to\}$

I have looked at the answer here for (b) : Prove that the set {→, ¬} is functionally complete


a)

$\{\vee, \neg\}$ is functionally complete. You only have to show that $\wedge$ (alias $\&$) is definable from $\{\vee, \neg\}$, because then you can express all the connectives of the complete set $\{\vee, \wedge, \neg\}$ (and the functions they induce). Like so: $$ p \wedge q \colon = \neg (\neg p \vee \neg q) $$

b)

$\{\to, \neg\}$ is functionally complete. By a), it suffices to show that $\vee$ is definable from $\{\to, \neg\}$. Thus: $$ p \vee q \colon = (\neg p \to q) $$

c)

$\{\to \}$ is not functionally complete. The proof is by induction on the complexity of propositional formulas in two variables. Let $2 = \{0,1\}$ be the set of truth values. We show that the always-false function $$F_{false} \colon (u,v) \mapsto 0 \colon 2 \times 2 \to 2$$ is not definable. Let $$ \begin{align} F_{\to} &\colon (u, v) \mapsto (\text{$1$ if $u\le v$ else $0$}) \colon 2 \times 2 \to 2 \\ \end{align} $$ $F_{\to}$ is just the truth table for implication "$\to$".

For any propositional formula $A = A(p,q)$ in variables $p, q$, we define the function $f_A \colon 2 \times 2 \to 2$ corresponding to A, inductively:

$$ \begin{align} f_p(u, v) &= u \tag{$pr_1$} \\ f_q(u, v) &= v \tag{$pr_1$} \\ f_{B\to C}(u,v) &= F_{\to}(f_B(u,v), f_C(u,v)) \tag{$Rule_{\to}$} \end{align} $$

Induction on formulas

Atomic formulas are $p$ and $q$. Clearly, neither $f_p$ nor $f_q$ is always false ($0$).

Now suppose $A$ is $B \to C$ with $B, C$ of lesser complexity (height, length). By induction hypothesis, neither $f_B$ nor $f_C$ is always false. Suppose $f_{B \to C}$ is always false: $$f_{B \to C}(u,v) = 0 \;\;\text{for all $u, v$.}$$ By ($Rule_{\to}$), this means: $$F_{\to}(f_B(u,v), f_C(u,v)) = 0 \;\;\text{for all $u, v$.}$$ By the definition of $F_{\to}$, this can only be so when $$ \begin{align} f_B(u,v) &= 1 \;\;\text{for all $u, v$, and} \tag{i} \\ f_C(u,v) &= 0 \;\;\text{for all $u, v$.} \tag{ii} \\ \end{align} $$ But by induction hypothesis, (ii) cannot be.


Here is a proof that $\{ \rightarrow \}$ is not complete:

We'll show by structural induction that for any expression $\phi(p,q)$ that is composed of any number of instances of variables $p$ and $q$, and any number of $\rightarrow$ connectives: $\phi(T,T)=T$.

Base: $\phi(p,q) = p$ and $\phi(p,q) = q$. In both cases we have $\phi(T,T)=T$

Step: Suppose $\phi(p,q) = \phi_1(p,q) \rightarrow \phi_2(p,q)$ and that (inductive hypothesis) $\phi_1(T,T)=T$ and $\phi_2(T,T)=T$. Then $\phi(T,T) = \phi_1(T,T) \rightarrow \phi_2(T,T) = T \rightarrow T = T$

We have proven that for no such expression $\phi(T,T)=F$, and hence $\{ \rightarrow \}$ is not complete.