By induction prove $ P(n) := $ "$ B \rightarrow \varphi_{n}(B,\rightarrow)$"

Question

Define $\varphi_{n}(B,\rightarrow)$ to be the statement form comprised of only the particular statement $B$ and connectives $\rightarrow$ such that $B$ occurs exactly $n$ times.

So I'm actually trying to show that the set of connectives {$\rightarrow$} is functionally incomplete. I reckon I could single out the statement form $\lnot B \land B$ and assume there does exist some $\varphi_{k}(B,\rightarrow)$ and $\varphi_{i}(B,\rightarrow)$ such that $$\lnot B \land B \iff \varphi_{k}(B,\rightarrow)\rightarrow \varphi_{i}(B,\rightarrow)$$

Using this induction lemma to demonstrate a contradiction. Demonstrating it is not possible to find a statement form hence showing {${\rightarrow}$} is not functionally complete.

So I started on it but as you may see in the proof below, the highlighted region raises concerns since that equivalence just simply doesn't hold in general.

Wondering if someone could help me out with pointers, and moreover, if there is a better way to show this set of connectives is functionally incomplete.

Answer 1

If your goal is to prove that $\{\to\}$ is not functionally complete, there is a very simple way to show this in two steps.

(Notation: $\top$ stands for the truth value "true", while $\bot$ stands for the truth value "false".)

First, prove the following lemma:

For every formula $A$ built up using only the connective $\to$, if $v$ is a valuation such that $v(p_i) = \top$ for all propositional variables $p_i$ occurring in $A$, then $v(A) = \top$

Proof. By induction on the number $n$ of occurrences of $\to$ in $A$.

• Base: If $n = 0$ then $A$ is a propositional variable and hence $v(A) = \top$ by hypothesis.

• Inductive step: If $n > 0$ then $A = B \to C$. Since $v$ is a valuation such that $v(p_i) = \top$ for all propositional variables $p_i$ occurring in $A$, then $v$ is such that $v(p_i) = \top$ for all propositional variables $p_i$ occurring in $B$ and $C$. By induction hypothesis, $v(B) = \top$ and $v(C) = \top$. According to the truth table of $\to$, this implies that $v(A) = \top$. $\Box$

Secondly, observe that the formula $\lnot p$ (where $p$ is a propositional variable) is such that $v(\lnot p ) = \bot $ for the valuation $v$ such that $v(p) = \top$. According to the lemma above, there is no formula $A$ built up using only the connective $\to$ that is logically equivalent to $\lnot p$. Therefore, $\{\to\}$ is not functionally complete, because it cannot express the truth table of $\lnot$.