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.