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).