Can someone please explain why I can't use only IMPLICATION to represent AND and NOT with proof as well?
I know that I can represent OR simply by using IMPLICATION. Was thinking if I could find representation of NOT, then I can easily find representation of AND.
From my understanding, we can represent IMPLICATION by using OR and NOT set. Which is a functionally complete. Does this mean that Implication is also functionally complete?
On
One way of approaching a formal proof of this, is by induction, I'll do negation for you, and you can see if you can modify it to do conjunction.
Notice that if you have an expression $\phi$ which is equivalent to $\neg A$, which has any occurrences of any propositional variables other than $A$, then, you can just replace them with $A$. Hence, we only need to consider sentences in $A$ and $\rightarrow$.
Claim: Any sentence in $A$ and $\rightarrow$ evaluates to true, when $A$ is true.
Proof: By induction on the length of the sentence. The base case is the sentence $A$, and clearly this is true with $A$ is true. In the induction step the expression is of the form $\phi \rightarrow \psi$, for some sentences $\phi$ and $\psi$ in only $A$ and $\rightarrow$. Also $\phi$ and $\psi$ are shorter, so, we can apply the induction hypothesis. In particular when $A$ is true $\phi$ and $\psi$ are both true. But then, by the semantics for $\rightarrow$, when $A$ is true $\phi\rightarrow \psi$ is true too.
Q.E.D.
So, any expression we can make preserves truth, and so, can't be equivalent to negation.
On
The problem with using $\Rightarrow$ as the only operator is that you cannot construct an universally false statement - which is required for a set of operators to be functionally complete. You can do this with for example $\lor$ and $\neg$, for example $\neg (\phi \lor \neg \phi)$.
To see why this is we can break down any statement into the form $\phi \Rightarrow \psi$, we also know that there should be a minimal such statement that is universally false (that is $\phi$ and $\psi$ are not universally false - or we could use $\phi$ or $\psi$ instead). But for $\phi\Rightarrow\psi$ to be false we must have $\phi$ being true and $\psi$ being false, and to be universally false we must have $\psi$ being universally false.
On the other hand if we had a universally false statement $\bot$ you could create the rest. For example $\phi\Rightarrow\bot$ is the same as $\neg\phi$ and when we constructed the $\neg$ operator we can construct the $\lor$ by observing that $\neg\phi\Rightarrow\psi$ is the same as $\phi\lor\psi$. The rest follows from that $\lor$ and $\neg$ are functionally complete.
Another way to see that $\Rightarrow$ is not functional complete is to consult characterization of functional completeness due to Post. This case is that $\Rightarrow$ is truth conserving connectives. This means that if all variables are true the result will be true and thereby any construct will be that as well. But a functionally complete set of connectives must be able to represent a statement that is false even though all variables are being true.
On
First I will show that $\land$ can not be represented using only $\to.$
Let $\mathcal S$ be the set of all formulas $\phi$ such that $\phi$ is a consequence of some propositional variable. Of course, every propositional variable belongs to $\mathcal S;$ moreover, for any formulas $\phi$ and $\psi,$ if $\phi\in\mathcal S$ then $\psi\to\phi\in\mathcal S.$ It follows (by induction on the length of formulas) that every formula, which contains no connectives other than $\to,$ belongs to $\mathcal S.$ Since the conjunction $p\land q$ is not a consequence of any single variable, it follows that $p\land q$ is not equivalent to (or even a consequence of) any formula in $\mathcal S;$ in particular $p\land q$ is not equivalent to any formula containing no connectives other than $\to.$
Since $\land$ can be represented using $\to$ and $\neg$, namely $p\land q=\neg(p\to\neg q),$ it follows that $\neg$ can not be represented using only $\to.$
$$\begin{align}\lnot A &\iff (A\implies \bot)\\ A\land B&\iff \lnot (A\implies\lnot B)\end{align}$$
If you can use $\bot$ as an argument to $\implies$ then I think this works. If you can not use $\bot$, then implementing $\lnot A$ is impossible. You are left with just $A$ and $\implies$. $A\implies A$ gives you $\top$, but it does not help. $\top\implies A$ is just $A$ and $A\implies\top$ is just $\top$ (as is $\top\implies\top$), so your return value can never be anything but $A$ or $\top$.