• Klungo
In summary, the proof by contradiction method states that if we have a set of premises that lead to both Q and ¬Q being true, then the original premise of ¬P must be false and thus P must be true. This is proven using the nine rules of deduction, particularly rule 8 which allows us to introduce a disjunction (¬P∨P) in order to reach the desired conclusion.
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).

$$\mbox{Theorem: If } \Sigma \cup \{\lnot P\} \vdash \{Q\} \mbox{ and }\Sigma \cup \{\lnot P\} \vdash \{\lnot Q\} \mbox{ then } \Sigma \vdash \{P\}.$$

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

$$\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) [?]. }$$

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

It doesn't get much clearer than this in the text. There should be no errors.

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

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.

Suppose that proof by contradiction was logically invalid...

Apologies for the late post. Something's come up.

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

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

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 said:
$$\Sigma \vdash \{\lnot P,P\} \mbox{ (line 3)}$$
It doesn't get much clearer than this in the text. There should be no errors.

$$\Sigma \vdash \{\lnot P \lor P\} \mbox{ ,(3) [I understand this result]. }$$

I would like to clarify that its a $$\lor$$ 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:

## 1. What is the concept of proof by contradiction?

Proof by contradiction is a method of mathematical proof in which a statement is proven to be true by assuming its opposite to be true and arriving at a contradiction. This contradiction shows that the original statement must be true.

## 2. How does proof by contradiction differ from other methods of proof?

Proof by contradiction differs from other methods of proof, such as direct proof or proof by induction, in that it works backwards from a false assumption to arrive at the truth. It is a powerful tool for proving statements that may be difficult to prove directly.

## 3. Can any statement be proven using proof by contradiction?

No, not all statements can be proven using proof by contradiction. This method of proof is most effective for proving statements that are logically equivalent to their negations, or statements that can be reduced to a contradiction.

## 4. How can I recognize when to use proof by contradiction?

There is no set formula for recognizing when to use proof by contradiction, but it can be helpful to look for statements that involve "if...then" or "for all" constructions. Additionally, if you have attempted to prove a statement using other methods and have reached a dead end, proof by contradiction may be a good approach to try.

## 5. Are there any risks or limitations to using proof by contradiction?

While proof by contradiction can be a powerful tool, it is important to ensure that the contradiction you arrive at is not a result of a mistake or error in your reasoning. Additionally, it may not be the most efficient method for proving certain statements, so it is important to consider other proof techniques as well.

• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
• General Math
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
24
Views
1K
• Precalculus Mathematics Homework Help
Replies
32
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
• General Math
Replies
1
Views
1K
• Calculus
Replies
9
Views
2K
• General Math
Replies
3
Views
929
• General Math
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K