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.