Home / Courses / Intro to Proofs / Unit 4

Intro to Proofs Unit 4: Contrapositive and Contradiction

Indirect proofs handle statements that resist a direct attack. Contrapositive proof flips a conditional into an easier one, and contradiction shows the opposite of a claim is impossible.

Covers: Proof by contrapositive, Choosing a proof method, Proof by contradiction, Irrationality proofs, Infinitely many primes, If-and-only-if proofs, Counterexamples and non-constructive proofs

Study guide

Because P → Q is equivalent to ¬Q → ¬P, you can prove a conditional by assuming the conclusion is false and showing the hypothesis must be false. This helps when the negated conclusion is easier to work with. For 'if n² is even, then n is even', a direct proof starts with n² = 2k and gets stuck, since there is no simple formula for n. The contrapositive, 'if n is odd, then n² is odd', starts from n = 2k + 1 and finishes with one line of algebra. Always state clearly at the start that you are proving the contrapositive, and write it out explicitly.

Proof by contradiction proves a statement S by assuming ¬S and deriving something impossible, a statement R together with ¬R. For a conditional P → Q, assume P and ¬Q together. The classic example is the irrationality of √2: suppose √2 = a/b in lowest terms; then a² = 2b², so a is even; writing a = 2c gives b² = 2c², so b is even too, contradicting lowest terms. Contradiction is the natural tool for 'there is no...' and 'is irrational' statements, because their negations hand you a concrete object to work with.

Euclid's proof that there are infinitely many primes is another model contradiction. Assume the primes are exactly p₁, ..., pₖ and let N = p₁p₂⋯pₖ + 1. Each pᵢ leaves remainder 1 when dividing N, so N has a prime factor missing from the list, a contradiction. Note that N need not itself be prime: 2·3·5·7·11·13 + 1 = 30031 = 59 × 509. A key lemma in many of these proofs is Euclid's lemma: if a prime p divides ab, then p divides a or p divides b, and in particular p | a² implies p | a.

A biconditional P ↔ Q needs two proofs, one for each direction, and either direction may be done directly, by contrapositive, or by contradiction. Be careful not to prove one direction twice by pairing a statement with its own contrapositive. To disprove a universal claim, give a counterexample, such as 2¹¹ − 1 = 2047 = 23 × 89 against 'p prime implies 2ᵖ − 1 prime'. Some existence proofs are non-constructive: they show an object exists, often by cases, without identifying it, as in the argument that some irrational a and b have aᵇ rational.

Key ideas

• P → Q and ¬Q → ¬P are equivalent, so proving either proves both.
• Use the contrapositive when the negated conclusion gives a better starting point.
• In a contradiction proof of P → Q, assume P and ¬Q together.
• A contradiction is any statement of the form R ∧ ¬R.
• Irrationality and 'no such object' claims are natural for contradiction.
• An if-and-only-if proof needs both directions.
• Non-constructive proofs show existence without producing the object.

Formulas and rules

Common mistakes

• Assuming the conclusion is false but forgetting to keep the hypothesis in a contradiction proof.
• Proving the inverse ¬P → ¬Q instead of the contrapositive ¬Q → ¬P.
• Claiming Euclid's number N must itself be prime.
• Proving one direction of an iff twice by using its contrapositive.
• Forgetting to assume lowest terms in an irrationality proof, so no contradiction appears.

Before the test, make sure you can

• Write the contrapositive of a conditional and prove it directly.
• Explain when contrapositive or contradiction is the better method.
• Prove that √2 (or √3) is irrational by contradiction.
• Reproduce Euclid's proof that there are infinitely many primes.
• Prove both directions of an if-and-only-if statement.
• Disprove false claims with explicit, verified counterexamples.
• Distinguish constructive from non-constructive existence proofs.

Words to know

Proof by contrapositive

Proving P → Q by proving ¬Q → ¬P.

Proof by contradiction

Proving S by showing ¬S leads to a contradiction.

Contradiction

A statement R ∧ ¬R, which can never be true.

Irrational number

A real number that cannot be written as a/b with integers a, b and b ≠ 0.

Lowest terms

A fraction a/b where a and b share no common factor greater than 1.

Euclid's lemma

If a prime divides a product, it divides at least one factor.

Euclid's theorem

There are infinitely many primes.

Biconditional proof

A proof of P ↔ Q consisting of proofs of P → Q and Q → P.

Counterexample

A specific case showing a universal statement is false.

Constructive proof

An existence proof that explicitly produces the object.

Non-constructive proof

An existence proof that shows an object exists without identifying it.

Reductio ad absurdum

Latin name for proof by contradiction: reduce the assumption to an absurdity.

Mersenne number

A number 2ⁿ − 1; prime n does not guarantee it is prime.

Fundamental Theorem of Arithmetic

Every integer greater than 1 factors into primes uniquely, up to order.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.