6Real numbers
IA Numbers and Sets
6.1 Construction of numbers
Construction of natural numbers
Our construction of natural numbers will include 0.
Definition
(Natural numbers)
.
The natural numbers
N
is defined by Peano’s
axioms. We call a set
N
“natural numbers” if it has a special element 0 and a
map S : N → N that maps n to its “successor” (intuitively, it is +1) such that:
(i) S(n) 6= 0 for all n ∈ N
(ii) For all n, m ∈ N, if S(n) = S(m), then n = m.
(iii)
For any subset
A ⊆ N
, if 0
∈ A
and “
n ∈ A ⇒ S
(
n
)
∈ A
, then in fact
A = N.
The last axiom is the axiom of induction.
We write 1 =
S
(0)
,
2 =
S
(1), 3 =
S
(2) etc. We can (but will not) prove that
the axiom of induction allows us to define functions on
N
recursively (cf. IID
Logic and Set Theory). Assuming this, we can define addition and multiplication
recursively by
n + 0 = n n × 0 = 0
n + S(m) = S(n + m) n × S(m) = n × m + n
We can show by induction that these satisfy the usual rules (e.g. associativity,
distributivity).
We can construct this explicitly by 0 =
∅
, 1 =
{
0
}
, 2 =
{
0
,
1
}
etc. In general,
we define
S
(
n
) =
{n} ∪ n
. Note that this is in some sense a circular definition,
since we are defining the natural numbers recursively, but to do recursion, we
need the natural numbers. Also, it is not clear how we can show this satisfies
the axioms above. To actually do this properly, we will need to approach this in
a slightly different way, and the details are better left for the IID Logic and Set
Theory course.
Construction of integers
Definition
(Integers)
. Z
is obtained from
N
by allowing subtraction. Formally,
we define
Z
to be the equivalence classes of
N ×N
under the equivalence relation
(a, b) ∼ (c, d) if and only if a + d = b + c.
Intuitively, we think of (a, b) as a − b.
We write a for [(a, 0)] and −a for [(0, a)], and define the operations by
(a, b) + (c, d) = (a + c, b + d)
(a, b) × (c, d) = (ac + bd, bd + ad).
We can check that these are well-defined and satisfy the usual properties.
Construction of rationals
Definition
(Rationals)
. Q
is obtained from
Z
by allowing division. Formally,
we define Q to be the equivalence classes of Z × N under the relation
(a, b) ∼ (c, d) if and only if ad = bc.
We write
a
b
for [(a, b)]. We define
(a, b) + (c, d) = (ad + bc, bd)
(a, b) × (c, d) = (ac, bd).
We can check that these are well-defined and satisfy the usual properties.
Algebraically, we say Q is a “totally ordered field”.
Definition
(Totally ordered field)
.
A set
F
equipped with binary operations
+, × and relation ≤ is a totally ordered field if
(i) F is an additive abelian group with identity 0.
(ii) F \{0} is a multiplicative abelian group with identity 1.
(iii) Multiplication is distributed over addition: a(b + c) = ab + ac.
(iv) ≤ is a total order.
(v) For any p, q, r ∈ F , if p ≤ q, then p + r ≤ q + r.
(vi) For any p, q, r ∈ F , if p ≤ q and 0 ≤ r, then pr ≤ qr.
Proposition. Q is a totally ordered-field.
Examples of non-totally-ordered fields include
Z
p
, which is a field but not
totally ordered.
Proposition. Q
is densely ordered, i.e. for any
p, q ∈ Q
, if
p < q
, then there is
some r ∈ Q such that p < r < q.
Proof. Take r =
p+q
2
.
However, Q is not enough for our purposes.
Proposition. There is no rational q ∈ Q with q
2
= 2.
Proof.
Suppose not, and (
a
b
)
2
= 2, where
b
is chosen as small as possible. We
will derive a contradiction in four ways.
(i) a
2
= 2
b
2
. So
a
is even. Let
a
= 2
a
0
. Then
b
2
= 2
a
02
. Then
b
is even as
well, and b = 2b
0
. But then
a
b
=
a
0
b
0
with a smaller b
0
. Contradiction.
(ii)
We know that
b
is a product of primes if
b 6
= 1. Let
p | b
. Then
a
2
= 2
b
2
.
So p | a
2
. So p | a. Contradict b minimal.
(iii)
(Dirichlet) We have
a
b
=
2b
a
. So
a
2
= 2
b
2
. For any,
u, v
, we have
a
2
v
= 2
b
2
v
and thus
uab
+
a
2
v
=
uab
+ 2
b
2
v
. So
a
b
=
au+2bv
bu+av
. Put
u
=
−
1
, v
= 1.
Then
a
b
=
2b−a
a−b
. Since
a <
2
b, a − b < b
. So we have found a rational with
smaller b.
(iv)
Same as 3, but pick
u, v
so
bu
+
av
= 1 since
a
and
b
are coprime. So
a
b
is
an integer.
Construction of real numbers
As shown above, the rational numbers don’t have all the numbers we need. What
exactly do we mean by “numbers are missing”? We might want to say that the
problem is that not all polynomial equations have solutions. However, this is
not the real problem. First of all, even if we are working with the reals, not all
equations have solutions, e.g.
x
2
+ 1 = 0. Also, some real numbers such as
π
are not solutions to polynomial equations (with integer coefficients), but we still
want them.
The real problem is expressed in terms of least upper bounds, or suprema.
Definition
(Least upper bound/supremum and greatest lower bound/infimum)
.
For an ordered set
X
,
s ∈ X
is a least upper bound (or supremum) for the set
S ⊆ X, denoted by s = sup S, if
(i) s is an upper bound for S, i.e. for every x ∈ S, we have x ≤ s.
(ii) if t is any upper bound for S, then s ≤ t.
Similarly,
s ∈ X
is a greatest lower bound (or infimum) if
s
is a lower bound and
any lower bound t ≤ s.
By definition, the least upper bound for S, if exists, is unique.
The problem with
Q
is that if we let
S
=
{q ∈ Q
:
q
2
<
2
}
, then it has no
supremum in Q.
Recall that
Q
is a totally ordered field. We will define the real numbers
axiomatically to be a totally ordered field without this problem.
Definition
(Real numbers)
.
The real numbers is a totally ordered field contain-
ing Q that satisfies the least upper bound axiom.
Axiom (Least upper bound axiom). Every non-empty set of the real numbers
that has an upper bound has a least upper bound.
We have the requirement “non-empty” since every number is an upper bound
of ∅ but it has no least upper bound.
We will leave the construction to the end of the section.
Note that
Q
is a subset of
R
, in the sense that we can find a copy of
Q
inside
R
. By definition of a field, there is a multiplicative identity 1
∈ R
. We can then
define the natural numbers by
n = 1 + ··· + 1
| {z }
n times
.
We can then define the negative integers by letting
−n
be the additive inverse of
n
. Then
1
n
is the multiplicative inverse of
n
(for
n 6
= 0), and
m
n
is just
m
copies
of
1
n
added together. This is our canonical copy of Q.
Corollary.
Every non-empty set of the real numbers bounded below has an
infimum.
Proof.
Let
S
be non-empty and bounded below. Then
−S
=
{−x
:
x ∈ S}
is a
non-empty set bounded above, and inf S = −sup(−S).
Alternatively, we can prove it just using the ordering of R:
Proof.
Let
S
be non-empty and bounded below. Let
L
be the set of all lower
bounds of
S
. Since
S
is bounded below,
L
is non-empty. Also,
L
is bounded
above by any member of S. So L has a least upper bound sup L.
For each
x ∈ S
, we know
x
is an upper bound of
L
. So we have
sup L ≤ x
by definition. So sup L is indeed a lower bound of S. Also, by definition, every
lower bound of S is less than (or equal to) sup L. So this is the infimum.
Now the set {q ∈ Q : q
2
< 2} has a supremum in R (by definition).
We make some useful definitions.
Definition
(Closed and open intervals)
.
A closed interval [
a, b
] with
a ≤ b ∈ R
is the set {x ∈ R : a ≤ x ≤ b}.
An open interval (a, b) with a ≤ b ∈ R is the set {x ∈ R : a < x < b}.
Similarly, we can have [
a, b
) =
{x ∈ R
:
a ≤ x < b}
and (
a, b
] =
{x ∈ R
:
a <
x ≤ b}.
Example.
Let
S
= [0
,
1]. Then
S 6
=
∅
. Also
S
has an upper bound, e.g. 2.
Hence sup S exists.
To find it explicitly, notice that 1 is an upper bound for
S
by definition, and
if
t <
1, then
t
is not an upper bound for
S
since 1
∈ S
but 1
6≤ t
. So every
upper bound is at least 1 and therefore 1 is the supremum of S.
Now let
T
= (0
,
1). Again
T
is non-empty and has an upper bound (e.g.
2). So again
sup T
exists. We know that 1 is an upper bound. If
t <
0, then
0
.
5
∈ S
but
s 6≤ t
. So
t
is not an upper bound. Now suppose 0
≤ t <
1, then
0
< t <
1+t
2
<
1 and so
1+t
2
∈ S
but
1+t
2
6≤ t
. So
t
is not an upper bound. So
sup T = 1.
Note that these cases differ by
sup S ∈ S
but
sup T 6∈ T
.
S
has a maximum
element 1 and the maximum is the supremum.
T
doesn’t have a maximum, but
the supremum can still exist.
The real numbers has a rather interesting property.
Theorem
(Axiom of Archimedes)
.
Given
r ∈ R
, there exists
n ∈ N
with
n > r
.
This was considered an axiom by Archimedes but we can prove this with the
least upper bound axiom.
Proof.
Assume the contrary. Then
r
is an upper bound for
N
.
N
is not empty
since 1
∈ N
. By the least upper bound axiom,
s
=
sup N
exists. Since
s
is the
least upper bound for
N
,
s −
1 is not an upper bound for
N
. So
∃m ∈ N
with
m > s −
1. Then
m
+ 1
∈ N
but
m
+ 1
> s
, which contradicts the statement
that s is an upper bound.
Notice that every non-empty set
S ∈ R
which is bounded below has a greatest
lower bound (or infimum). In particular, we have
Proposition. inf{
1
n
: n ∈ N} = 0.
Proof.
Certainly 0 is a lower bound for
S
. If
t >
0, there exists
n ∈ N
such that
n ≥ 1/t. So t ≥ 1/n ∈ S. So t is not a lower bound for S.
Theorem. Q
is dense in
R
, i.e. given
r, s ∈ R
, with
r < s
,
∃q ∈ Q
with
r < q < s.
Proof.
wlog assume first
r ≥
0 (just multiply everything by
−
1 if
r <
0 and
swap
r
and
s
). Since
s − r >
0, there is some
n ∈ N
such that
1
n
< s − r
. By
the Axiom of Archimedes, ∃N ∈ N such that N > sn.
Let
T
=
{k ∈ N
:
k
n
≥ s}
.
T
is not empty, since
N ∈ T
. Then by the well-
ordering principle,
T
has a minimum element
m
. Now
m 6
= 1 since
1
n
< s−r ≤ s
.
Let
q
=
m−1
n
. Since
m −
1
6∈ T
,
q < s
. If
q
=
m−1
n
< r
, then
m
n
< r
+
1
n
< s
, so
m 6∈ T , contradiction. So r < q < s.
Theorem. There exists x ∈ R with x
2
= 2.
Proof.
Let
S
=
{r ∈ R
:
r
2
≤
2
}
. Then 0
∈ S
so
S 6
=
∅
. Also for every
r ∈ S
,
we have r ≤ 3. So S is bounded above. So x = sup S exists and 0 ≤ x ≤ 3.
By trichotomy, either x
2
< 2, x
2
> 2 or x
2
= 2.
Suppose
x
2
<
2. Let 0
< t <
1. Then consider (
x
+
t
)
2
=
x
2
+ 2
xt
+
t
2
<
x
2
+ 6
t
+
t ≤ x
2
+ 7
t
. Pick
t <
2−x
2
7
, then (
x
+
t
)
2
<
2. So
x
+
t ∈ S
. This
contradicts the fact that x is an upper bound of S.
Now suppose
x
2
>
2. Let 0
< t <
1. Then consider (
x −t
)
2
=
x
2
−
2
xt
+
t
2
≥
x
2
−
6
t
. Pick
t <
x
2
−2
6
. Then (
x − t
)
2
>
2, so
x − t
is an upper bound for
S
.
This contradicts the fact that x is the least upper bound of S.
So by trichotomy, x
2
= 2.
Now let’s try to construct the real numbers from the rationals. The idea
is that each set like
{q ∈ Q
:
q
2
<
2
}
represents a “missing number”, namely
the supremum
√
2
. However, many different sets can correspond to the same
missing number, e.g.
{q ∈ Q
:
q
2
<
2
} ∪ {−
3
}
also “should have” supremum
√
2
.
So we need to pick a particular one that represents this missing number.
To do so, we pick the maximal one, i.e. a subset
S
such that for
x ∈ S
and
y ∈ Q
, if
y < x
, then
y ∈ S
(if
y
is not in
S
, we can add it to
S
, and
S ∪{y}
will
“have the same upper bound”). Each rational
q ∈ Q
can also be represented by
the set
{x ∈ Q
:
x ≤ q}
. These are known as Dedekind cuts. By convention, a
Dedekind cut is instead defined as the pair (
S, Q \ S
), and can be characterized
by the following definition:
Definition
(Dedekind cut)
.
A Dedekind cut of
Q
is a set of partition of
Q
into
L and R such that
(∀l ∈ L)(∀r ∈ R) l < r,
and R has no minimum.
The requirement that
R
has no minimum corresponds to our (arbitrary)
decision that the rationals should be embedded as
q 7→ {x ∈ q : x ≤ Q}, {x ∈ Q : x > q},
instead of q 7→ {x ∈ q : x < Q}, {x ∈ Q : x ≥ q},
We can then construct the set
R
from
Q
by letting
R
be the set of all
Dedekind cuts. The supremum of any bounded set of real numbers is obtained
by taking the union of (the left sides) of the Dedekind cuts. The definition of
the arithmetic operations is left as an exercise for the reader (to actually define
them is tedious but not hard).