Building logical connectives only with $\neg$ and $\to$

Question

We want to show that the only connectives that are absolutely necessary are $\neg$ and $\to$. Meaning we can construct all the others with them.

Given $A_1, A_2 \in \mathcal{L_0}$, the set of formulas, how can we construct:
(a) $(A_1\land A_2)$
(b) $(A_1\lor A_2) $
(c) $(A_1\iff A_2)$

(c) I find $\iff$ to be quite intuitive, I'd think $$(A_1\iff A_2) = ((A_1\to A_2) \to (A_2 \to A_1)).$$ But I believe that is wrong.

But I find the others hard to construct or understand their forms.

Answer 1

What you mean is that $\{ \neg, \to\}$ is a functionally complete set of connectives. We find such systems for example in Frege's famous Begriffsschrift (1879).

Naturally:

(a) $(A_1∧A_2) \equiv \neg (A_1 \to \neg A_2)$

(b) $(A_1∨A_2) \equiv \neg A_1 \to A_2$

(c) $(A_1 \leftrightarrow A_2) \equiv (A_1 \to A_2) \wedge (A_2 \to A_1)$

These equivalences can be more easily seen by noting that:

$\vDash (\varphi \to \psi) \leftrightarrow (\neg \varphi \vee \psi)$ or $\vDash \neg(\varphi \to \psi) \leftrightarrow (\varphi \wedge \neg \psi)$

Please note that (c) is not equivalent to the statement you suggested above.

Answer 2

Hint: Use the fact that $A\to B$ is equivalent to $\neg A \vee B$. And, of course, deMorgan's rules.