’ 2|a| 3b 51+sign a ,

f:

b

where (a, b) = 1 and b > 0.

CHAPTER 3. SETS, FUNCTIONS AND RELATIONS

32

Theorem 3.6. A countable union of countable sets is countable. That is, if I is a

countable indexing set and Ai is countable ∀i ∈ I then i∈I Ai is countable.

Proof. Identify ¬rst I with the subset f (I) ⊆ N. De¬ne F : A ’ N by a ’ 2n 3m

where n is the smallest index i with a ∈ Ai , and m = fn (a). This is well-de¬ned and

injective (stop to think about it for a bit).

Theorem 3.7. The set of all algebraic numbers is countable.

Proof. Let Pn be the set of all polynomials of degree at most n with integral coef¬-

cients. Then the map cn xn + · · · + c1 x + c0 ’ (cn , . . . , c1 , c0 ) is an injection from Pn

to Zn+1 . Hence each Pn is countable. It follows that the set of all polynomials with

integral coef¬cients is countable. Each polynomial has ¬nitely many roots, so the set

of algebraic numbers is countable.

Theorem 3.8 (Cantor™s diagonal argument). R is uncountable.

Proof. Assume R is countable, then the elements can be listed as

r1 = n1 .d11 d12 d13 . . .

r2 = n2 .d21 d22 d13 . . .

r3 = n3 .d31 d32 d33 . . .

(in decimal notation). Now de¬ne the real r = 0.d1 d2 d3 . . . by di = 0 if dii = 0 and

di = 1 if dii = 0. This is real, but it differs from ri in the ith decimal place. So the list

is incomplete and the reals are uncountable.

Exercise: use a similiar proof to show that P (N) is uncountable.

Theorem 3.9. The set of all transcendental numbers is uncountable. (And therefore at

least non-empty!)

Proof. Let A be the set of algebraic numbers and T the set of transcendentals. Then

R = A ∪ T , so if T was countable then so would R be. Thus T is uncountable.

3.7 Bigger sets

The material from now on is starred.

Two sets S and T have the same cardinality (|S| = |T |) if there is a bijection

between S and T . One can show (the Schr¨ der-Bernstein theorem) that if there is an

o

injection from S to T and an injection from T to S then there is a bijection between S

and T .

For any set S, there is an injection from S to P (S), simply x ’ {x}. However

there is never a surjection S ’ P (S), so |S| < |P (S)|, and so

|N| < |P (N)| < |P (P (N))| < . . .

for some sensible meaning of <.

Theorem 3.10. There is no surjection S ’ P (S).

3.7. BIGGER SETS 33

Proof. Let f : S ’ P (S) be a surjection and consider X ∈ P (S) de¬ned by {x ∈

S : x ∈ f (x)}. Now ∃x ∈ S such that f (x ) = X. If x ∈ X then x ∈ f (x ) but

/ /

f (x ) = X ” a contradiction. But if x ∈ X then x ∈ f (x ) and x ∈ X ” giving a

/ /

contradiction either way.

injection surjection

f : A ’ B then there exists a g : B ’ A.

If there is an

surjection injection

g —¦ f = ιA

Moreover we can ensure that

f —¦ g = ιB

CHAPTER 3. SETS, FUNCTIONS AND RELATIONS

34

References

—¦ Hardy & Wright, An Introduction to the Theory of Numbers, Fifth ed., OUP, 1988.

This book is relevant to quite a bit of the course, and I quite enjoyed (parts of!) it.

—¦ H. Davenport, The Higher Arithmetic, Sixth ed., CUP, 1992.

A very good book for this course. It™s also worth a read just for interest™s sake.

I™ve also heard good things about Biggs™ book, but haven™t read it.

35