# Axiom System Irreducible

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.

• – Mauro ALLEGRANZA Feb 9 '18 at 15:52
• – Mauro ALLEGRANZA Feb 9 '18 at 15:59
• @MauroALLEGRANZA my third axiom is different to the one in discussion in that thread, and here I'm seeking a contradiction...I must say I've only done propositional calculas so far. I forgot to add I played with deduction theorem above as well. – WhizKid Feb 9 '18 at 16:00
• And see also the post what-would-be-an-example-of-a-proof-system-being-sound-but-not-complete – Mauro ALLEGRANZA Feb 9 '18 at 16:03
• @MauroALLEGRANZA ok so the first post you attached, I see your using the two axioms above, EFQ and Pierce's law to prove what I want (although I don't see how you got step 3 in that proof)...having shown and that EFQ and Pierce are tautologies...is that enough to show there is no proof using only the first two axioms? – WhizKid Feb 9 '18 at 17:24

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.

• Note that Bram's nonstandard semantics is just the usual one with the letters T and F interchanged. So a more syntactic way of phrasing the same argument would be that as long as neither of our axioms even mentions $\bot$, any proof of $((p\to\bot)\to\bot)\to p$ could become a proof of $((p\to q)\to q)\to p$ just by replacing every $\bot$ in it with a $q$. And the latter formula is not a tautology. – hmakholm left over Monica Feb 9 '18 at 23:04
• For an argument with a similar flavor, see "Examples" under en.wikipedia.org/wiki/Heyting_algebra and use the example $\{ 0, \frac{1}{2}, 1 \}$ for a model of (generalized) truth values and $\rightarrow$ in which the given axioms always evaluate to 1, and modus ponens works (if $(p \rightarrow q) = 1$ and $p = 1$ then $q = 1$), but $((p \rightarrow 0) \rightarrow 0) \rightarrow p$ doesn't always evaluate to 1. – Daniel Schepler Feb 9 '18 at 23:21
• why doesn't this work with the normal semantics for => (by symmetry-guessing it's symmetric after all)? Plus when you say syntax doesn't fix semantics, I'm open to defining the semantics for => as I choose? – WhizKid Feb 11 '18 at 2:00
• @WhizKid With the normal semantics all three statements are always true, i.e. They would all be tautologies. So no, it doesn't work with that. And yes, you can define the semantics any which way you want. In fact, you don't even need to suppose that the variables take on only one of two values ... there could be three or more values. – Bram28 Feb 11 '18 at 2:09
• i presume completeness theorem can't be applied here, if anything it would be the false rather than true version if I'm imagining it right? – WhizKid Feb 11 '18 at 2:23

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.