5
$\begingroup$

How do we show that we are using independent axioms in an axiomatic systems i.e

  1. $A\rightarrow (B \rightarrow A)$

  2. $(A\rightarrow (B\rightarrow C)) \rightarrow ((A\rightarrow B)\rightarrow (A\rightarrow C))$

  3. $(\lnot A\rightarrow \lnot B)\rightarrow (B\rightarrow A)$

I think I know how to show that the third is independent of the first two, we can take $\lnot \phi = \phi$ and then the first two are still valid but the third is not, but I'm not sure how to go about doing this for the other axioms.

Thanks for any help.

  • 0
    @ZhenLin Thanks, I'll try that out and see if can get anywhere, thanks for the help2012-02-23

1 Answers 1

3

OK so here goes,

To show that these three axioms are all independent we want to construct an interpretation that shows that two of the axioms are still valid but the third is not (as said in the comments). The first of these will just use two truth values (T,F) and the rest will use three (T,F,A).

To show that A3) is independent from A1) and A2)

This is the simplest case, we simply let our interpretation of $\lnot\phi$ and $\phi$ be the same. In this case we can see that A3) is no longer valid, by taking $A=F$ and $B=T$ then this is no longer valid but A1) and A2) obviously still are (they don't have a negation in them).

To show that A2) is independent from A1) and A3)

$ \begin{array} \hline A & B & A\rightarrow B \\ \hline T & T & T \\ \hline T & A & A \\ \hline T & F & F \\ \hline A & T & T \\ \hline A & A & T \\ \hline A & F & A \\ \hline F & T & T \\ \hline F & A & T \\ \hline F & F & T \\ \hline \end{array}$

$ \begin{array} \hline A & \lnot A \\ \hline T & F \\ \hline A & A \\ \hline F & T \\ \hline \end{array} $

We can now see that under these new interpretations that A1) and A3) are still valid but A2) is no longer valid under this new interpretation.

Showing that A1) is independent from A2) and A3)

We use the same argument as above but with the first table slightly different:

$ \begin{array} \hline A & B & A\rightarrow B \\ \hline T & T & T \\ \hline T & A & F \\ \hline T & F & F \\ \hline A & T & T \\ \hline A & A & T \\ \hline A & F & F \\ \hline F & T & T \\ \hline F & A & T \\ \hline F & F & T \\ \hline \end{array}$

$ \begin{array} \hline A & \lnot A \\ \hline T & F \\ \hline A & A \\ \hline F & T \\ \hline \end{array} $

So we can see that A1) is independent from A2) and A3) as they are still valid here but A1) is not.

We have now shown that these three axioms are independent from each other. (We should also notice that modus ponens is preserved under these two new interpretations)

  • 0
    The first truth table here for "→" and "¬" has the same semantics as Lukasiewicz's three-valued logic.2013-06-21