Proving: Proof by Contradiction


by Klungo
Tags: contradiction, proof, proving
Klungo
Klungo is offline
#1
Jan16-13, 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.
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Stephen Tashi
Stephen Tashi is offline
#2
Jan18-13, 10:28 AM
Sci Advisor
P: 3,175
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.)
Klungo
Klungo is offline
#3
Jan18-13, 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.

Number Nine
Number Nine is online now
#4
Jan18-13, 05:09 PM
P: 771

Proving: Proof by Contradiction


Suppose that proof by contradiction was logically invalid...
Klungo
Klungo is offline
#5
Jan20-13, 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?).
Klungo
Klungo is offline
#6
Jan20-13, 09:07 PM
P: 136
Quote Quote by Klungo View Post
[tex]\Sigma \vdash \{\lnot P,P\} \mbox{ (line 3)}[/tex]
It doesn't get much clearer than this in the text. There should be no errors.
[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.


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