I realize this question has been asked and answered multiple times, but I'm still not understanding the reasoning. For reference, I've read this, this, and this.
Theorem 2.12. Let {πΈπ}, π=1,2,β¦, be a sequence of countable sets, and put
$$S = \bigcup\limits_{n=1}^{\infty}E_n$$
Then π is countable.
Proof. Let every set πΈπ be arranged in a sequence {πππ},
π=1,2,3,β¦, and consider the infinite array
in which the elements of πΈπ form the πth row. The array contains
all elements of π. As indicated by the arrows, these elements can be arranged in a
sequenceπ₯11;π₯21,π₯12;π₯31,π₯22,π₯13;π₯41,π₯32,π₯23,π₯14;β¦(*)
If any two of the sets πΈπ have elements in common, these will appear
more than once in (β). Hence there is a subset π of the set of all
positive integers such that πβΌπ, which shows that π is at most
countable. Since πΈ1βπ, and πΈ1 is infinite, π is infinite, and thus
countable. βΌ
I understand if there's an injection $F: S\rightarrow \mathbb{N}$, S is countable. I don't understand how utilizing the diagonals leads to such an injection. Since there's 1 element in the first diagonal, 2 in the second, …, n in the n-th, (n – 1) in the (n + 1)-th, etc., how is it possible to say that since there are n elements at most in any diagonal the set is countable?
Best Answer
It's hard, at least for me, to make the diagonal argument clearer, so I offer you the next. Define the following sets:
$$\begin{cases}A_0=\{1,3,5,7,...,2n-1,...\}\\{}\\ A_1=\{2,6,10,14,...,4n-2,...\}\\{}\\ A_2=\{4,12,20,28,...,8n-4,...\}\\{}\\ ...................................\\{}\\ A_n=\{2^n, 2^n+2^{n+1}, 2^n+2\cdot2^{n+1},...,n2^{n+1}-2^n,...\\{}\\..........................................| \end{cases}$$
Check all the above sets are pairwise disjoint and that their union is $\;\Bbb N\;$. Now you have a nice bijection between $\;\Bbb N\;$ and that countable union $\;\{E_n\}\;$ of countable sets: first, map each $\;E_n\to A_n\;$, and then map each element of $\;E_n\to $ an element of $\;A_n\;$ ( can you see why is this possible?).