# Proof by Contradiction and Contrapositive

Mathematics I · Mathematical Language and Reasoning · https://tryals.app/learn/mathematics-i/proof-by-contradiction-and-contrapositive

## Proof by Contrapositive

Sometimes a direct proof is awkward, so we use indirect techniques. **Proof by contrapositive** proves **if $p$ then $q$** by proving the equivalent statement **if $\neg q$ then $\neg p$**.

Use this when negating the conclusion gives a better starting point. 

**Example:** To prove "if $n^2$ is even, then $n$ is even," prove the contrapositive: "if $n$ is odd, then $n^2$ is odd."

| Step | Action |
| --- | --- |
| **Setup** | Let $n = 2k+1$ (odd) |
| **Square** | $n^2 = 4k^2 + 4k + 1$ |
| **Result** | $n^2 = 2(2k^2 + 2k) + 1$ (odd) |

## Proof by Contradiction

**Proof by contradiction** (**reductio ad absurdum**) assumes the target statement is **false**, then derives a logical **contradiction** (like $0 = 1$). Valid steps cannot lead to a contradiction, so the original statement must be true.

**Example ($\sqrt{2}$ is irrational):** Assume $\sqrt{2} = a/b$ in lowest terms. Squaring gives $a^2 = 2b^2$, forcing $a$ and $b$ both even, which contradicts lowest terms.

| Technique | Structure | Goal |
| --- | --- | --- |
| **Contrapositive** | Prove $\neg q \to \neg p$ | Direct conditional |
| **Contradiction** | Assume $\neg (\text{statement})$ | Find any absurdity |

**Pitfall:** Don't confuse them. Contrapositive proves an equivalent conditional directly. Contradiction assumes the whole statement false to hunt for an impossibility.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Order the steps of the classic proof by contradiction that the square root of 2 is irrational.

**Answer:**

1. Assume the square root of 2 is rational
2. Write it as a fraction a/b in lowest terms
3. Square and rearrange to get a squared = 2 b squared
4. Deduce that a is even, so a = 2k, giving b squared = 2 k squared
5. Deduce that b is also even, contradicting 'lowest terms'
6. Conclude the square root of 2 is irrational

**Why:** Assume the negation, derive consequences until something impossible appears, then conclude the assumption was false. The contradiction here is that a and b are both even despite being in lowest terms, so no such fraction exists.

Page: https://tryals.app/practice/mathematics-i/proof-by-contradiction-and-contrapositive/order-the-steps-of-the-classic-proof-by-contradiction-that-the-square

### 2. Sort each opening line by the proof technique it belongs to.

**Answer:**

- Direct proof: Assume p holds; we show q follows
- Contrapositive: Assume q fails; we show p must fail too
- Contradiction: Suppose, for the sake of argument, that the statement is false, Assume there is no largest prime is false, i.e. assume finitely many primes

**Why:** A direct proof assumes the hypothesis. The contrapositive assumes the conclusion fails and derives that the hypothesis fails. Contradiction assumes the entire statement is false and hunts for an impossibility, the distinction between o2 and o3 is subtle but real.

Page: https://tryals.app/practice/mathematics-i/proof-by-contradiction-and-contrapositive/sort-each-opening-line-by-the-proof-technique-it-belongs-to

### 3. Select every statement that is a CORRECT negation of the one shown beside it.

A. 'Some x is prime' -> 'No x is prime'
B. 'x > 3' -> 'x is at most 3'
C. 'All swans are white' -> 'No swan is white'
D. 'x > 3' -> 'x < 3'
E. 'All swans are white' -> 'Some swan is not white'

**Answer:** A. 'Some x is prime' -> 'No x is prime'; B. 'x > 3' -> 'x is at most 3'; E. 'All swans are white' -> 'Some swan is not white'

**Why:** Correct negations: 'some swan is not white', 'no x is prime', and 'x is at most 3'. Option 2 overshoots (denying all does not assert none) and option 4 forgets x = 3, which satisfies neither 'x > 3' nor 'x < 3'.

Page: https://tryals.app/practice/mathematics-i/proof-by-contradiction-and-contrapositive/select-every-statement-that-is-a-correct-negation-of-the-one-shown

### 4. Euclid proved there are infinitely many primes by assuming a finite list and building N = p₁p₂…pₖ + 1. Why does that one construction settle it?

A. Because the construction can be repeated indefinitely, generating new primes forever
B. Because N leaves remainder 1 on every prime in the supposedly complete list
C. Because N is larger than every prime in the list, and larger numbers must be prime
D. Because N is itself always prime, which the list omitted

**Answer:** B. Because N leaves remainder 1 on every prime in the supposedly complete list

**Why:** Every listed prime leaves remainder 1, so none divides N, and N has *some* prime factor, which is therefore missing from a list assumed to hold them all. Option 2 is the standard misremembering: N is often composite, and the argument never needed it to be prime.

Page: https://tryals.app/practice/mathematics-i/proof-by-contradiction-and-contrapositive/euclid-proved-there-are-infinitely-many-primes-by-assuming-a-finite

### 5. Proof by contrapositive and proof by contradiction both begin by assuming a negation. What distinguishes them, and why is the contrapositive usually preferred where both apply?

A. Contrapositive works only for statements about integers, while contradiction applies generally.
B. They are the same technique under two names, and the preference is purely stylistic.
C. Contradiction assumes ¬q and derives ¬p, while contrapositive assumes both p and ¬q - so contradiction is the simpler of the two.
D. Contrapositive assumes ¬q and derives ¬p; contradiction assumes both.

**Answer:** D. Contrapositive assumes ¬q and derives ¬p; contradiction assumes both.

**Why:** A contrapositive proof carries one assumption and works toward a named target; a contradiction proof carries two and hunts for any absurdity at all. Contradiction earns its place where there is no implication to contrapose, the irrationality of √2 being the standard case, since there is no q to negate.

Page: https://tryals.app/practice/mathematics-i/proof-by-contradiction-and-contrapositive/proof-by-contrapositive-and-proof-by-contradiction-both-begin-by

### 6. A conditional and its contrapositive always have the same truth value.

**Answer:** True

**Why:** True. 'If p then q' and 'if NOT q then NOT p' agree in all four rows, which is exactly why proving the contrapositive proves the original. The converse and inverse enjoy no such guarantee.

Page: https://tryals.app/practice/mathematics-i/proof-by-contradiction-and-contrapositive/a-conditional-and-its-contrapositive-always-have-the-same-truth-value