Can either one of $P ⟹ (Q ⟹ P)$ or $Q ⟹ (P ⟹ P)$ be derived from the other in the implicational propositional calculus?

Question

I am reading a bit about the implicational propositional calculus and initially I was confused about the axiom system:

Axiom Schema 1: $P ⟹ (Q ⟹ P)$

Axiom Schema 2: $(P ⟹ (Q ⟹ R)) ⟹ ((P ⟹ Q)⟹ (P⟹R))$

Axiom Schema 3: $((P ⟹ Q) ⟹ P) ⟹ P$

Each one of these is a tautology; moreover, $P ⟹ (Q ⟹ P)$ and $((P ⟹ Q) ⟹ P) ⟹ P$ are both tautologies in $2$ variables. My initial confusion (which I still have not resolved and must point to a fundamental gap in my understanding) is that I am not sure why one of $P ⟹ (Q ⟹ P)$ or $((P ⟹ Q) ⟹ P) ⟹ P$ can't be derived from the other since they are both tautologies in $2$ variables.

In my attempts to figure out what my misunderstanding was I thought that maybe it had something to do with the fact that:

• $((P ⟹ Q) ⟹ P) ⟹ P$ has $3$ instances of $P$, whereas $P ⟹ (Q ⟹ P)$ has only $2$

or maybe it had something to do with the fact that

• $((P ⟹ Q) ⟹ P) ⟹ P$ has $3$ instances of $⟹$, whereas $P ⟹ (Q ⟹ P)$ only has $2$

And to test that theory I wanted to see if one of $P ⟹ (Q ⟹ P)$ or $Q ⟹ (P ⟹ P)$ is derivable from the other since they both are tautologies in $2$ variables with $2$ instances of $⟹$, $2$ instances of $P$, and $1$ instance of $Q$.

The problem is, I don't know how to go about showing that one is (or isn't) derivable from the other in the implicational propositional calculus.

Any insight into this issue will be greatly appreciated.

Answer 1

By 'being derivable from each other' I assume that you can still use Axioms 2 and 3, but use 'the other' as Axiom 1.

As such, $Q \to (P \to P)$ can be derived from Axioms 2 and 3 together with $P \to (Q \to P)$, i.e. the original Axiom 1:

\begin{array}{lll} 1 & (P \to ((P \to P) \to P) \to ((P \to (P \to P)) \to (P \to P)) &Axiom \ 2\\ 2 & P \to ((P \to P) \to P) & Axiom \ 1\\ 3 & (P \to (P \to P)) \to (P \to P)& MP \ 1,2\\ 4 & P \to (P \to P) & Axiom \ 1\\ 5 & P \to P & MP \ 3,4\\ 6 & (P \to P) \to (Q \to (P \to P)) & Axiom \ 1\\ 7 & Q \to (P \to P) & MP \ 5,6\\ \end{array}

However, $P \to (Q \to P)$ can not be derived from Axioms 2 and 3 together with $Q \to (P \to P)$. Here is why.

Suppose we have a $4$-valued semantics. That is, suppose that all variables take on one of three values $0$, $1$, $2$, or $3$. Now assume that the $\to$ operator works as specified by the following table with the value of the left-operand on the left, and the value of the right-operand at the top:

\begin{array}{c|cccc} & 0&1&2&3\\ \hline 0&1&1&1&1\\ 1&0&1&3&3\\ 2&0&1&1&0\\ 3&0&1&1&1\\ \end{array}

Thus, for example, $1 \to 2 = 3$

Let's see what happens with this semantics for the $\to$ to the statements of $Q \to (P \to P)$, $((P \to Q) \to P) \to P$, and $P \to (Q \to P)$:

\begin{array}{cc|c|rc|cll|rc} P&Q&P\to Q & Q \to & (P \to P) & ((P \to Q) & \to P) & \to P & P \to & (Q \to P)\\ 0&0&1&\color{red}1&1&1&0&\color{red}1&\color{red}1&1\\ 0&1&1&\color{red}1&1&1&0&\color{red}1&\color{red}1&0\\ 0&2&1&\color{red}1&1&1&0&\color{red}1&\color{red}1&0\\ 0&3&1&\color{red}1&1&1&0&\color{red}1&\color{red}1&0\\ 1&0&0&\color{red}1&1&0&1&\color{red}1&\color{red}1&1\\ 1&1&1&\color{red}1&1&1&1&\color{red}1&\color{red}1&1\\ 1&2&3&\color{red}1&1&3&1&\color{red}1&\color{red}1&1\\ 1&3&3&\color{red}1&1&3&1&\color{red}1&\color{red}1&1\\ 2&0&0&\color{red}1&1&0&1&\color{red}1&\color{red}1&1\\ 2&1&1&\color{red}1&1&1&3&\color{red}1&\color{red}0&3\\ 2&2&1&\color{red}1&1&1&3&\color{red}1&\color{red}1&1\\ 2&3&0&\color{red}1&1&0&1&\color{red}1&\color{red}1&1\\ 3&0&0&\color{red}1&1&0&1&\color{red}1&\color{red}1&1\\ 3&1&1&\color{red}1&1&1&3&\color{red}1&\color{red}1&3\\ 3&2&1&\color{red}1&1&1&3&\color{red}1&\color{red}0&0\\ 3&3&1&\color{red}1&1&1&3&\color{red}1&\color{red}1&1\\ \end{array}

We see that $Q \to (P \to P)$ and $((P \to Q) \to P) \to P$ always evaluate to $1$. As such, we can call them '$1$-tautologies'. But note that $P \to (Q \to P)$ is not a $1$-tautology.

Now, what about the statement $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$? We could do a $64$ row table, but we can reason this out more quickly.

First, since $\varphi \to \psi$ never evaluates to $2$, $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ will never evaluate to $2$.

Second, for the same reason that $\varphi \to \psi$ never evaluates to $2$, we know that $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ cannot evaluate to $3$. This is because the only way for it to evaluate to $3$ would be when $P \to (Q \to R)$ evaluates to $1$, and $(P \to Q) \to (P \to R)$ to $3$, meaning that $P \to Q$ would have to evaluate to $1$, and $P \to R$ to $3$, and that in turn means that $P$ would have to evaluate to $1$ and $R$ to $2$ or $3$. However, with $p$ being $1$, $P \to Q$ can only evaluate to $1$ if $Q$ evaluates to $1$, and with $R$ being $2$ or $3$, that means $Q \to R$ evaluates to $3$, and hence $P \to (Q \to R)$ would evaluates to $3$, rather than $1$. So, $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ cannot evaluate to $3$.

Finally, and again because $\varphi \to \psi$ never evaluates to $2$, the only way for statement $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ to evaluate to $0$ would be when $P \to (Q \to R)$ evaluates to $1$ or $3$, and $(P \to Q) \to (P \to R)$ to $0$, and the latter means that $P \to Q$ would have to evaluate to $1$ or $3$, and $P \to R$ to $0$, and that in turn means that $P$ would have to evaluate to $1$, $2$, or $3$, and $R$ to $0$. This means that $Q$ cannot evaluate to $0$, for otherwise $P \to Q$ would have to evaluate to $0$ as well. But if $Q$ evaluates to $1$, $2$, or $3$, then $Q \to R$ evaluates to $0$, and hence $P \to (Q \to R)$ would evaluate to $0$ as well, so that can't be either. So, there is no way for $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ to evaluate to $0$.

In sum: $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ will always to evaluate to $1$, and is therefore a $1$=-tautology.

OK, so using $Q \to (P \to P)$, $((P \to Q) \to P) \to P$, and $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$ as the axioms, it turns out that they are all $1$-tautologies under this semantics.

Also, note that when applying Modus Ponens to any two $1$-tautologies, you will always get another $1$-tautology, because the only time that $\varphi \to \psi$ and $\varphi$ both evaluate to $1$ is where $\psi$ evaluates to $0$. So, applying Modus Ponens to $1$-tautologies, you can only get more $1$-tautologies.

However, we already saw that $P \to (Q \to P)$ is not a $1$-tautology. Therefore, $P \to (Q \to P)$ cannot be derived from the other three.

Answer 2

Axiom 3 is known Pierce's Law, which is the implication connective form of the Law of the Excluded Middle and is known to be unprovable from the deduction theorem alone (where we include Modus Ponens as a tautology along as part of the deduction theorem; Modus Ponens is also assumed in the Implicational Propositional Logic, so this is reasonable). Just because you have things we decide to be "tautologies" of a given number of variables doesn't mean you can immediately prove other "intuitive tautologies" of the same number of variables. Your system might not be strong enough.

To conclude here, note the Wikipedia Page for the Deduction Theorem includes proofs of both your Axioms 1 and 2 using only the Deduction Theorem. If Axiom 3 could be proved from Axioms 1 and 2 this would mean Pierce's Law could be proved by the Deduction Theorem, known to be false.

I cannot yet think of a quick way to show Axiom 3 does not imply Axiom 1. If you use classical logic and translate the axioms you will find they all say very different things, and there is no reason to suspect any of the three axioms are redundant.

Answer 3

The simplest way to look at this sort of problem is to look at the axiom systems through condensed detachment. An axiom system under Condensed detachment only produces theorems which are the most general theorems up to relettering of the variables given the axioms. A theorem A is more general than another theorem B if by using only substitution in A we can obtain B, but we can't use substitution from B to obtain A. For example, (P$\rightarrow$(P$\rightarrow$P)) is not a most general type of theorem in the implicational propositional, since both (Q→(P→P)) and (P→(Q→P)) are more general.

Suppose, (Q$\rightarrow$(P$\rightarrow$P)) is our only axiom. Alright, so we make some copy of (Q$\rightarrow$(P$\rightarrow$P)) and put that in for Q. Then we'll obtain (P$\rightarrow$P) as a theorem. All other theorems are substitution instances of (Q$\rightarrow$(P$\rightarrow$P) and (P$\rightarrow$P). (P$\rightarrow$(Q$\rightarrow$P)) is not one of those theorems. Thus, (P$\rightarrow$(Q$\rightarrow$P)) is not derivable from (Q$\rightarrow$(P$\rightarrow$P)).

Conversely, the theorems generated via condensed detachment with (P→(Q→P)) follow a pattern and always get longer. Basically, one can see what this pattern is as follows:

1. (P→(Q→P))

2. (A1$\rightarrow$1.)

3. (A2$\rightarrow$2.)

and so on ad infinitum.

(Q$\rightarrow$(P$\rightarrow$P)) isn't on that list, and thus can't get proved.