34 CHAPTER 2. SET THEORY

Theorem 2.2.7 If X and Y are both at most countable, then X×Y is also at most countable.If either X or Y is countable, then X×Y is also countable.

Proof: It is given that there exists a mapping η :N→ X which is onto. Define η (i)≡ xiand consider X as the set {x1,x2,x3, · · ·}. Similarly, consider Y as the set {y1,y2,y3, · · ·}. Itfollows the elements of X×Y are included in the following rectangular array.

(x1,y1) (x1,y2) (x1,y3) · · · ← Those which have x1 in first slot.(x2,y1) (x2,y2) (x2,y3) · · · ← Those which have x2 in first slot.(x3,y1) (x3,y2) (x3,y3) · · · ← Those which have x3 in first slot.

......

......

.

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. This proves the theorem.

Theorem 2.2.8 If X and Y are at most countable, then X ∪Y is at most countable. If eitherX 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. This proves the theorem.