Schinazi R.B. From Calculus to Analysis

Подождите немного. Документ загружается.

240 9 Countable and Uncountable Sets

We will prove the result for a countable union. The proof for a ﬁnite union can be

easily adapted. What we mean by countable union is that the index set of the union

is countable. The general case is

A =



i∈N

so that the index set is N. Assume that each A

is countable. For each i in N, there

exists a function f

:N →A

which is one-to-one and onto. Consider the following

subset of N:

T =



:i, j ∈N



That is, T is the set of naturals whose unique decomposition in prime numbers only

has the primes 2 and 3. The fact that each natural number has a unique factorization

in prime numbers is known as the fundamental theorem of arithmetic (for a proof,

see, for instance, ‘An introduction to Number Theory’ by Hardy and Wright (1980),

Oxford University Press).

Deﬁne the function f :T →A by





(j).

Take now a an element in A. Then there is i in N such that a belongs to A

, and

there is j in N such that f

(j) = a since we assume that f

is onto. Therefore,

a =f(2

), and f is onto. Thus, by criterion (ii) of the lemma, A is countable.

Cartesian product

If A and B are countable, then the Cartesian product A ×B deﬁned by

A ×B =



(a, b) :a ∈A, b ∈B



is also countable.

This is again a consequence of the lemma. Since A and B are countable, there

are functions f

and f

such that f

: N → A and f

: N → B are both one-to-

one and onto. Deﬁne f :N ×N →A ×B by f(i,j)= (f

(i), f

(j)).Itisleftasan

exercise to show that f is one-to-one and onto. Thus, A×B is countable if and only

if N×N is countable. We now prove that N×N is countable. Deﬁne g :N ×N →N

by g(i, j) = 2

. Then by the fundamental theorem of arithmetic, g is one-to-one.

Thus, by the lemma (iii), N ×N is countable, and so is A ×B.

Example 9.5 In Example 9.4 we have shown that Z is countable. Therefore, Z ×Z

is also countable.

The rationals

The set Q of rationals is countable.

9 Countable and Uncountable Sets 241

Let Z

∗

be the set of nonzero integers. By Application 9.1 the set Z×Z

∗

is count-

able since it is an inﬁnite subset of the countable set Z×Z. Thus, there is a function

g :N →Z ×Z

∗

which is one-to-one and onto. Consider now f : Z ×Z

∗

→Q de-

ﬁned by f(a,b)=a/b and let h :N →Q be deﬁned by h(i) =f(g(i)). By (ii) of

the lemma, it is enough to show that h is onto. Let r be a rational. Then there is

(a, b) in Z ×Z

∗

such that r =a/b. That is, r =f(a,b). Since g is onto, there is i

in N such that g(i) = (a, b). Thus, r =f(g(i))=h(i). This proves that h is onto.

Thus, Q is countable.

Example 9.6 The proof above that the set of rationals is a countable set is rather

abstract. We have proved that there is a function h :N →Q that is one-to-one and

onto, but we have not said what h looks like. We are now going to be more explicit.

We label the elements of N ×N as follows:

=(1, 1),

=(1, 2), q

=(2, 1),

=(1, 3), q

=(2, 2), q

=(3, 1),

=(1, 4), q

=(2, 3), q

=(3, 2), q

=(4, 1),

and so on. This gives an explicit way of labeling all elements of N×N and therefore

all positive rationals.

We are now going to see our ﬁrst inﬁnite set which is not countable.

Example 9.7 Let S be the set of inﬁnite sequences of 0’s and 1’s. For instance, the

sequence s = (0, 1, 0, 1, 0, 1,...) is in S. Maybe surprisingly, S is not countable:

there are too many elements in S to have one-to-one correspondence with N.Wedo

a proof by contradiction. Assume that S is countable. Then there exists a function

f : N → S which is one-to-one and onto. Note that f(1) is an inﬁnite sequence of

0’s and 1’s, and we write f(1) = (f

(1), f

(1),...), where f

(1) is 0 or 1 for each

natural i. More generally, for any i in N, we write f(i)=(f

(i), f

(i), . . .).

We now deﬁne a new sequence a in S by setting

=1 −f

(1), a

=1 −f

(2), a

=1 −f

(3),....

More generally, we set a

=1 −f

(i) for every natural i. Note that since f

(i) is 0

or 1, so is a

for every i. That is, the sequence a is in S. Since f is onto, there is

j in N such that a = f(j).Buta

= 1 − f

(j) = f

(j),soa = f(j).Wehavea

contradiction. This proves that S is not countable.

The reals

The set R of reals is not countable.

We use the result in Example 9.7 to prove this result. It is actually enough to show

that the set of reals in [0, 1] is not countable (why?). Assume, by contradiction, that

242 9 Countable and Uncountable Sets

[0, 1] is countable. Then there is a function g :[0, 1]→N which is one-to-one and

onto. Consider the function f : S →[0, 1], where S is the set of inﬁnite sequences

of 0’s and 1’s, and f is deﬁned by

f(s)=

∞



i=1

for every s =(s

,...) in S. We now show that f is one-to-one. Assume that for

a and b in S,wehavef(a)=f(b).Let

x =

∞



i=1

∞



i=1

That is, a and b are decimal representations of the real x. But we know that a decimal

representation is unique (provided that inﬁnitely many of the digits are not 9, but

here we have only 0’s and 1’s). Thus, a = b, and f is one-to-one. Deﬁne now the

function h : S →N by h(s) =g(f (s)). Assume that h(a) =h(b) for a and b in S.

That is, g(f (a)) =g(f(b)). Since g is one-to-one, we have f(a)=f(b), and since

f is one-to-one, a = b. That is, h is one-to-one. By the lemma, S is countable, but

we know that it is not by Example 9.7. Thus, we have a contradiction, and [0, 1] is

uncountable. Therefore, R is also uncountable.

Example 9.8 The set of irrational reals is uncountable.

The set of reals is the union of the set of rationals and the set of irrationals.

The set of rationals is countable. If the set of irrationals were countable, then the

union of rationals and irrationals would be countable as well (since the union of two

countable sets is countable). The reals would be countable. That is not true. Hence,

the set of irrationals is uncountable.

A natural question is: are there sets that have even more elements than the reals?

The answer is yes. Actually, it is always possible to ﬁnd sets with more elements

than a given set. Given a set X, we deﬁne the power set of X, P(X),asthesetofall

subsets of X. For instance, if X ={1, 2, 3}, then

P(X) =



∅,X,{1}, {2

}, {3}, {1, 2}, {1, 3}, {2, 3}



It is

clear that P(X) has strictly more elements than X and cannot have the same

cardinality as X. This is in fact always true.

Power sets

For any set X, its power set P(X) has a strictly larger cardinality than X in

the sense that there exists a one-to-one function from X to P(X) but no onto

function.

Note that if h :A →B is one-to-one and if

C =



h(a) :a ∈A



9 Countable and Uncountable Sets 243

then h :A →C is one-to-one and onto. Thus, A has the same cardinality as C which

is a subset of B. This is why it makes sense to say that the cardinality of A is less

than the cardinality of B if there is a one-to-one function from A to B.

We now prove that a set has a strictly smaller cardinality than its power set. If

X =∅, then P(X) ={X}. The cardinality of X is 0, and the cardinality of P(X)

is 1.

If X = ∅, then deﬁne f : X → P(X) by setting for every x in Xf(x)={x}.

Clearly, f is one-to-one.

We now show that there is no function g : X → P(X) which is onto. By contra-

diction assume that such a function exists. Deﬁne

Y =



x ∈X :x ∈g(x)



Note that Y belongs to P(X), and since g is onto, there is a in X such that g(a) =Y .

If a belongs to Y ,wehavethat

a does not belong to g(

a) but g(a) is Y , so that is

not possible. Thus, a does not belong to Y . That is, a belongs to g(a) which is Y .

This is not possible either. Thus, we have a contradiction. There is no g :X →P(X)

which is onto.

The result above shows that the cardinality of X is strictly less than its power set

P(X), whose cardinality is strictly less than its own power set P(P(X)), and so on.

Thus, it is always possible to ﬁnd a set with a strictly larger cardinality.

Exercises

1. Show that the function f : A → B is one-to-one and onto if and only if for

every b in B, there is a unique a in A such that f(a)=b.

2. Assume that f and g are bijections such that f : A → B and g : B → C.For

every a in A, deﬁne

h(a) =g



f(a)



Show that h is also a bijection.

3. Let A ⊂B and assume that A is ﬁnite. Then A and

B have the same cardinality

and only if A =B.

4. Let f :N →S for some set S.Let

F =



f(i),i∈N



Show that F is countable or ﬁnite.

5. Show that

B =



:i, j ∈N



is countable.

6. Show that if k

is a strictly increasing sequence of naturals, then k

≥i for every

i ≥1.

7. Let f

:N →A and f

:N →B be one-to-one and onto. Deﬁne f : N ×N →

A ×B by f(i,j)=(f

(i), f

(j)). Show that f is one-to-one and onto.

8. Deﬁne g :N ×N →N by g(i, j) =2

(a) Show that g is one-to-one.

244 9 Countable and Uncountable Sets

(b) Is g onto?

9. (a) Show that

=N ×N ×N =



(a,b,c):a ∈N,b∈N,c∈N



is countable.

(b) Generalize (a).

10. Assume that g :A →B and f :B →C are onto. Let h :A → C be deﬁned by

h(a) =f(g(a)). Prove that h is onto.

11. Assume that A ⊂ B and that A is inﬁnite and uncountable. Prove that B is

uncountable.

12. Is P(N) countable?

13. Given a nonempty set X,let

{0, 1}



f :f :X →{0, 1}



be the set of functions from X to {0, 1}. In this exercise we are going to show

that P(X) has the same cardinality as {0, 1}

(a) Given A a subset of X,let1

be the indicator function of A. It is deﬁned

by 1

(x) = 0ifx does not belong to A and 1

(x) = 1ifx belongs to A.

Show that 1

belongs to {0, 1}

(b) Deﬁne the function F : P(X) →{0, 1}

by F(A) = 1

for each A in

P(X). Show that F is one-to-one.

. Deﬁne

A =



x ∈X :f(x)=1



Show that f = 1

(d) Conclude.