Question

Prove that if X and Y are disjoint countably infinite sets then X ∪ Y is countably infinity (can you please show the bijection from N->XUY clearly)

Answer 1

A formal proof would be something like this.

If X and Y are countable and disjoint sets, then there exist injective functions f and g from X and Y, respectively, to N.

Let C = X∪Y and define a function h : C→N as follows:

h(z) = 2f(z) , if z ∈ X

&, h(z) = 2g(z)+1 , if z ∈ Y

Then, if x≠y, we clearly have h(x)≠h(y) since if x,y∈X , this follows from the fact that f is injective (analogously for x,y∈Y) and if x∈X and y∈Y, we have that h(x) is even while h(y) is odd (analogously for x∈Y, y∈X). Hence h is an injective function from C to N and thus, by definition, C is countable.