Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
(1) is certainly independent of the others, since it is false (with the standard interpreations of the symbols) while the others are true. –  Chris Eagle Feb 21 '12 at 23:45
    
Ah sorry I had the axiom wrong! –  hmmmm Feb 21 '12 at 23:48
2  
As usual in logic, independence is proven by constructing a suitable model. For example, what if we interpret $\to$ as "iff"? –  Zhen Lin Feb 22 '12 at 7:25
1  
@hmmmm: In your comment, by "the second axiom", did you mean the third? –  joriki Feb 22 '12 at 16:34
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. –  joriki Feb 22 '12 at 17:23

1 Answer 1

up vote 2 down vote accepted

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)

share|improve this answer
    
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. –  Doug Spoonwood Jun 21 '13 at 1:19
    
The first truth table here for "→" and "¬" has the same semantics as Lukasiewicz's three-valued logic. –  Doug Spoonwood Jun 21 '13 at 1:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.