1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving: Proof by Contradiction

  1. Jan 16, 2013 #1
    I'm reading through a text's proof on proof by contradiction. But it makes inexplicable jumps and doesn't appear to use some of the things brought up.

    Here's the theorem and proof in the text (shortened with comment).

    [tex] \mbox{Theorem: If } \Sigma \cup \{\lnot P\} \vdash \{Q\} \mbox{ and }\Sigma \cup \{\lnot P\} \vdash \{\lnot Q\} \mbox{ then } \Sigma \vdash \{P\}.[/tex]

    [tex] \mbox{Proof: }\Sigma \vdash \{P \lor \lnot P\} \mbox{ ,(1) [I understand this result]. }[/tex]
    [tex]\Sigma \cup \{P\} \vdash \{P\} \mbox{,(2) [By Axiom]. }[/tex]
    [tex]\Sigma \vdash \{\lnot P,P\} \mbox{ ,(3) [I understand this result]. }[/tex]

    [tex]\mbox{Since }\Sigma \cup \{\lnot P\} \vdash \{Q\} \mbox{ and }\Sigma \cup \{\lnot P\} \vdash \{\lnot Q\} \mbox{ ,then }\Sigma \cup \{\lnot P\} \vdash \{P\}\mbox{ ,(4) [?]. }[/tex]

    [tex]\Sigma \cup \{P \lor \lnot P\} \vdash \{P\} \mbox{ ,(5) [Follows from (4)]. }[/tex]
    [tex]\Sigma \vdash \{P\} \mbox{ ,(6) [Follows from (5)]. }[/tex]

    It doesn't get much clearer than this in the text. There should be no errors.
  2. jcsd
  3. Jan 18, 2013 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    There are some widely recognized conventions in logic but nobody is going to know what Axiom 2 says unless you at least reveal what book you are reading. (And even with that, getting an answer will depend on someone else having a copy of the book.)
  4. Jan 18, 2013 #3
    These are deductions. The axiom is just the name given to say that a sentence P can be formally proved by sentence P itself.

    I'll clarify rules later tonight.
  5. Jan 18, 2013 #4
    Suppose that proof by contradiction was logically invalid...
  6. Jan 20, 2013 #5
    Apologies for the late post. Something's come up.

    Anyways, here are the "legal" rules of this particular deductive system:

    [tex] \mbox{(1) If } P \in \Sigma \mbox{, then } \Sigma \vdash \{P\}[/tex]
    [tex] \mbox{(2) If } \Sigma \cup \{P,Q\} \vdash \{R\} \mbox{, then } \Sigma \cup \{P \land Q\} \vdash \{R\}[/tex]
    [tex] \mbox{(3) If } \Sigma \vdash \{P\} \mbox{ and } \Sigma \vdash \{Q\} \mbox{, then } \Sigma \vdash \{P \land Q \}[/tex]
    [tex] \mbox{(4) If } \Sigma \cup \{P\} \vdash \{R\} \mbox{ and } \Sigma \cup \{Q\} \vdash \{R\} \mbox{, then } \Sigma \cup \{P \lor Q\} \vdash \{R\} [/tex]
    [tex] \mbox{(5) If } \Sigma \vdash \{P\} \mbox { or } \Sigma \vdash \{Q\} \mbox{, then } \Sigma \vdash \{P \lor Q\} [/tex]
    [tex] \mbox{(6) If } \Sigma \vdash \{P\} \mbox{ and } \Sigma \vdash \{P \rightarrow Q\} \mbox{, then } \Sigma \vdash \{Q\} [/tex]
    [tex] \mbox{(7) If } \Sigma \cup \{P\} \vdash \{Q\} \mbox{, then } \Sigma \vdash \{P \rightarrow Q\}[/tex]
    [tex] \mbox{(8) If } \Sigma \vdash \{P \lor Q\} \mbox{, then } \Sigma \cup \{\lnot P\} \vdash \{Q\} [/tex]
    [tex] \mbox{(9) If } \Sigma \cup \{P\} \vdash \{Q\} \mbox{, then } \Sigma \vdash \{\lnot P \lor Q\}[/tex]

    Double checked to make sure no errors were present. (1) is the "axiom deduction".

    The only part of the proof I don't understand is how they obtained part 4.
    I'll be working on this in the mean time.

    @Number Nine, perhaps the title is a little misleading. I am trying to understand the proof of the 'proof by contradiction' method using the nine rules of deduction. Proving this by contradiction would result in a (cyclic proof?).
  7. Jan 20, 2013 #6
    [tex]\Sigma \vdash \{\lnot P \lor P\} \mbox{ ,(3) [I understand this result]. }[/tex]

    I would like to clarify that its a [tex]\lor[/tex] and not a comma (,)

    Edit: I solved the problem. I understand the proof in detail now.

    The proof does not need lines 1,2, and 3.
    Last edited: Jan 20, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook