Register to reply 
Proving: Proof by Contradiction 
Share this thread: 
#1
Jan1613, 08:04 PM

P: 136

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
Jan1813, 10:28 AM

Sci Advisor
P: 3,245

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.)



#3
Jan1813, 10:36 AM

P: 136

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. 


#4
Jan1813, 05:09 PM

P: 772

Proving: Proof by Contradiction
Suppose that proof by contradiction was logically invalid...



#5
Jan2013, 08:55 PM

P: 136

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?). 


#6
Jan2013, 09:07 PM

P: 136

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. 


Register to reply 
Related Discussions  
Proof by contradiction  Precalculus Mathematics Homework  6  
Proving the proof by contradiction method  Set Theory, Logic, Probability, Statistics  9  
Proof by Contradiction  Calculus & Beyond Homework  1  
Proof by contradiction  Precalculus Mathematics Homework  1  
Proof By Contradiction  Calculus & Beyond Homework  7 