# Prove by induction that the union of countable sets is countable

Say you have a set $$A_i$$ for $$i$$ in the natural numbers $$\mathbb{N}$$, and that is a countable set. Then for all natural numbers $$n$$, the union of those sets is countable.

I must prove this by induction, and I do realize that to do that, I must show that there is an injection( or surjection ) between the first two sets. Everything should follow accordingly afterwards, but I had the idea to utilize Cantor's Diagonal Argument in the inductive proof, but I am not sure how to go about defining injections for the argument in a way that shows that the sets are countable.

• So, you're trying to prove that a countable union of countable sets is countable? While that's true, I don't think proving it by induction is appropriate, as (unless I'm missing some really creative idea) induction will only ever show that finite unions of countable sets are countable. – Theo Bendit Oct 25 '18 at 2:25
• Why would you use the diagonal argument? That's a way to prove something is not countable. – Matt Samuel Oct 25 '18 at 2:27
• Also (again, unless I'm missing something really creative), Cantor's diagonal argument will only ever show a set is strictly larger than a given cardinality, not equal to a given cardinality. You'll need to construct the maps explicitly. – Theo Bendit Oct 25 '18 at 2:28
• For aall natural numbers $n$ the union of WHAT sets is countable? All of the sets $A_i$? No, must be something to do with $n$, I guess. The union of all the sets $A_i$ for $i\gt n$ is countable? It would help a lot if we know what sets you were trying to prove countable. – bof Oct 25 '18 at 9:25

Are you talking about a finite union of countable sets? If so, for the induction hypothesis write $$\cup_{i=1}^n A_i=(\cup_{i=1}^{n-1}A_i)\cup A_n.$$ Now both sets on the right hand side are countable, so there is a surjection from $$\mathbb{N}$$ to each of them. Can you turn this into a surjection from $$\mathbb{N}$$ to their union, possibly by splitting $$\mathbb{N}$$ into $$\mathbb{N}=\{2k:k\in \mathbb{N}\}\cup \{2k+1:k\in \mathbb{N}\}$$?