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
    (1) is certainly independent of the others, since it is false (with the standard interpreations of the symbols) while the others are true.2012-02-21
  • 0
    Ah sorry I had the axiom wrong!2012-02-21
  • 2
    As usual in logic, independence is proven by constructing a suitable model. For example, what if we interpret $\to$ as "iff"?2012-02-22
  • 0
    If we do this do we have that the second axiom is still valid but axioms 1 and 2 are not so it is independent from them?2012-02-22
  • 0
    @Zhen: I'm wondering what exactly a model is in this case. I used the term [here](http://math.stackexchange.com/questions/93420/prove-a-rightarrow-b-rightarrow-neg-b-rightarrow-neg-a-in-hilbert-sys/93563#93563) in the same sense as you seem to be using it, but now I'm thinking that this is something slightly different from what the term means in model theory, because $\to$ is acting both as a function (else we couldn't use its output as its input) and as a relation (else its output couldn't be the truth value of the expression), so we can't choose an arbitrary universe, and $\to$ is restricted2012-02-22
  • 0
    ... to be a function that maps two truth values to a truth value. I went through all $16$ of these, and unless I made a mistake the "real" $\to$ is the only one for which the first axiom is valid. So that seems to say that we can't prove e.g. that the second one is independent of the first by finding a non-standard model in which the first is valid and the second isn't. Or am I confused about this? Also I'm not sure I understand what you're getting at with the interpretation as "iff" -- only the third axiom is valid under that interpretation, so this proves that it doesn't entail the others?2012-02-22
  • 1
    @hmmmm: In your comment, by "the second axiom", did you mean the third?2012-02-22
  • 0
    yes sorry the third is still valid and the other two are not, right?2012-02-22
  • 1
    People don't get notified of your comments unless you ping them using the @username idiom. Yes, that's correct -- so that shows that the other two are independent of that one taken alone, not the other way around as you said in your previous comment.2012-02-22
  • 0
    @joriki ah ok thanks, I can't see a way of showing the independence of the others using just two valued functions, do we do it using three valued functions?2012-02-22
  • 0
    @hmmmm: Yes, it is sometimes necessary to consider truth values in sets other than the usual $\{ 0, 1 \}$.2012-02-22
  • 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
    This sort of independence proof implies a bounded lattice of logical systems, if we take the empty axiom set under modus ponendo ponens as a rule of inference as a logical system also. Presuming the rule of inference understood, the atoms of this lattice are the individual axioms. Their join is simply their union, and the meet is simply the intersection of the axiom sets.2013-06-21
  • 0
    The first truth table here for "→" and "¬" has the same semantics as Lukasiewicz's three-valued logic.2013-06-21