Arranging $\mathbb N$ into a two-dimensional array to prove a countably infinite collection of countable sets is countable.

Question

If $A_n$ is a countable set for each $n \in\mathbb N,$ then $$\bigcup_{n=1}^\infty A_n$$ is countable. How does arranging the natural numbers in a two-dimensional array allow one to show the statement given in the title?

Is it that, given any set $A_i$, being countably infinite, is in bijection with the $i$-th row of that two-dimensional array, itself being countably infinite, and therefore the collection of the sets $A_i$ is in the bijection with the set of rows in that two-dimensional array, which of course is in bijection with the natural numbers?

Answer 1

Since each $A_n$ is countable, there exists, for each $n$, a bijective function $f_n : \mathbb N \to A_n$.

Using these $f_n$'s, we can define a function $f : \mathbb N \times \mathbb N \to \cup_{n=1}^\infty A_n$, which sends each $(n, m) \in \mathbb Z \times \mathbb Z$ to the element $f_n(m) \subset A_n\subset \bigcup_{n = 1}^\infty A_n$. Clearly, this function $f$ is surjective.

So we have exhibited a surjective function $f$ from the countable set $\mathbb N \times \mathbb N$ onto the set $\bigcup_{n = 1}^\infty A_n$. Hence $\bigcup_{n=1}^\infty A_n$ is countable.

[The set $\mathbb N \times \mathbb N$ in this answer is the "two-dimensional array" referred to in your hint.]

Answer 2

I think the two-dimensional array refers to something like this: 1 3 6 10 15 ... 2 5 9 14 ... 4 8 13 ... 7 12... 11 ...

In this case, you can call each column $C_i$. And $B_i$ is referred to the set of $A_i \backslash \bigcup_{k = 1}^{i-1} A_k$It is not hard to prove that $C_i$ is countable. Then there exists a bijective function $f_i: C_i \rightarrow B_i$. Notice that the $C_i$s are disjoint and $B_i$s are disjoint. Besides, each $B_i$ is also countable as they are subsets of $A_i$. If you combine these functions $f_i$ to a new function $f$, you will notice that the domain is $\mathbb{N}$ and the codomain is the union of all $A_i$, and the function is bijective.

(This is my first time answering a question on StackExchange, my writing style still needs a lot of improvement, but hope you would find this solution helpful!)