Page 105 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

Definition 5.4.1 An infinite set S is countable if there is an algorithm which assigns precisely one natural
number to each distinct element of the set: each distinct element of the set corresponds to precisely one
natural number, and the set is in one-to-one correspondence with the set of natural numbers. An infinite
set which is not countable is uncountable.

At this point, it may be difficult to imagine how a set could be uncountable, but we will see examples
of uncountable sets in Chapter 7.

Since each element in a countable set corresponds to precisely one natural number, it’s possible to index
any countable set S as

∞
S = {s n } n=1 ,

because precisely one natural number is assigned to precisely one element of S . So for each n ∈ N there
is a corresponding s n ∈ S , and conversely each element of S corresponds to precisely one n ∈ N .

By the definition, the set of natural numbers is countable, because we can assign each natural number
to itself. Are the integers countable? The integers consist of the natural numbers, their additive inverses,

and the additive identity. Well, it makes sense to start in the middle so we can assign the first natural
number 1 to the integer 0. Next we can assign 2 to the first positive integer 1. But if we keep going on
with positive integers we’ll never make it back to all the negative integers. So instead of continuing with
positive integers, we can go back to the first negative integer and assign 3 to −1.

Exercise: Keep doing this and see if you notice a pattern. If n is a natural number, can you write a formula
in terms of n for the integer which gets assigned to n ? When you have spent some time working on

this exercise, then you may turn the page.

Theorem 5.4.2 (Zipper Theorem). The integers are countable.

Proof: Let’s continue what we started. Now 4 gets assigned to 2, and 5 gets assigned to −2. Then 6
gets assigned to 3, and 7 gets assigned to −3. There is a pattern with the even natural numbers: if n
n
is an even natural number, then it is assigned to the positive integer . What happens if n is odd? If
2
n =1, then it is assigned to 0. If n> 1 is odd, then we know that n − 1 is an even natural number,
and it was assigned to the positive integer n−1 . By our algorithm then n is assigned to the negative
2
(n−1)
integer − . We can summarize our algorithm as follows :
2
1. The first natural number 1 is assigned to 0.
n
2. For each natural number n> 1, if n is even, then it is assigned to .
2
(n−1)
3. For each natural number n> 1, if n is odd, then it is assigned to − .
2

105