8 CHAPTER 1. BASIC NOTIONS

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 1.2.5 yields the conclusion. ■

In fact, the countable union of countable sets is also at most countable.

Theorem 1.2.9 Let Ai be a countable set. Thus Ai ={

rij

}∞

j=1. Then ∪∞

i=1Ai is also

at most a countable set. If it is an infinite set, then it is countable.

Proof: This is proved like Theorem 1.2.7 arrange ∪∞i=1Ai as follows.

r11 r1

2 r13 · · ·

r21 r2

2 r23 · · ·

r31 r3

2 r33 · · ·

......

...

Now take a route through this rectangular array as in Theorem 1.2.7, identifying an enumer-ation in the order in which the displayed elements are encountered as done in that theorem.Thus there is an onto mapping from N to ∪∞

i=1Ai and so ∪∞i=1Ai is at most countable, mean-

ing its elements can be enumerated. However, if any of the Ai is infinite or if the union is,then there is an onto map from ∪∞

i=1Ai onto N and so from Corollary 1.2.5, there would bea one to one and onto map between N and ∪∞

i=1Ai. ■Note that by induction this shows that if you have any finite set whose elements are

countable sets, then the union of these is countable.

1.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.

Definition 1.3.1 Let S be a set. ∼ is an equivalence relation on S if it satisfies thefollowing axioms.

1. x∼ x for all x ∈ S. (Reflexive)

2. If x∼ y then y∼ x. (Symmetric)

3. If x∼ y and y∼ z, then x∼ z. (Transitive)

Definition 1.3.2 [x] denotes the set of all elements of S which are equivalent to xand [x] is called the equivalence class determined by x or just the equivalence class of x.

With the above definition one can prove the following simple theorem.