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.

• Yeah I guess it's okay but not the way I would do it. I would just take a union over singletons personally but to each their own. – Cameron Williams Jun 25 '14 at 19:02
• Um, why not $A_{i}=\{i\}$? – Gina Jun 25 '14 at 19:02
• I'm sorry. The subsets must be also infinite. I'll edit the question. – Ivo Terek Jun 25 '14 at 19:04
• How about: $A_{0}$ is all number that is not prime power including 1. $A_{i}$ is all power (not including 1) of the $i$-th prime. – Gina Jun 25 '14 at 19:06
• That's nice. Simpler, also. Thanks! (; – Ivo Terek Jun 25 '14 at 19:09

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.

• I like this because it avoids everything but the essential set theoretic structure... – Lorenzo Jun 25 '14 at 19:32
• So how about enumerating $\mathbb{N}\times\mathbb{N}$ by $2^{k-1}(2m-1)\mapsto(k,m)$? Then your answer and Thomas's are the same. – Harald Hanche-Olsen Jun 25 '14 at 20:05
• Right, @HaraldHanche-Olsen, I guess the two are as alike as peas in a pod. Only thing is, that I had in mind a different enumeration of $\mathbb N\times\mathbb N$. – Lubin Jun 26 '14 at 3:12
• I expect you did. And of course, your solution has the advantage of not requiring a specific enumeration, i.e., being more conceptual. (Which some people might consider a disadvantage.) But anyhow, my comment was slightly tongue-in-cheek. – Harald Hanche-Olsen Jun 26 '14 at 7:44

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}$.

• I'm sorry, I forgot to put there that the subsets must be also infinite. I have edited the question. Thanks for pointing out the $20$. But my point is, I can have an algorithm to construct the $A_n$ sets. But does it work? – Ivo Terek Jun 25 '14 at 19:07
• I've added a construction I personally like, but yes, what you have right now works fine. The only thing you need to show is that each $A_n$ is infinite, but this is not hard. – Hayden Jun 25 '14 at 19:08
• About the edit, I think I'm missing something here. By what you said, $A_0$ is the set of the even numbers, and $A_1$ would be the set of the odd numbers, and $A_0 \cup A_1$ already killed it. – Ivo Terek Jun 25 '14 at 19:12
• It would be easier to start with taking all the odd numbers. Next, take all odd multiples of 2. Then take all odd multiples of 4. In the $n$th step, take all odd multiples of $2^n$. – Harald Hanche-Olsen Jun 25 '14 at 19:15
• Yes; $A_0=\{0,2,4,6,\ldots\}$, $A_1=\{1,5,9,13,17,\ldots\}$, $A_2=\{3,11,19,\ldots\}$, etc. – Hayden Jun 25 '14 at 19:26

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}$$