54 CHAPTER 2. SOME BASIC TOPICS

Follow a path through this array as follows.

(x1,y1) → (x1,y2) (x1,y3) →↙ ↗

(x2,y1) (x2,y2)↓ ↗

(x3,y1)

Thus the first element of X×Y is (x1,y1), the second element of X×Y is (x1,y2), the thirdelement of X ×Y is (x2,y1) etc. This assigns a number from N to each element of X ×Y.Thus X×Y is at most countable.

It remains to show the last claim. Suppose without loss of generality that X is countable.Then there exists α : N→ X which is one to one and onto. Let β : X ×Y → N be definedby β ((x,y)) ≡ α−1 (x). Thus β is onto N. By the first part there exists a function fromN onto X ×Y . Therefore, by Corollary 2.2.5, there exists a one to one and onto mappingfrom X×Y to N. ■

Theorem 2.2.8 If X and Y are at most countable, then X ∪Y is at most countable.If either X or Y are countable, then X ∪Y is countable.

Proof:As in the preceding theorem,

X = {x1,x2,x3, · · ·}

andY = {y1,y2,y3, · · ·} .

Consider the following array consisting of X ∪Y and path through it.

x1 → x2 x3 →↙ ↗

y1 → y2

Thus the first element of X ∪Y is x1, the second is x2 the third is y1 the fourth is y2 etc.Consider the second claim. By the first part, there is a map fromN onto X×Y . Suppose

without loss of generality that X is countable and α : N→ X is one to one and onto. Thendefine β (y) ≡ 1, for all y ∈ Y ,and β (x) ≡ α−1 (x). Thus, β maps X ×Y onto N and thisshows there exist two onto maps, one mapping X ∪Y onto N and the other mapping N ontoX ∪Y . Then Corollary 2.2.5 yields the conclusion. ■

Note that by induction this shows that if you have any finite set whose elements arecountable sets, then the union of these is countable.

2.3 Equivalence RelationsThere are many ways to compare elements of a set other than to say two elements are equalor the same. For example, in the set of people let two people be equivalent if they have thesame weight. This would not be saying they were the same person, just that they weighedthe same. Often such relations involve considering one characteristic of the elements of aset and then saying the two elements are equivalent if they are the same as far as the givencharacteristic is concerned.