Principles of Mathematics in Operations Research

9.6 Countable and Uncountable Sets 131

Proposition 9.6.6 If s = {xi,i £ 1} is a countable class of countable sets,

then Ui£iXi is also countable. That is, countable union of countable sets are

countable.

Proof. We have /:N4/, 1-1, onto. Let Y„ — Xf(ny The elements of Yn can

be listed as a sequence. Yn = {X^,X^, • • •} Vra. Use the Cantor's counting

scheme for the union. Another counting schema is given in Figure 9.1. •

Example 9.6.7 X = [0,1) is not countable.

Every x € [0,1) has a binary expansion x = 0.aia2«3 • • • where an =

Suppose [0,1) is countable. Then, its elements can be listed as a sequence

{X^1 , X^2 , X^3 ,...}. Consider their binary expansions

X^1 = Q.a\a\a\ ...

X^2 = O.ajalal...

X^3 = O.afalal...

LetaiTpfn _/0,i/ai = l _ f 0, */ al = 1 _/0,t/oi = l

-\l,ifal=0'a2-\l,ifal=0'a3-\l,ifa^3 = 0'---

Let

x = 0.aia 2 a 3 ... e [0,1).

But this number is not contained in the list {X^1 , X^2 , X^3 ,...}

x is different from X^1 by the first digit after 0;

x is different from X^2 by the second digit after 0;

x is different from X^3 by the third digit after 0;

Therefore, x ^ Xn, Vn; since x and Xn differ in the nth digit after zero. So,

X = [0,1) is not countable.

Example 9.6.8 X = (0,1) is not countable. Since X — [0,1) is not count-

able, excluding a countable number of elements (just zero) does not change

uncountability. Thus, X = (0,1) is uncountable.

Example 9.6.9 For any open interval (a, b) we have

M)~(0,1) f : (a,b) ^ (0,1).

Refer to Figure 9.2.

Example 9.6.10 X — K is not countable. Since R ~ (—1,1), by projection
R is not countable [because (0,1) is not countable]. One way of showing 1-1
correspondence between any open interval and (0,1) is illustrated in Figure
9.3.

?