Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How is reductio ad absurdum a valid proof method?

  1. May 24, 2008 #1
    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.
     
  2. jcsd
  3. May 24, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)

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

    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.
     
  4. Jun 26, 2008 #3
    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.
     
  5. Jun 26, 2008 #4
    Re: How is reduction ad absurdum a valid proof method?

    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
     
  6. Jun 27, 2008 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  7. Jun 27, 2008 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

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

    Suppose [itex]R[/itex] and its contradiction [itex]\lnot R[/itex] are both true in some theory. I will prove a statement [itex]S[/itex] in this theory using two tautologies and the rule of modus ponens:
    • [tex]\lnot P \to (\lnot Q \to \lnot P)[/tex]
      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 [tex]\lnot P \to (\lnot Q \to \lnot P)[/tex] is a tautology.

    • [tex](\lnot Q \to \lnot P) \to (P \to Q)[/tex]
      (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.

    • [tex]A \to B, \, A\vdash B[/tex]
      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. [tex]\lnot R\quad[/tex]
      Given.

    2. [tex]\lnot S \to \lnot R[/tex]
      From step 1 and tautology a.

    3. [tex]R \to S[/itex]
      From step 2 and tautology b.

    4. [tex]R\qquad[/tex]
      Given.

    5. [tex]S[/itex]
      From step 4 and step 3, and QED.
     
  8. Jun 27, 2008 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  9. Jun 27, 2008 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  10. Jun 27, 2008 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Amusingly, I can never remember what modus tollens is despite having learned Latin.
     
  11. Jun 27, 2008 #10

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  12. Jun 27, 2008 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Modus pollens? Is that another name for modus ponens?
     
  13. Jun 27, 2008 #12
    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.
     
  14. Jun 27, 2008 #13

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  15. Jun 27, 2008 #14

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    No. Its another name for DH types too fast.
     
  16. Jun 27, 2008 #15

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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. [tex]1\stackrel{\mathrm{def}}{=}S(0)[/tex]
    2. [tex]2\stackrel{\mathrm{def}}{=}S(1)[/tex]
    3. [tex]1+0=1[/tex]
    4. [tex]1+1=1+S(0)[/tex] (using 1)
    5. [tex]1+1=S(1+0)[/tex] (using 4)
    6. [tex]1+1=S(1)[/tex] (using 3 and 5)
    7. [tex]1+1=2[/tex] (using 2 and 6)

    There. Now let's see you do [tex]2\times2=4[/tex] in Peano arithmetic.
     
  17. Jun 27, 2008 #16
    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.
    [tex]R \wedge \neg R[/tex]
    Then study carefully the following steps.
    1) [tex]R \wedge \neg R[/tex]
    2) [tex]R[/tex]................................(from step 1 and using conjuction elimination)
    3) [tex] \neg R[/tex].............................(from step 1 and using conjuction elimination)
    4) [tex]R \rightarrow R \vee Q[/tex].................(from step 2 and using disjunction introduction)
    5) [tex]R \vee Q[/tex].........................(from step 2 and step 4 and using modus ponens)
    6) [tex]R \vee Q \leftrightarrow \neg R \rightarrow Q[/tex]...... (from step 5 and using material implication)
    7) [tex]\neg R \rightarrow Q[/tex].....................(from steps 5 and 6 and modus ponens)
    8) [tex]Q[/tex] ...............................(from step 7 and step 3 and modus ponens)

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

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    What does that mean?
     
  19. Jun 27, 2008 #18
    I mean to explicitly mention the laws of logic involved in every step of your proof.
    Where is that?
     
  20. Jun 27, 2008 #19
    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.
     
  21. Jun 27, 2008 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How is reductio ad absurdum a valid proof method?
Loading...