3.3. EQUIVALENCE RELATIONS 47

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 3.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. In fact, you can say that a countableunion of countable sets is countable.

Theorem 3.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 3.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 3.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 3.2.5, there would bea one to one and onto map between N and ∪∞

i=1Ai.As mentioned, in virtually all applications to analysis, the topic of main interest is “at

most countable” meaning that the elements of a set S can be listed with subscripts fromN to obtain them all. More precisely, there is a map from N onto the set S. Often peoplesimply refer to such a set as countable.

3.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 3.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)