# Expressing $\Bbb N$ as an infinite union of disjoint infinite subsets.

The title says it. I thought of the following: we want $$\Bbb N = \dot {\bigcup_{n \geq 1} }A_n$$
We pick multiples of primes. I’ll add $1$ in the first subset. For each set, we take multiples of some prime, that hasn’t appeared in any other set before. Then \begin{align} A_1 &= \{1, 2, 4, 6, 8, \cdots \} \\ A_2 &= \{3, 9, 15, 21, 27, \cdots \} \\ A_3 &= \{5, 25, 35, 55, \cdots \} \\ A_4 &= \{7, 49, 77, \cdots \} \\ &\vdots \end{align}

I’m heavily using the fact that there are infinite primes. I think these sets will do the job. Can someone check if this is really ok? Also, it would be nice to know how I could express my idea better, instead of that hand-waving. Alternate solutions are also welcome. Thank you!

Edit: the subsets must be also infinite.

#### Solutions Collecting From Web of "Expressing $\Bbb N$ as an infinite union of disjoint infinite subsets."

Here is another way to do it.
Let $A_{i}$ consist of all the numbers of the form $2^im$ where $2\nmid m$. That is, $A_i$ consists of all the numbers that have exactly a factor of $2^i$ in them. So
\begin{align} A_0 &= \{1,3,5,7,9,11, \dots\}\\ A_1 &= \{2, 6 =2^1\cdot 3, 10 = 2^1\cdot 5, 14 = 2^1\cdot 7, \dots\}\\ A_2 &= \{4 = 2^2, 12=2^2\cdot 3, 20=2^2\cdot 5, \dots\}\\ A_3 &= \{8=2^3, 24=2^3\cdot 3, 40=2^3\cdot 5, \dots \}\\ &\vdots \end{align}
In general $A_i = \{2^im: p\nmid m\}$. You can of course pick any other prime instead of $2$.

I like @Thomas’s answer best, but I would have enumerated $\mathbb N\times\mathbb N$ and then taken the inverse images of the separate columns for the subsets.

This is an alternate solution.

Let $\alpha$ and $\beta$ be any pair of irrational numbers such that
$$1 < \alpha < 2 < \beta\quad\text{ and }\quad \frac{1}{\alpha} + \frac{1}{\beta} = 1.$$
The two sequences
$\displaystyle\;\left\lfloor\alpha k\right\rfloor\;$ and
$\displaystyle\;\left\lfloor\beta k\right\rfloor\;$, $k \in \mathbb{Z}_{+}$
are called Beatty sequence and it is known they form a partition of $\mathbb{Z}_{+}$.
Define two functions $\tilde{\alpha}, \tilde{\beta} : \mathbb{Z}_{+} \to \mathbb{Z}_{+}$ by
$$\tilde{\alpha}(k) = \left\lfloor\alpha k\right\rfloor \quad\text{ and }\quad \tilde{\beta}(k) = \left\lfloor\beta k\right\rfloor$$
We have
$$\mathbb{Z}_{+} = \tilde{\alpha}(\mathbb{Z}_{+}) \uplus \tilde{\beta}(\mathbb{Z}_{+})$$ where $\uplus$ stands for disjoint union.
Replace the rightmost $\mathbb{Z}_{+}$ recursively by this relation, we get

\begin{align} \mathbb{Z}_{+} &= \tilde{\alpha}(\mathbb{Z}_{+}) \uplus \tilde{\beta}(\mathbb{Z}_{+})\\ &= \tilde{\alpha}(\mathbb{Z}_{+}) \uplus \tilde{\beta}(\tilde{\alpha}(\mathbb{Z}_{+})) \uplus \tilde{\beta}(\tilde{\beta}(\mathbb{Z}_{+})))\\ &= \tilde{\alpha}(\mathbb{Z}_{+}) \uplus \tilde{\beta}(\tilde{\alpha}(\mathbb{Z}_{+})) \uplus \tilde{\beta}(\tilde{\beta}(\tilde{\alpha}(\mathbb{Z}_{+}))) \uplus \tilde{\beta}(\tilde{\beta}(\tilde{\beta}(\mathbb{Z}_{+}))))\\ &\;\vdots \end{align}
As a consequence, if one define a sequence of subsets $A_1, A_2, \ldots \subset \mathbb{Z}_{+}$ recursively by
$$A_1 = \tilde{\alpha}(\mathbb{Z}_{+}) \quad\text{ and }\quad A_n = \tilde{\beta}(A_{n-1}), \quad\text{ for } n > 1,$$
these subsets will be pairwise disjoint. It is clear all these $A_n$ are infinite sets.
Since $\beta > 2$, we have

$$\tilde{\beta}(k) = \left\lfloor \beta k \right\rfloor > \beta k – 1 \ge (\beta – 1) k\quad\text{ for all } k \in \mathbb{Z}_{+}$$
This implies
$$\tilde{\beta}^{\circ\,\ell}(k) = \underbrace{\tilde{\beta}(\tilde{\beta}( \cdots \tilde{\beta}(k)))}_{\ell \text{ times}} > (\beta-1)^\ell k \ge (\beta-1)^\ell \quad\text{ for all } k, \ell \in \mathbb{Z}_{+}$$

As a result,

$$\bigcap_{\ell=1}^\infty \tilde{\beta}^{\circ\,\ell}(\mathbb{Z}_{+}) = \emptyset \quad\implies\quad \mathbb{Z_{+}} = \biguplus_{k = 1}^\infty A_k$$
i.e. $\mathbb{Z}_{+}$ is an infinite disjoint union of infinite sets $A_k$. Since there are uncountable choices for $\alpha$, there are uncountable ways of such infinite disjoint unions.

For a concrete example, let $\alpha = \phi, \beta = \phi^2$ where $\phi$ is the golden mean, we get something like

$$\begin{array}{rll} \mathbb{Z}_{+} = & \{\; 1,3,4,6,8,9,11,12,14,16,17,19,\ldots\;\}\\ \uplus & \{\; 2,7,10,15,20,23,28,31,36,41,\ldots\;\}\\ \uplus & \{\; 5,18,26,39,52,60,73,81,94,\ldots\;\}\\ \uplus &\{\; 13,47,68,\ldots\;\}\\ \vdots\; & \end{array}$$

If you follow the rule that you only take the multiples that didn’t show up already, then you’re fine, since by construction you’ll be making all the subsets disjoint and by the Fundamental Theorem of Arithmetic every element will be in some $A_i$.

An example of simple infinite disjoint union would be $A_i=\{i\}$ and then $\mathbb{N}=\bigcup_{i=0}^\infty{A_i}$.

With edit: A simple way to split up $\mathbb{N}$ into a disjoint union of infinite subsets is to start with $A_0=\{0,2,4,\ldots\}$, and then let $A_1$ be every other element of $\mathbb{N}\setminus A_0$ (i.e. $\{1,5,9,13,\ldots\}$). In general, let $A_n$ be the set containing “every other element” of the set $\mathbb{N}\setminus \bigcup_{i=0}^{n-1}{A_n}$.