630 CHAPTER 32. MEASURES AND INTEGRALS

Definition 32.1.1 A set S is said to be countable if there is a function f : N → Swhich is onto. This means you can assign a positive integer to each element of S. In otherwords, you could write S = ∪∞

k=1 {sk}.If X ,Y are countable sets, then so is X ×Y.

Proof: This follows from the diagram in which X = {xk} and Y ={

y j}

(x1,y1) (x1,y2) (x1,y3) (x1,y4) · · ·(x2,y1) (x2,y2) (x2,y3) (x2,y4) · · ·(x3,y1) (x3,y2) (x3,y3) (x3,y4) · · ·

......

......

Now pick a route through this doubly infinite array of ordered pairs:

(x1,y1)(x2,y1)(x1,y2)(x3,y1)(x2,y2)(x1,y3) · · ·

You will see the pattern if you begin with the sequence just shown. Give an ordered pairthe number which corresponds to its order in the above listing process. Thus you pick upthe entire X ×Y, giving each ordered pair a number from N.

Lemma 32.1.2 If A,B are countable, so is A∪B. If A is countable and if  is a subsetof A, then  is countable also.

Proof: Consider the array

a1 a2 a3 a4 · · ·b1 b2 b3 b4 · · ·

Then list them as follows a1,b1,a2,b2, · · · . Give the number in this list the number whichcorresponds to its order in the listing process. As to the last claim, let

a1 a2 a3 a4 · · ·

be the list of things in A. Let an1 be the first in Â. If an1 , · · · ,ank have been chosen, n1 <

n2 < · · ·< nk, let ank+1 be the next in Â. Then k → ank lists all the elements of Â.

Corollary 32.1.3 The rational numbers are countable.

Proof: The positive rational numbers are included in the set of numbers m/n where m,nare positive integers. Considering a doubly infinite array like the above, the element in themth row and nth column being m/n, it follows that all positive rationals are listed. Letting0 be the first in the list shows that all nonnegative rationals are countable. Then similarly,the non positive rationals are countable. It follows from the above lemma that the rationalsare countable along with every subset of the rationals.

Corollary 32.1.4 Qp is countable and also dense in Rp.

Proof: Let x ∈ Rp. Let |ri − xi| < δ . Then |r−x| ≤(

∑pk=1 |ri − xi|2

)1/2<

√pδ .

Therefore, contained in B(x,r) is a point of Qp if we make each |ri − xi| < δ where√pδ < r. This shows Qp is dense in Rp. As to it being countable, it was shown that

Q is countable. Suppose Qm is countable. Then by Proposition 32.1.1, Qm ×Q is alsocountable. It follows by induction that Qn is countable for any n ∈ N.

Note this does not say that an infinite Cartesian product of Q is countable. This is noteven true. However, for any p ∈ N, Qp is indeed countable.