Page 116 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

∞ ,
Now we need an algorithm to assign one natural number to each element of S. Since S ⊆ Z = {z k }
k=1
and S is infinite, we know that there is some z k ∈ S . Let’s find the first k such that z k ∈ S . To do
this, we can use the greatest lower bound property of the integers. Let

Y = {k ∈ N such that z k ∈ S}.

The set Y is not empty, because S ⊆ Z , and S is infinite, so there is a z k ∈ S , and k ∈ Y . The set
Y is bounded below because Y ⊆ N, and every natural number is greater than or equal to one. So, by
the GLB Property, Y has a greatest lower bound, and this is its unique smallest element. Let’s call it k 1 .
Then, by the definition of k 1 ∈ Y ,

∈ S.
z k 1

So, the first element of S which we shall write s 1 is

.
s 1 = z k 1

The second element of S which we will write s 2 must be different from s 1 . What do we know about

S \{s 1 }?

By the Infinite Proposition, since the set {s 1 } contains one element,

S 1 = S \{s 1 }

is also an infinite set. Since S 1 ⊂ S ⊂ Z, let’s define

Y 1 = {k ∈ N such that z k ∈ S 1 }.

Since S 1 is an infinite set there must be some z k ∈ S 1 . Since each k ∈ N , the set Y 1 is also bounded
below by 1. So, Y 1 is a set of integers which is not empty and is bounded below, so by the GLB Property,
Y 1 has a greatest lower bound, and this is its unique smallest element. Let’s call it k 2 . By the definition
of k 2 ∈ Y 1 ,

∈ S 1 .
z k 2

So, we can call

,
s 2 = z k 2

and since

s 2 ∈ S 1 = S \{s 1 },

116