1.2. THE SCHRODER BERNSTEIN THEOREM 7

The property of being at most countable is often referred to as being countable becausethe question of interest is normally whether one can list all elements of the set, designatinga first, second, third etc. in such a way as to give each element of the set a natural number.The possibility that a single element of the set may be counted more than once is often notimportant.

Theorem 1.2.7 If X and Y are both at most countable, then X ×Y is also at mostcountable. 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 1.2.5, there exists a one to one and onto mappingfrom X×Y to N. ■

Note that by induction, ∏ni=1 Xi is at most countable if each Xi is.

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