PG2.5 Proof by contradiction: √2 is irrational

Simulate

Check the claim with numbers

A number is rational if it is a fraction $\frac{p}{q}$ of integers, with $q \ne 0$ . If $\sqrt{2}$ were one, say $\sqrt{2} = \frac{p}{q}$ , then $p^2 = 2q^2$ . The cell looks for such whole numbers with $q$ up to 10,000, in exact integer arithmetic.

import math from fractions import Fraction hits, near = [], [] for q in range(1, 10_001): p = math.isqrt(2 * q * q) # the largest p with p^2 <= 2q^2 for c in (p, p + 1): d = c * c - 2 * q * q if d == 0: hits.append((c, q)) elif abs(d) == 1: near.append((c, q)) print("p/q with p^2 = 2q^2:", hits) print("near misses, p^2 - 2q^2 = 1 or -1:", near) print("(577/408)^2 - 2 =", Fraction(577, 408)**2 - 2)

⌘/Ctrl + Enter runs the cell

No fraction works, but eleven pairs come as close as whole numbers can, with $p^2 - 2q^2 = \pm 1$ . One is $\frac{577}{408}$ , whose square misses 2 by only $\frac{1}{166464}$ .

The same search for other square roots shows what success looks like.

import math for N in [2, 3, 4]: hits = [(p, q) for q in range(1, 1001) for p in [math.isqrt(N * q * q)] if p * p == N * q * q] print(f"N = {N}: fractions p/q with p^2 = N q^2: {len(hits)}, first two {hits[:2]}")

⌘/Ctrl + Enter runs the cell

For $N = 4$ every $q$ has a $p$ , since $\sqrt{4} = 2 = \frac{2}{1}$ . For 2 and 3 there are none. Keep $\sqrt{4}$ in mind: the proof for $\sqrt{2}$ must fail for it somewhere.

Conjecture

\sqrt{2}

Ten thousand denominators fail, but a search can never rule out a larger one. A proof must show that no fraction, of any size, squares to 2.

Proof by contradiction

"There is no fraction" is a claim about every fraction, and none of the earlier techniques starts from it. A proof by contradiction assumes the opposite and shows that it leads somewhere impossible.

Rule: Proof by contradiction

\begin{gathered} \text{assume } \neg S \\ \Downarrow \\ \text{some } R \text{ and } \neg R \\ \text{so } S \text{ is true} \end{gathered}

To prove $S$ , assume $\neg S$ , "not $S$ ", and deduce a contradiction: some $R$ and $\neg R$ together. Both cannot hold, so $\neg S$ is false, and $S$ is true.

Why this is valid: the proof shows that " $\neg S \Rightarrow (R \wedge \neg R)$ " is true, and its conclusion is always false. By lesson PG1.2, an implication with a false conclusion is true only when its hypothesis is false. So $\neg S$ is false.

The proof also uses one fact from arithmetic. Every fraction can be written in lowest terms, with no common factor above 1, by dividing top and bottom by their common factors. And since $\sqrt{2} > 0$ , a fraction equal to it can be taken with $p, q \ge 1$ .

Format 1

Reorder the steps

Here is the proof that $\sqrt{2}$ is irrational, with its lines shuffled. Put them in order.

Suppose, for a contradiction, that $\sqrt{2}$ is rational.
Then $4m^2 = 2q^2$ , so $q^2 = 2m^2$ is even, and $q$ is even too.
By lesson PG2.4, $p$ is even, so $p = 2m$ for some whole number $m$ .
Then $\sqrt{2} = \frac{p}{q}$ for whole numbers $p, q \ge 1$ with no common factor above 1.
Squaring gives $p^2 = 2q^2$ , so $p^2$ is even.
So 2 is a common factor of $p$ and $q$ , a contradiction. Hence $\sqrt{2}$ is irrational.

Format 3

Find the error

The same argument, applied to $\sqrt{4}$ , seems to show that $\sqrt{4}$ is irrational. But $\sqrt{4} = 2$ . Select the line that breaks, then say why.

Simulate

A claim of your own to prove

For $\sqrt{3}$ the proof needs a fact about multiples of 3 instead of even numbers. Every integer leaves a remainder of 0, 1 or 2 when divided by 3. The cell prints $n$ , its remainder, $n^2$ and the remainder of $n^2$ .

import math for n in range(0, 9): print(n, n % 3, n**2, n**2 % 3) hits = [(p, q) for q in range(1, 10_001) for p in [math.isqrt(3 * q * q)] if p * p == 3 * q * q] print("p/q with p^2 = 3q^2, q up to 10,000:", hits)

⌘/Ctrl + Enter runs the cell

The square has remainder 0 only when $n$ does, and remainder 1 otherwise. So it seems that if $n^2$ is a multiple of 3, then so is $n$ . No fraction with denominator up to 10,000 squares to 3.

Conjecture

n

Nine values of $n$ and ten thousand denominators agree. Prove the fact about multiples of 3 first, then use it as lesson PG2.4 was used above.

Format 4

Write it

Prove both claims. For the first, prove the contrapositive by cases. For the second, argue by contradiction, using the first claim.

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

\neg S

Proof by contradiction: √2 is irrational

Check the claim with numbers

Proof by contradiction

Rule: Proof by contradiction

Reorder the steps

Find the error

A claim of your own to prove

Write it

Summary card

Free further reading