Let $\{\mathrm a _ n \mid \mathrm n \in \omega\}$ be a countably family of countable sets. Prove $\bigcup _{n\in \omega} a _i$ is countable.

We can't suppose axiom of choice but, to balance things out we can suppose there's a family of bijections $\mathcal f _ n :\omega\ \rightarrow\ \mathcal a _ n\ $ for each $n$ in $\omega$ .

I started by making each set from the family disjoint to each other by defining $\mathrm b_0 = \mathrm a_0$, $\mathrm b_n = \bigcup_{i = 0}^{n-1} a_i$ and so on. It all seemed to work fine since $\bigcup_{n\in \omega} b_i = \bigcup_{n\in \omega} a_i$ and i was then almost able to arrange the elements of each set in some sort of table from which i could build a bijection from $\omega \times\omega $ to $\omega$.

To do so, i needed to define new functions $\mathcal g_n$'s from the $\mathcal f_n$'s i had. First i can define $g_0 = f_0$. But then i can't figure out how to index the next elements in $b_1$ without overlaping nor using axiom of choice.

Any wise advice will be truly appreciated.

  • $\begingroup$ Since the axiom of choice is only needed to choose the bijections... $\endgroup$ – Asaf Karagila Jun 4 '18 at 8:53
  • $\begingroup$ Also, the axiom of choice tag is for questions related to the necessity or usage of the axiom of choice in a proof. This question is about neither. $\endgroup$ – Asaf Karagila Jun 4 '18 at 11:42

Fix $n_0$. We have $f_{n_0}$ injects $a_{n_0}$ into $\mathbb{N}$. Consider the following injection $g_{n_0}\circ f_{n_0}$, where $g_{n_0}:m\mapsto p_{n_{0}}^m$ and $p_{n_0}$ is the $n_0$-th prime number under the usual ordering.

Then $\bigcup_{n\in\mathbb{N}}(g_n\circ f_n)$ is the desired injection from $\bigcup_{n\in\mathbb{N}} a_n$ to $\mathbb{N}$.

  • $\begingroup$ I don't get it, since each function $\mathcal f _ n $ goes from $\omega $ to each specified set, are you suggesting to take the inverse of it? I have just edited my question to specify the $\mathcal f _ n$ functions go from $\omega\ $ to $\mathcal a _n $ . $\endgroup$ – José Manuel Madrigal Ramírez Jun 4 '18 at 2:56
  • $\begingroup$ Yes. Let $f_n$ be any function that injects $a_n$ into $\omega$. Observe that the existence of the following family of functions $\{f_n:n\in\omega\}$ is all that is needed from the axiom of choice since we need to choose $f_n$ for infinitely many $n$. $\endgroup$ – Alberto Takase Jun 4 '18 at 4:11

The proof is similar to show that the rationals are countable. Let {$A_i$}$_{i=1}^\infty$ be a countable family of countable sets. Consider an array whose first columns enumerates every member of $A_1$, and the second column enumerate every member of $A_2$ and so on. \begin{bmatrix} A_{(1,1)} & & A_{(2,1)} & \rightarrow& A_{(3,1)} & \\ \downarrow & & \uparrow& & \downarrow \\ A_{(1,2)} & \rightarrow& A_{(2,2)}& &A_{(3,2)} \\ & & & & \downarrow\\ A_{(1,3)} & \leftarrow & A_{(2,3)} & \leftarrow & A_{(3,3)}\\ \downarrow \\ \end{bmatrix} Take into account three things:

  1. Some columns might be finite

  2. Number of columns might be finite

  3. Some elements might be repeated

From the enumeration above, {$A_i$}$_{i=1}^\infty$ is countable.

  • $\begingroup$ But this way you would be using Axiom of Choice to build the arangement aren't you? $\endgroup$ – José Manuel Madrigal Ramírez Jun 4 '18 at 5:07

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.