Axiom System Irreducible

Question

I want to show that you can't syntactically deduce $[(p\to f)\to f]\to p$ where $f$ is false from the following two tautologies:

$p\to (q\to p)$

$[p\to (q\to r)]\to [(p\to q)\to (p\to r)]$

My attempt has been saying suppose there was a solution, I used the completeness theorem but haven't got a contradiction. Thanks.

Answer 1

Suppose the semantics of the $\rightarrow$ is this:

\begin{array}{cc|c} p&q&p\rightarrow q\\ \hline T&T&F\\ T&F&F\\ F&T&T\\ F&F&F\\ \end{array}

This is of course not the normal semantics for the $\rightarrow$, but that's just the point: syntax doesn't fix semantics, so we are free to play with the semantics.

Now let's look at your two axioms:

\begin{array}{cc|ccccc} p&q&p&\rightarrow &(q &\rightarrow &p)\\ \hline T&T&T&\color{red}F&T&F&T\\ T&T&T&\color{red}F&F&T&T\\ T&T&F&\color{red}F&T&F&F\\ T&T&F&\color{red}F&F&F&F\\ \end{array}

\begin{array}{ccc|ccccccccccccc} p&q&r&(p&\rightarrow & (q & \rightarrow & r) & ) \rightarrow ( & (p & \rightarrow & q) & \rightarrow & (p & \rightarrow & r))\\ \hline T&T&T&T&F&T&F&T&\color{red}F&T&F&T&F&T&F&T\\ T&T&F&T&F&T&F&F&\color{red}F&T&F&T&F&T&F&F\\ T&F&T&T&F&F&T&T&\color{red}F&T&F&F&F&T&F&T\\ T&F&F&T&F&F&F&F&\color{red}F&T&F&F&F&T&F&F\\ F&T&T&F&F&T&F&T&\color{red}F&F&T&T&F&F&T&T\\ F&T&F&F&F&T&F&F&\color{red}F&F&T&T&F&F&F&F\\ F&F&T&F&T&F&T&T&\color{red}F&F&F&F&T&F&T&T\\ F&F&F&F&F&F&F&F&\color{red}F&F&F&F&F&F&F&F\\ \end{array}

OK, so we see that these two axioms are always false, i.e. they are contradictions (I highlighted the main connective). Moreover, if you look back at how we defined the semantics for the $\rightarrow$, you'll find that given that whenever $p \rightarrow q$ is $F$, and $p$ is $F$, $q$ will always be $F$ as well. This means that with this semantics, if you start out with any (instance of) the axioms, and the only inference rule you have is Modus Ponens, then the only resulting statements will have to be contradictions.

OK, but is $((p \rightarrow \bot) \rightarrow \bot) \rightarrow p$ a logical contradiction under this semantics (and here I used $\bot$ as the statement that is always $F$)? Well, let's see:

\begin{array}{c|ccccccc} p&((p & \rightarrow & \bot) & \rightarrow & \bot ) & \rightarrow & p\\ \hline T&T&F&F&F&F&\color{red}T&T\\ F&F&F&F&F&F&\color{red}F&F\\ \end{array}

No, it is not. Hence, it can not be inferred from the two axioms and Modus Ponens alone.

Answer 2

First, recall, that two statements $A$ and $B$ are independent from one another, if there is some model $\mathfrak{M}_1$ wherein $\mathfrak{M}_1\vDash A$ and $\mathfrak{M}_1\nvDash B$ and there is also a model $\mathfrak{M}_2$ wherein $\mathfrak{M}_2\vDash B$ and $\mathfrak{M}_2\nvDash B$. Moreover, we will need to find models $\mathfrak{M}_3\vDash A,B$ and $\mathfrak{M}_4\nvDash A,B$.

Note, that it is not enough to show that there is a model, where $A$ is false and $B$ is false for it will not rule out that the statements are incompatible (i.e. have no common models), nor is it enough to show only a model wherein first one is true and second one is false (it does not rule out that second is stronger than the first one).

However, we don't need to show independence of these statements, we only need to show that $p\rightarrow(q\rightarrow p)$ and $(p\rightarrow(q\rightarrow r))\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))$ do not entail $((p\rightarrow\bot)\rightarrow\bot)\rightarrow p$. This means that we need to show that there is a model wherein $p\rightarrow(q\rightarrow p)$ and $(p\rightarrow(q\rightarrow r))\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))$ are true but $((p\rightarrow\bot)\rightarrow\bot)\rightarrow p$ is false.

Fortunately, this task can also be easily done. Intuitionistic logic is one of those logics where we have $p\rightarrow(q\rightarrow p)$ and $(p\rightarrow(q\rightarrow r))\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))$ but don't have $((p\rightarrow\bot)\rightarrow\bot)\rightarrow p$. It now remains to construct an intuitionistic model where $((p\rightarrow\bot)\rightarrow\bot)\rightarrow p$ does not hold.

A model can be as follows. $$ w_0\longrightarrow w_1 $$

If we set $w_0\nvDash p$ and $w_1\vDash p$, we will have that $w_0\nvDash((p\rightarrow\bot)\rightarrow\bot)\rightarrow p$ in intuitionistic semantics.