How is reductio ad absurdum a valid proof method?

[Werg22]

Main Question or Discussion Point

Since it's impossible to know whether or not a consistent theory is indeed consistent, how is a proof by contradiction a valid proof method? I would think a proof by contradiction is only valid if we are certain a theory is consistent, else a contradiction could mean that the theory is inconsistent.

 

[Hurkyl]

Since it's impossible to know whether or not a consistent theory is indeed consistent,

Only in the philosophical sense of absolute knowledge. Mathematically, not only do we have relative consistency proofs, but I'm pretty sure there are examples of first-order theories capable of proving their own consistency. (Such a theory cannot be both recursively enumerable and include the theory of integer arithmetic, of course)

how is a proof by contradiction a valid proof method?

It's a fairly direct consequence of the law of noncontradiction.

I would think a proof by contradiction is only valid if we are certain a theory is consistent, else a contradiction could mean that the theory is inconsistent.

A formal proof is valid if and only if it is built from the rules of deduction in whatever logic you're using.


Incidentally, in an inconsistent theory, every logical statement is a theorem. In particular, this includes the thing you were trying to prove.

 

[Mathsbaby]

Reductio ad absurdum and proof by contradiction are two (albeit subtlely) different approaches to proof. For the latter, taste seems to dictate whether it is a valid approach in mathematics. There is a recognised danger that contradiction can fail to reveal inconsistencies in assumptions. Also, in general, induction is easier computationallly.

Reductio ad absurdum means, for example, that if you can prove black is white then the moon is made of green cheese. i.e. they both have the same truth value.

 

[LAVRANOS]

The following will show you why Now we must be very careful to distinguish between an implication and a logical implication. We say P implies Q noted as P---->Q and this can be true or false depending on the values of p and q. And if p is false and q true then P--->Q is true A thing that mattgrime so much insisted on
And we say that P logically implies Q denoted by P===>Q(DOUBLE ARROW) ,If the implication P---->Q IS ALWAYS TRUE no matter what are the values of p and q
Now let us see how contradiction works
Suppose we want to prove P===>Q BY the power invested on us by the rule in logic called conditional we can assume P and if prove Q we can say we have proved P===>Q
So let P

NOW it happens some time that we don't know how to arrive at Q
hence we reason by contradiction,hence we assume
notQ
THEN along down the steps of proof we come across two statement which are contradictory i.e R and notR A statement which is always false
And here now the doctrine (false LOGICALLY IMPLIES everything) can be used so we can get Q But why???????? AND HOW ????????
Let us see why:from R AND notR we can get notR (The law is called addition elimination)
Now from notR we can get (notR or Q) using the law Disjunction introduction.
But (notR or Q) is logically equivalent to ( R--->Q) The law is called material implication
But from( R and notR) we can get R.
Hence now from (R--->Q)and R by using the law called M.Ponens we get Q

HENCE P===>Q

Note T is logically equivalent to S Iff they logically imply each other y contradiction is valid:
CERTAINLY we must assume that the system within we work is consistent .Very few systems are consistent and then again it depends on the definition of consistency.
The propositional calculus for example is asystem which is CONSISTENT COMPLETE AND DECIDABLE while predicate calculus is CONSISTENT AND COMPLETE relative to the set of valid formulas

 

[CRGreathouse]

Since it's impossible to know whether or not a consistent theory is indeed consistent, how is a proof by contradiction a valid proof method? I would think a proof by contradiction is only valid if we are certain a theory is consistent, else a contradiction could mean that the theory is inconsistent.

Theories prove statements. As you add axioms to theories, they can prove more statements (or as many, if you add something redundant). If you add enough powerful axioms the theory becomes inconsistent, that is, it proves every statement.

So proof by contradiction seems quite sensible to me. If the underlying theory is inconsistent you can prove everything anyway, so there's no problem with proof by contradiction (a problem would be not being able to prove something, since everything is provable).

 

[D H]

If you add enough powerful axioms the theory becomes inconsistent, that is, it proves every statement.

The mathematicians at PF know what this means. Many readers will not. What CR is saying is that if both a proposition $R$ and its contradiction $\lnot R$ are provable in some theory then any statement in the theory can be proven true. It's easy.

Suppose $R$ and its contradiction $\lnot R$ are both true in some theory. I will prove a statement $S$ in this theory using two tautologies and the rule of modus ponens:

• $$\lnot P \to (\lnot Q \to \lnot P)$$
  The contradiction of P implies (the contradiction of Q implies the contradiction of P). Material implication is bit of a strange beast. [tex]A\to B[/itex] means that if A is true then B must also be true. If A is true but B is false then A does not imply B. Material implication, on the other hand, does not place any limitations on B if A is false. The expression $$\lnot P \to (\lnot Q \to \lnot P)$$ is a tautology.
  
  
• $$(\lnot Q \to \lnot P) \to (P \to Q)$$
  (The contradiction of Q implies the contradiction of P) implies (P implies Q). This is another tautology. These two tautologies fall out from the definition of material implication.
  
  
• $$A \to B, \, A\vdash B$$
  This is modus ponens, which says that if A implies B is true and if [/i]A[/i] is true then B is true.

The proof, using modus ponens to move from step-to-step:

1. $$\lnot R\quad$$
   Given.
   
   
2. $$\lnot S \to \lnot R$$
   From step 1 and tautology a.
   
   
3. [tex]R \to S[/itex]
   From step 2 and tautology b.
   
   
4. $$R\qquad$$
   Given.
   
   
5. [tex]S[/itex]
   From step 4 and step 3, and QED.

 

[CRGreathouse]

Thanks for clearing that up, D H.

I'll note that the conclusion only holds if you allow certain axioms -- in the above, two particular tautologies (contraposition and introduction) along with modus ponens. Just like the equivalence of the axiom of choice and Zorn's lemma (which requires a strong enough fragment of ZF), the existence of rectangles (requires the parallel postulate), and the incompleteness of consistent systems (requires a certain system strength), this can fail for weak enough systems. In the extreme, the empty theory can't draw any conclusions from P and not-P.

 

[D H]

contraposition and introduction

I knew those tautologies had a name, too. I just could not remember them for the life of me. Why I can remember the names of the Latin phrases modus ponens and modus tollens but not the English terms is even more befuddling. I never learned Latin. It's Greek to me. Thanks, CR.

 

[CRGreathouse]

Amusingly, I can never remember what modus tollens is despite having learned Latin.

 

[D H]

Modus tollens is modus pollens run contrapositively backwards. Kinda.

Foward chaining rule systems like CLIPS and ART use modus pollens. Backward chaining rule systems like Prolog and make use modus tollens.

 

[CRGreathouse]

Modus pollens? Is that another name for modus ponens?

 

[LAVRANOS]

The point with you guys is that you write nonsense all the time and if somebody asks you a question with respect to your nonsense and illogical mumbling you get angry.
What actually happens is the following:
you read a couple of things in a couple of books and then you come here and you throw the stuff pretending that you are an expert.
Definitely nobody of you is knowledgeable enough in logic stuff to be able to put it in practice.
I ask you again: Do you know logic? If yes, here and now show me. Pick up any mathematical proof you like and show your expertise in applying the laws of logic in that proof.

 

[D H]

The point with you guys is that you write nonsense all the time and if somebody asks you a question with respect to your nonsense and illogical mumbling you get angry.

In a prior career incarnation I worked in the field of AI, back in its hey-day. I had the monitor for Symbolics machine #2 sitting on my desk and the rest of the machine (wire-wrap boards and all) sitting down the hall. I worked with the developers of CLIPS on a first-name basis. So please, try again.

 

[D H]

Modus pollens? Is that another name for modus ponens?

No. Its another name for DH types too fast.

 

[CRGreathouse]

The point with you guys is that you write nonsense all the time and if somebody asks you a question with respect to your nonsense and illogical mumbling you get angry.

I answered the question in post #5, though now I see Hurkyl gave the same answer (but shorter and better) in post #2. D H expanded on my answer in post #6.

I'll admit to being confused about 'us' getting angry: where has anyone displayed annoyance, let alone anger on this thread? Or are you talking about a different thread, perhaps? Sometimes the PhDs get a bit huffy in response to thickheadedness, but usually this is a friendly place. Certainly I can't recall ever posting here in anger.

you read a couple of things in a couple of books and then you come here and you throw the stuff pretending that you are an expert.
Definitely nobody of you is knowledgeable enough in logic stuff to be able to put it in practice.
I ask you again: Do you know logic? If yes, here and now show me. Pick up any mathematical proof you like and show your expertise in applying the laws of logic in that proof.

Wow, you're really throwing down the gauntlet.

1. $$1\stackrel{\mathrm{def}}{=}S(0)$$
2. $$2\stackrel{\mathrm{def}}{=}S(1)$$
3. $$1+0=1$$
4. $$1+1=1+S(0)$$ (using 1)
5. $$1+1=S(1+0)$$ (using 4)
6. $$1+1=S(1)$$ (using 3 and 5)
7. $$1+1=2$$ (using 2 and 6)

There. Now let's see you do $$2\times2=4$$ in Peano arithmetic.

 

[LAVRANOS]

Since it's impossible to know whether or not a consistent theory is indeed consistent, how is a proof by contradiction a valid proof method? I would think a proof by contradiction is only valid if we are certain a theory is consistent, else a contradiction could mean that the theory is inconsistent.

if the theory is not consistent, then a contradiction doesnt work.
I ask you again: Do you know how contradiction works?
I will show you for the last time how contradiction works.
In a proof by contradiction you ALWAYS END UP with 2 contradictory statements i.e.
$$R \wedge \neg R$$
Then study carefully the following steps.
1) $$R \wedge \neg R$$
2) $$R$$................................(from step 1 and using conjuction elimination)
3) $$\neg R$$.............................(from step 1 and using conjuction elimination)
4) $$R \rightarrow R \vee Q$$.................(from step 2 and using disjunction introduction)
5) $$R \vee Q$$.........................(from step 2 and step 4 and using modus ponens)
6) $$R \vee Q \leftrightarrow \neg R \rightarrow Q$$...... (from step 5 and using material implication)
7) $$\neg R \rightarrow Q$$.....................(from steps 5 and 6 and modus ponens)
8) $$Q$$ ...............................(from step 7 and step 3 and modus ponens)

So suppose you wanted to prove $$P \rightarrow Q$$
By using the rule of the conditional proof we assume $$P$$ and also we assume $$\neg Q$$
Then somewhere down along the proof we come with a contradictory statement $$P \wedge \neg P$$
Then we follow the above steps to prove $$Q$$
Take that home and study it carefully. Then I am sure you will change attitude

 

[CRGreathouse]

if the theory is not consistent, then a contradiction doesnt work.

What does that mean?

 

[LAVRANOS]

I answered the question in post #5, though now I see Hurkyl gave the same answer (but shorter and better) in post #2. D H expanded on my answer in post #6.

I'll admit to being confused about 'us' getting angry: where has anyone displayed annoyance, let alone anger on this thread? Or are you talking about a different thread, perhaps? Sometimes the PhDs get a bit huffy in response to thickheadedness, but usually this is a friendly place. Certainly I can't recall ever posting here in anger.



Wow, you're really throwing down the gauntlet.

1. $$1\stackrel{\mathrm{def}}{=}S(0)$$
2. $$2\stackrel{\mathrm{def}}{=}S(1)$$
3. $$1+0=1$$
4. $$1+1=1+S(0)$$ (using 1)
5. $$1+1=S(1+0)$$ (using 4)
6. $$1+1=S(1)$$ (using 3 and 5)
7. $$1+1=2$$ (using 2 and 6)

There. Now let's see you do $$2\times2=4$$ in Peano arithmetic.

I mean to explicitly mention the laws of logic involved in every step of your proof.
Where is that?

 

[LAVRANOS]

What does that mean?

It means that you cannot apply contradiction if the theory is incosistent.
Because in incosistent theories somewhere you will get a contradictory statement hence when you work by contradiction you will not know if you meet this particular statement and hence contadiction has no value.

 

[LAVRANOS]

Certainly I can't recall ever posting here in anger.

Maybe not you CRGreathouse but in another thread where i was acussed of not knowing the number pi (the Greek invented number) when i responded back the got so ungry that they deleted my posts.

 

[CRGreathouse]

I mean to explicitly mention the laws of logic involved in every step of your proof.
Where is that?

It's pretty evident, using two definitions, the two addition axioms, and the identity of indiscernibles.
I. n + 0 = n
II. m + S(n) = S(m + n)

1. $$1\stackrel{\mathrm{def}}{=}S(0)$$ (definition)
2. $$2\stackrel{\mathrm{def}}{=}S(1)$$ (definition)
3. $$1+0=1$$ (I)
4. $$1+1=1+S(0)$$ (identity of indiscernibles, using 1)
5. $$1+1=S(1+0)$$ (II, using 4)
6. $$1+1=S(1)$$ (identity of indiscernibles, using 3 and 5)
7. $$1+1=2$$ (identity of indiscernibles, using 2 and 6)

 

[CRGreathouse]

It means that you cannot apply contradiction if the theory is incosistent.
Because in incosistent theories somewhere you will get a contradictory statement hence when you work by contradiction you will not know if you meet this particular statement and hence contadiction has no value.

I don't follow at all. Of course you can get contradictions in inconsistent theories, that's the whole point. In fact inconsistent theories (unless paraconsistent or otherwise weak) prove all statements, so RAA/proof by contradiction correctly proves everything in those theories. Or rather, in that theory; other than the aforementioned weak theories, there is only one inconsistent theory. To be precise, there is a unique inconsistent theory containing first-order logic, which contains as theorems all the axioms of ZFC, Tarski's axiom, the generalized continuum hypothesis, the negation of the Riemann hypothesis, Martin's axiom, the existence of heaps of large cardinals, V = L, $$\beth_1=\aleph_3,$$ 1 + 1 = 7, and a host of other amazing statements.

 

[LAVRANOS]

OK STEPS 1 AND 2 ,BY WHAT LAW YOU GET 3
ALSO EXPLAIN <identity of indiscemibles>

 

[LAVRANOS]

if you cannot give a right proof i can give you one

 

[LAVRANOS]

O.K With such a small proof WHAT ABOUT THE FOLLOWING PROOF??
for all x and for all y(x>=0 and y>=0 -------> ( sqroot(xy)=sqroot(x).sqroot(y) ))
CAN YOU DO IT STEP WISE??????