# Prove union of sets is countable [duplicate]

Question:

Let $A_{1}, A_{2}, ...$ be a sequence of sets, each of which is countable. Prove that the union of all the sets in the sequence is countable.

My attempt:

We know that for each set in the sequence, $\exists \ f: \mathbb{N} \to A_{k}$ a bijection. Now I'm not sure how to prove that the union of all these sets is countable.

## marked as duplicate by MJD, Daniel W. Farlow, Lord Shark the Unknown, dantopa, Claude LeiboviciAug 1 '17 at 4:53

• Check this – B. de Morais Aug 1 '17 at 0:45
• I recommend the little book $Stories$ $About$ $Sets$ by N. Ya. Vilenkin. – DanielWainfleet Aug 1 '17 at 2:20

Have you seen the proof that the rational numbers are countable, where you arrange them in a grid?

List the elements in each set in a similar grid, with $A_1$ in the first row, $A_2$ in the second row, etc. Then define a similar function in a zig-zag manner through the grid. This should be a bijection between $\mathbb{N}$ and your union.

• For rational numbers, I listed the elements. I didn't arrange them in a grid. – user444945 Aug 1 '17 at 0:44
• I see. Check out this picture: personal.maths.surrey.ac.uk/st/H.Bruin/image/… - hopefully this helps to show you shows you what I intend here. – smb3 Aug 1 '17 at 0:45
• Once I list all the elements using zig-zag manner through the grid, how do I know if there are any repeats in the list? – user444945 Aug 1 '17 at 1:05
• Repeats are no problem, you can simply skip over them. If the collection including the repeats is countable, then certainly the one without them is also countable. – smb3 Aug 1 '17 at 1:15
• So when listing I don't need to worry about repeats right? If all the sets are countable I think they won't have any repeats. – user444945 Aug 1 '17 at 1:16

Associate a prime $p_k$ to $A_k$ such that $p_i\neq p_j$ if $i\neq j$, let $f_k:A_k\rightarrow \mathbb{N}-\{0\}$ a bijection, define $f:\bigcup_k A_k\rightarrow \mathbb{N}$ by $f(a_k)=p_k^{f_k(a_k)}, a_k\in A_k$, $f$ is injective.

• Your proof is sophisticated. – DeepSea Aug 1 '17 at 1:24

Do you know the "Cantor Diagonal" ? list the elements of $A_1$ as $a_{11}, a_{12}, ...., a_{1n},.....$ And continue for $A_2$, and the $A_k$ has: $a_{k1}, a_{k2}, ...., a_{kn}, ...$. Thus you have an infinite square,and you can rearrange these terms in the following order: $a_{11}, a_{21}, a_{22}, a_{31}, a_{32}, a_{33}, a_{41}, a_{42}, a_{43}, a_{44},....$ and this list is countably infinite hence the union is countable.