Example. Prove that
√
2 is irrational.
Suppose
√
2 is rational, i.e.
√
2 = a/b for some integers a and b with b 6= 0.
We can assume that b is positive, since otherwise we can simply change the
signs of both a and b. (Then a is positive too, although we will not need this.)
Let us choose integers a and b with
√
2 = a/b, such that b is positive and
as small as possible. (We can do this by the Well-Ordering Principle, which
says that every nonempty set of positive integers has a smallest element; see
§4.2.)
Squaring both sides of the equation
√
2 = a/b and multiplying both sides
by b
2
, we obtain a
2
= 2b
2
. Since a
2
is even, it follows that a is even. Thus
a = 2k for some integer k, so a
2
= 4k
2
, and hence b
2
= 2k
2
. Since b
2
is
even, it follows that b is even. Since a and b are both even, a/2 and b/2 are
integers with b/2 > 0, and
√
2 = (a/2)/(b/2), because (a/2)/(b/2) = a/b.
But we said before that b is as small as possible, so this is a contradiction.
Therefore
√
2 cannot be rational. 2
This particular type of proof by contradiction is known as infinite de-
scent, which is used to prove various theorems in classical number theory. If
there exist positive integers a and b such that a/b =
√
2, then the above proof
shows that we can find smaller positive integers a and b with the same prop-
erty, and repeating this process, we will get an infinite descending sequence
of positive integers, which is impossible.
Recall that in the above proof, we said
We can assume that b is positive, since otherwise we can simply
change the signs of both a and b.
Another way to write this would be
Without loss of generality, b > 0.
“Without loss of generality” means that there are two or more cases (in this
proof the cases when b > 0 and b < 0), but considering just one particular
case is enough to prove the theorem, because the proof for the other case or
cases works the same way.
3.3 Uniqueness proofs
Suppose we want to prove that the object x satisfying a certain property, if
it exists, is unique. There is a standard strategy for doing this. We let x
14