Question

1) a) Prove that the union of two countable sets is countable.

b) Prove that the union of a finite collection of countable sets is countable.

Answer 1

a)   Let A and B be countable sets. We will consider four cases.

case 1 Suppose both A and B are finite. Then A ∪ B is finite, and hence countable.

case 2   Suppose one of A and B is finite and the other is countably infinite. Assume without loss of generality that A is finite. Since B is countably infinite, there exists a function f: B 7→ Z ⁺ which is a one-to-one correspondence. Say that f(b_i) = i, for b_i ∈ B and i ∈ Z ⁺. Let C = A − B. Thus A ∪ B = B ∪ C.

If C = ∅, then A ∪ B = B which is countably infinite. Thus assume that C 6= ∅. Suppose that C = {c1, c2, ...cn}.

Let f : B ∪ C → Z ⁺ be defined as follows: f ^' (c_j) = j and f ^' (b_i) = n + i.

Clearly, f ^' is one-to-one and onto. Thus B ∪ C is countable. But B ∪ C = A ∪ B, so A ∪ B is countable.

case 3   Suppose that both A and B are infinite and that A ∩ B = ∅. Given that A and B are both

countable, there exists functions f : Z⁺ → A and g : Z⁺ → B that are one-to-one correspondences. Consider the function h : Z⁺ → A ∪ B where h(n) = f(n/2) if n is even and h(n) = g((n + 1)/2) if n is odd. Since both f and g are one-to-one, then so is h. Similarly, since f is onto, every element in A is covered and since g is onto, every element in B is coverd, so h is onto. Therefore, h is a one-to-one correspondence, and hence h is countable.

case 4   Suppose that both A and B are infinite and that A ∩ B ≠ ∅. Let C = B − A. Then A∪B = A∪C and

A∩C = ∅. If C is countably infinite, then A∪B = A∪C is countable by the previous case. If C is finite,

then A ∪ B A ∪ C is countable by the second case. In any case, A ∪ B is countable.

b) to show that union of a finite collection of a countable set is countable

suppose A_{1 ,} A_2.........., A_K  is countable set

to show A_{1 U} A₂U.........U A_K is countable  

by induction

A_{1 U} A₂   is countable by part ( a)

let B₁ = A₁UA₂

than B₁UA₁ is also countable

suppose A_{1 U} A₂U.........U A_K-1 is countable

let B₂ =A_{1 U} A₂U.........U A_K-1

B₂UA_K is countable again by part (a)