Proving: Proof by Contradiction

Klungo

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.

Stephen Tashi

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

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

Suppose that proof by contradiction was logically invalid...

Klungo

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

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