Register to reply

Proving: Proof by Contradiction

by Klungo
Tags: contradiction, proof, proving
Share this thread:
Klungo
#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
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
Stephen Tashi
#2
Jan18-13, 10:28 AM
Sci Advisor
P: 3,252
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
#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
#4
Jan18-13, 05:09 PM
P: 772
Proving: Proof by Contradiction

Suppose that proof by contradiction was logically invalid...
Klungo
#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
#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