1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.]

$\endgroup$
  • $\begingroup$ It probably deserves to be noted that you need the axiom of choice (or some variant of it) to be able to decide on all of the $f_n$s at the same time such that you can use them to construct a single function $\mathbb N\times\mathbb N\to\bigcup_n A_n$. $\endgroup$ – Henning Makholm May 31 '18 at 17:59
  • $\begingroup$ What do you mean by this? And why? The "Axiom of Choice" and the "Axiom of Completeness" are, of course, two different axiomatic statements? Thank you! $\endgroup$ – Rafael Vergnaud May 31 '18 at 18:04
  • $\begingroup$ The statement "Using these $f_n$'s...." implicitly assumes Choice... WHICH $f_n$'s??? What we know is that for each $n$ the set $S_n$ of bijections from $\Bbb N$ to $A_n$ is not empty. The axiom of Choice is needed to prove that there exists a function $g:\Bbb N\to \cup_{n\in \Bbb N}S_n$ such that $\forall n\;(g(n)\in S_n).$ So for any such $g$ we can re-name $g(n)$ as $ f_n$, so as to conclude that there exists a sequence $(f_n)_{n\in \Bbb N} $ where$ f_n\in S_n$ for every $n.$ $\endgroup$ – DanielWainfleet Jun 1 '18 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.