Question

Prove that a disjoint union of any finite set and any countably infinite set is countably infinite.

Proof: Suppose A is any finite set, B is any countably infinite set, and A and B are disjoint. By definition of disjoint, A ∩ B = ∅

In case A = ∅, then A ∪ B = B, which is countably infinite by hypothesis.

Now suppose A ≠ ∅. Then there is a positive integer m so that A has m elements and there is a one-to-one correspondence f: {1, 2, 3, .., m} → A. In addition, since B is countably infinite, there is a one-to-one correspondence g: ℤ⁺ → B.

Let h: ℤ⁺ → A ∪ B be the function selected below. (Select one definition for h and use it for the rest of your answer.) We will show that h is one-to-one and onto.

Then h is one-to-one because f and g are one-to-one and A ∩ B = 0.  Further, h is onto because f and g are onto and given any element x in A ∪ B, x is in A or x is in B.

In case x is in A, then, since f is onto, there is an integer r in {1, 2, 3, ..., m} such that f(r) = x. Since r is in {1, 2, 3, ..., m}, r ≤ m, and so h(r) = _________.

In case x is in B, then, since g is onto, there is an integer s in ℤ⁺ such that g(s) = x.Let t = s + m.Then s = t − m. Also t > m+1, and thus h(t) = g(t-m)=g(s)=_________.

Therefore, h is a one-to-one correspondence from ℤ⁺ to A ∪ B, and so A ∪ B is countably infinite by definition of countably infinite.

Please write in bold letters where the ______ are.

Answer 1