A proof using the Well-Ordering Principle
This proof uses the Well-Ordering Principle for Non-negative Integers, which is that
any non-empty subset of the non-negative integers has a least element.
Assume that √2 is rational; that is, √2 = a/b, where a and b are integers.
Then a > b since √2 > 1.
Now, 2 = a2/b2 so that a2 = 2b2. So a2 is even, implying that a is even, say a = 2a', for some integer a'. Hence, b2 = 2a'2 or √2 = b/a'. Thus, starting with a fraction representation of √2 = a/b, we get another fraction representation √2 = b/a' with a smaller numerator b < a. Repeating the argument, we get fraction representation of √2, with ever decreasing numerators. But then the set of these numerators does not have a least element; contradicting the Well-Ordering Principle. So our assumption that √2 is rational has to be false. QED
A proof using the Principle of Mathematical Induction
Noting that a proof using the
Well-Ordering Principle can usually be converted to a proof using the Principle of Mathematical Induction, and vice versa, I was pleasantly surprised that I could easily construct the following proof.
We need to show that √2 ¹ a/b for all integers a and b. That is, 2 ¹ a2/b2 for all integers a and b.
We use the Strong version of Mathematical Induction:
Let P(n) denote a property that holds for integer n.
Suppose that P(n0) is true;
and for all k ≥ n0, P(m) is true for all m with n0 ≤ m≤ k implies P(k+1) is true.
Then P(n) is true for all n ≥ n0.
In our proof here we will take n0 = 1, for we know that 2 ¹ 1/b2 for all integers b.
Suppose that 2 ¹ a2/b2, for all a, where 1 ≤a ≤n.
Suppose 2 = (n+1)2/b2. Then (n+1)2 = 2b2 so that (n+1)2 is even and hence n+1 is even, say n+1 = 2a'. Then b2 = 2a'2, or 2 = b2/(a')2; a contradiction of the induction hypothesis since b < n+1. So 2 ¹ (n+1)2/b2, and hence the statement holds for n+1. By Strong Induction, the statement holds for all n. That is, 2 ¹ a2/b2 for all integers a and b.
Hence √2 is not rational.
MathPath - "BRIGHT AND EARLY"
Send suggestions to firstname.lastname@example.org
Copyright © 2001- MathPath
Last updated - July 3, 2004