Page 117 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

we know that

s 2 = s 1 .

We have just proven the base case for a proof by induction because we have found the first two elements
of S. Now, we make the induction assumption: we have followed the same algorithm to assign the first
n natural numbers each to a different element of S . We have found

∈ S,
s 1 = z k 1 ,...,s n = z k n

and for each j =1,...,n ,

j−1
∈ S \{s i } .
i=1
k j is thesmallest naturalnumbersuchthat s j = z k j
. By the Infinite Proposition the set
We need to find s n+1 . We can do this the same way we found z k 1
n
S n = S \{s j } j=1

still has infinitely many elements. So, we can again define

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

Since S n ⊂ S ⊆ Z , and S n has infinitely many elements, we know that Y n = ∅ . Since Y n is a subset
of N , Y n is bounded below by 1. Therefore, Y n is a non-empty set of integers which is bounded below,

so by the GLB Property, Y n has a greatest lower bound, and this is its unique smallest element. We can
call this k n+1 , and the corresponding

∈ S n ,
z k n+1

by the definition of Y n . Since

n
S n = S \{s j } j=1 ,

this means that

forall j =1, 2,...,n − 1,n.
s n+1 = z k n+1 = s j

So we have assigned the next natural number n +1 to a unique element of S . Now the induction
escalator is started! Our algorithm assigns each natural number to precisely one element of S.

♥

117