Question

Prove tha sum of 2 countable sets is countable

Answer 1

Theorem: If AA and BB are both countable sets, then their union A∪BA∪B is also countable.

I am trying to prove this theorem in the following manner:

Since AA is a countable set, there exists a bijective function such that f:N→Af:N→A. Similarly, there exists a bijective function g:N→Bg:N→B. Now define h:N→A∪Bh:N→A∪B such that:

h(n)={f(n+12)g(n/2), n is odd, n is evenh(n)={f(n+12), n is oddg(n/2), n is even

So in essence, h(1)=f(1)h(1)=f(1), h(2)=g(1)h(2)=g(1), h(3)=f(2)h(3)=f(2) and so on. Now we have to show that h is a bijection.

h(n) is one-one:

Proof: If h(n1)=h(n2)h(n1)=h(n2) then, if n1n1 and n2n2 are both either odd or even, we get n1=n2n1=n2. But if, suppose n1n1 is odd and n2n2 is even, this implies that:

f(n1+12)=g(n22)f(n1+12)=g(n22)

How can one deduce from this equality that n1=n2n1=n2?

I tried to think about this and realized that if A∩B=ϕA∩B=ϕ then this case is impossible as it would imply that there is a common element in both sets. On the other hand, if we assume that A∩B≠ϕA∩B≠ϕ, then either f(n1+12)∈A∪Bf(n1+12)∈A∪B or g(n22)∈A∪Bg(n22)∈A∪B....Beyond this I'm clueless.