2
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.

$\endgroup$
  • $\begingroup$ For rational numbers, I listed the elements. I didn't arrange them in a grid. $\endgroup$ – user444945 Aug 1 '17 at 0:44
  • $\begingroup$ 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. $\endgroup$ – smb3 Aug 1 '17 at 0:45
  • $\begingroup$ 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? $\endgroup$ – user444945 Aug 1 '17 at 1:05
  • $\begingroup$ 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. $\endgroup$ – smb3 Aug 1 '17 at 1:15
  • $\begingroup$ 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. $\endgroup$ – user444945 Aug 1 '17 at 1:16
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your proof is sophisticated. $\endgroup$ – DeepSea Aug 1 '17 at 1:24
0
$\begingroup$

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.

$\endgroup$