Why is Proof by Contradiction considered an 'indirect' proof?

It is indirect because it doesn't build the conclusion from the ground up; instead, it eliminates the only other logical alternative by showing its absurdity.

Why is prime factorization a common tool in proving numbers are irrational by contradiction?

It allows mathematicians to show that the number of prime factors on one side of an equation is even while the other is odd, creating an impossible numerical identity.

What is the logical difference between a proof by contrapositive and a proof by contradiction?

Contrapositive only assumes the conclusion is false to prove the premise is false ($\neg Q \implies \neg P$). Contradiction assumes the conclusion is false AND the premises are true to derive a general logical impossibility.

When should you choose contradiction over a direct proof?

Contradiction is preferred when the statement involves proving that something is 'not' something else (like irrational) or when a direct path from the premises to the conclusion is unclear.

How does Proof by Contradiction differ from Proof by Exhaustion?

Exhaustion proves a statement by testing every possible individual case. Contradiction proves a statement by showing that the alternative is logically impossible for all cases simultaneously.

What is the danger of negating a 'for all' statement incorrectly in the first step?

If the negation is incorrect, the entire proof is invalid. For example, the negation of 'For all $x$, $P(x)$' is 'There exists at least one $x$ such that not $P(x)$,' not 'For no $x$, $P(x)$.'

What is 'circular reasoning' in a proof by contradiction?

This occurs when you assume the statement you are trying to prove is true and use it within your logical steps. A proof must only use the *negation* and existing known facts.

Why is it an error to stop the proof once a 'strange' or 'unexpected' result is found?

Mathematical intuition is not proof. The result must be a definite logical impossibility (like $2=3$) or a direct contradiction of an established rule to conclude the proof.

Define a 'Contradiction' in the context of mathematical logic.

A contradiction is a compound statement of the form $P \land \neg P$, which is always false regardless of the truth value of the individual components.

What is a 'Rational Number' definition used in these proofs?

A rational number is any number that can be expressed as $\frac{p}{q}$ where $p$ and $q$ are integers, $q \neq 0$, and usually assumed to have no common factors (coprime).

Library Podcasts

Courses

Referral & Rewards

Revision Notes

International A-Level

Proof by Contradiction

Summary

Proof by contradiction is a powerful indirect method of mathematical proof that establishes the truth of a statement by assuming its negation is true and showing that this leads to a logical impossibility or an inconsistency with established facts.

1. Definition & Core Concepts

Core Definition: A proof by contradiction (also known as reductio ad absurdum) begins by assuming that the statement to be proven is false.
Logic of Indirect Proof: Instead of showing how the premises directly lead to the conclusion, this method shows that the conclusion must be true because its absence creates a logical breakdown.
Goal of the Method: The objective is to derive a statement that is clearly false, such as $0 = 1$ or a number being both even and odd simultaneously, which invalidates the initial assumption.

A diagram showing how assuming the negation of a statement leads back to a contradiction of that assumption.

2. Underlying Principles

Law of Excluded Middle: This principle states that for any proposition, either that proposition is true or its negation is true; there is no third middle ground.
Consistency of Mathematics: The validity of the method relies on the axiom that mathematical systems must be internally consistent, meaning they cannot contain two contradictory truths.
Reductio ad Absurdum: This Latin term describes the process of reducing an argument to an 'absurdity' or a logical dead end, proving the starting premise was flawed.

3. Methods & Techniques

The Four-Step Process

Step 1: Negate the Statement: State clearly at the beginning, "Assume that the statement is false," or "Assume the negation of the statement is true."
Step 2: Logical Derivation: Use known axioms, definitions, and theorems to proceed through a series of logical deductions based on the assumption.
Step 3: Identify the Contradiction: Reach a point where your derivation contradicts a known fact, a given premise, or the initial assumption itself.
Step 4: Conclude: Declare that because the negation led to a contradiction, the original statement must be true.

4. Key Distinctions

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions