$¬((p_1 \rightarrow p_2)\rightarrow (p_2\rightarrow p_3))$ cannot be expressed using only connectives in $\{∧,\rightarrow\}$

Question

Show that the formula $¬((p_1 \rightarrow p_2)\rightarrow (p_2\rightarrow p_3))$ is not logically equivalent to a formula involving only connectives from the set $\{∧,\rightarrow\}$.

Am I correct in thinking it is because we cannot write the negation connective $¬$ and the connective $\rightarrow$ using only the connectives in the set $\{∧,\rightarrow \}?$

($\phi \rightarrow \psi$) is logically equivalent to (($\lnot\phi)\lor \psi$) but the connectives $¬$ and $\lor$ do not exist in the set $\{\land, \rightarrow \}.$

I just don't really know how to go any further to show it.

Thanks

Answer 1

$$\begin{align} \lnot((p_1 \rightarrow p_2) \rightarrow(p_2 \rightarrow p_3)) & \equiv \lnot(\lnot(p_1\rightarrow p_2) \lor (p_2\rightarrow p_3))\tag{1}\\ \\ & \equiv (p_1\rightarrow p_2) \land \lnot(p_2\rightarrow p_3)\tag{2}\\ \\ &\equiv (p_1 \rightarrow p_2) \land \lnot(\lnot p_2 \lor p_3) \tag{3}\\ \\ & \equiv (p_1 \rightarrow p_2) \land p_2 \land \lnot p_3\tag{4}\end{align}$$

In $(4)$, we have the connectives $\land, \rightarrow$, but we also have the negation $\lnot$ of the literal $p_3$. (Similarly, in $(2)$ we have the only $\rightarrow$ and $\land$, but still also need $\lnot$.) We cannot simply omit the negation sign in either without losing the meaning of the proposition.

See the Wikipedia entry on Functional Completness for a more formal treatment on how to determine whether a set of connectives is complete, or adequate, to express all possible truth valuations for, in this case, an expression with three variables.

Answer 2

See Herbert Enderton, A Mathematical Introduction to Logic (2nd ed Harcourt - 2001), page 50.

With only the $\land$ and $\rightarrow$ connectives, if the sentence symbols in our formula are assigned the value $\top$, then the entire formula is assigned the value $\top$.

We have to proof this by induction on the lenght of the formula; i.e. we have to show that for any wff $\alpha$ built up using only these connectives we have that :

in each valuation $v$ such that $v(p_i) = \top$, for each $p_i$ in $\alpha$, then $v(\alpha) = \top$.

The proof is trivial :

Basis

$\alpha$ is $p_1$; then, $v(p_1) = \top = v(\alpha)$.

Induction step

$\alpha$ is $\alpha_1 \land \alpha_2$ or $\alpha_1 \rightarrow \alpha_2$, where we assume by induction hypotheses, that :

if $v(p_i)=\top$ for each $p_i$ in $\alpha_1$ and $\alpha_2$, then $v(\alpha_1)=v(\alpha_2)=\top$.

It's enough to use truth-tables.

Having shown this, we have shown that with only the two connectives $\land$ and $\rightarrow$ we are not able to "produce" a formula that, when all its sentence letters evaluates to $\top$ (i.e.TRUE), it gives as result the value $\bot$ (i.e.FALSE).

But with the valuation $v_0$ such that :

$v_0(p_1)=v_0(p_2)=v_0(p_3)= \top$

the formula $\alpha := \lnot [(p_1 \rightarrow p_2) \rightarrow (p_2 \rightarrow p_3)]$

will have the value $\bot$.

Another way to prove it is based on :

the equivalence between : $p \rightarrow q$ and $\lnot (p \land \lnot q)$,

in classical logic : because we need Double Negation.

Using this equivalence, we may rewrite our formula as :

$(p_1 \rightarrow p_2) \land \lnot (p_2 \rightarrow p_3)$

and again as :

$\lnot (p_1 \land \lnot p_2) \land (p_2 \land \lnot p_3)$.

Now we may apply the above argument in terms of valuations; with $v_0(p_1)=v_0(p_2)=v_0(p_3)= \top$, we have that :

$[\lnot (\top \land \lnot \top) \land (\top \land \lnot \top)] \equiv [\lnot (\top \land \bot) \land (\top \land \bot)] \equiv (\lnot \bot \land \bot) \equiv (\top \land \bot) \equiv \bot$.

But we have the above result that with only the $\land$ and $\rightarrow$ connectives, if the sentence symbols in a formula are assigned the value $\top$, then the entire formula is assigned the value $\top$.

Thus, is not possible to find a formula with only $\land$ and $\rightarrow$ that is equivalent to the original one.

Answer 3

Every function created with the connectives $\rightarrow$ and $\land$ has the property that $f(\text{true}, \text{true}, \dots) = \text{true}$

Prove with structural induction.

The provided function doesn't have that property.