# Not a functionally complete set

I have to show that the set $C=\{\to , \lor \}$ is not a functionally set. I think that I have to find a connective that is not possible to replicate with the connectives of my set C. But how I can proceed to show it? Sorry for my english, I'm Italian. Thanks for the attention.

Prove by structural induction that every expression built from $\to$, $\lor$, and a single variable represents one of these two truth functions.
• sorry but I don't understand in what I have to the induction. For example how is the base of the induction?If I pick one variable, $p \to p$ and $p \lor p$ give me two different truth table...thanks Commented Jan 6, 2014 at 16:32
• @andreasvr: The base of structural induction is the simplest possible expression: one variable alone. Yes, $p\to p$ and $p \lor p$ give two different truth tables, but there are two other truth tables that you cannot produce with $\to$ and $\lor$ alone. Commented Jan 6, 2014 at 16:39
• Yes yes, sorry but only now I have understand your precious hint...I try to explain what I have understand... The base of the induction show me that picked p that has truth values $(1,0)$, $p \to p$ goes to $(1,1)$ and $p \lor p$ goes to $(1,0)$. Commented Jan 6, 2014 at 16:46
• @andreasvr: Yes. So what you have to prove for the induction step is that if $\varphi(p)$ and $\psi(p)$ each have one of those two truth tables, then so do $\varphi(p)\to\psi(p)$ and $\varphi(p)\lor\psi(p)$. Commented Jan 6, 2014 at 16:49
• Sorry but only now I understood your precious hint. I try to explain... The base of the induction show me that picked p with truth values $(1,0)$, $p \to p$, $p \lor p$ go respectively to $(1,1)$,$(1,0)$. Now let's $\alpha$ a formula with n+1 connectives of types $\to$ or $\lor$. I assume for inductive hypotesis that for n connectives my truth table is $(1,1)$ or $(1,0)$. So $\alpha=\psi \to p$ or $\alpha= \psi \lor p$. Proceeding by induction the truth table of $\psi$ is $(1,1)$ or $(1,0)$.I have only to show that $\psi \to p$ or $\alpha= \psi \lor p$ goes to $(1,1) or (1,0)$. Commented Jan 6, 2014 at 17:02