46 CHAPTER 3. SET THEORY

Definition 3.2.6 A set S, is finite if there exists a natural number n and a map θ

which maps {1, · · · ,n} one to one and onto S. S is infinite if it is not finite. A set S, is calledcountable if there exists a map θ mapping N one to one and onto S.(When θ maps a set Ato a set B, is written as θ : A→ B in the future.) Here N≡ {1,2, · · ·}, the natural numbers.S is at most countable if there exists a map θ : N→ S which is onto.

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 3.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 3.2.5, there exists a one to one and onto mappingfrom X×Y to N.

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

Proof: As in the preceding theorem,

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

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