4 Chapter 1
Slightly revised proof of theorem 1. Suppose toward contradiction that
√
2 is rational. So
√
2 = p/q for some integers p and q, and we may assume that the numerator p is chosen
as small as possible for such a representation. It follows as before that 2q
2
= p
2
, and
so p
2
and hence also p is even. So p = 2k for some k, which implies that q
2
= 2k
2
as before, and so q
2
and hence also q is even. So q = 2r for some r, and consequently
√
2 = p/q = (2k)/(2r) = k/r. We have therefore found a rational representation of
√
2
using a smaller numerator, contradicting our earlier assumption. So
√
2 is not rational.
This way of arguing, although very similar to the original argument, does not require
putting fractions in lowest terms. Furthermore, an essentially similar idea can be used to
prove that indeed every fraction can be put in lowest terms.
1.2 Lowest terms
What does it mean for a fraction p/q to be in lowest terms? It means that p and q are
relatively prime, that is, that they have no common factor, a number k > 1 that divides both
of them. I find it interesting that the property of being in lowest terms is not a property of
the rational number itself but rather a property of the fractional expression used to represent
the number. For example,
3
6
is not in lowest terms and
1
2
is, yet we say that they are equal:
3
6
=
1
2
. But how can two things be identical if they have different properties? These two
expressions are equal in that they describe the same rational number; the values of the
expressions are the same, even though the expressions themselves are different. Thus, we
distinguish between the description of a number and the number itself, between our talk
about a number and what the number actually is. It is a form of the use/mention distinction,
the distinction between syntax and semantics at the core of the subject of mathematical
logic. How pleasant to see it arise in the familiar elementary topic of lowest terms.
Lemma 2. Every fraction can be put in lowest terms.
Proof. Consider any fraction p/q, where p and q are integers and q 0. Let p
be the
smallest nonnegative integer for which there is an integer q
with
p
q
=
p
q
. That is, we
consider a representation
p
q
of the original fraction
p
q
whose numerator p
is as small as
possible. I claim that it follows that p
and q
are relatively prime, since if they had a
common factor, we could divide it out and thereby make an instance of a fraction equal to
p/q with a smaller numerator. But p
was chosen to be smallest, and so there is no such
common factor. Therefore, p
/q
is in lowest terms.
This proof and the previous proof of theorem 1 relied on a more fundamental principle,
the least-number principle, which asserts that if there is a natural number with a certain
property, then there is a smallest such number with that property. In other words, every
nonempty set of natural numbers has a least element. This principle is closely connected
with the principle of mathematical induction, discussed in chapter 4. For now, let us simply