# Infinite partition of $\mathbb N$ by infinite subsets

I am looking for an explicit partition of $\mathbb N$ with the following condition: $$\mathbb N=\bigsqcup_{i\in\mathbb N}A_i$$ where all the $A_i$'s are infinite. What I mean by explicit is a formula for each $A_i$ (I will have to do computation with the elements of $A_i$). So, I can not use the choice axiom.

If someone has an idea to build such a partition...

• $A_i=\{2^i*(2k+1):k\in\Bbb N\}$, and throw in $0$ to any of these. Oct 6, 2014 at 19:54
• Wowoju. Thanks a lot!!! Oct 6, 2014 at 20:02
• See Partitioning an infinite set and other posts linked there. Nov 20, 2017 at 12:41

A really explicit formula would be $$A_i=\{2^i (2j+1) - 1: j\ge 0\}.$$ So $$A_0=\{2j+0\}=\text{even numbers}$$ $$A_1=\{4j+1\}=\{1,5,9,13,\dots\}$$ $$A_2=\{8j+3\}=\{3,11,19,\dots\}$$ $$A_3=\{16j+7\}=\{7,23,39,\dots\}$$ $$\dots$$

Alternatively, you can use Cantor's pairing function to get a bijection $\pi:\Bbb N\times\Bbb N\rightarrow N$. Then we can define $A_i=\{\pi(i,k):k\in\Bbb N\}$.

• Well, the problem is equivalent to give a bijection $\mathbb{N} \times \mathbb{N} \cong \mathbb{N}$. Each of the other answers just mention one such bijection. Oct 8, 2014 at 21:29

Let $\{p_n\}_{n\in\mathbb N}$ be the prime numbers.

Set $$A_j=\{p_j^k : k=1,2,\ldots,\},$$ and $A_0=\mathbb N\setminus\bigcup_{j\in\mathbb N}A_j$.

For every $k\geqslant0$, let $$A_k=\{k+n^2\mid n\geqslant1,2n\geqslant k\}.$$ The partition up to $25$ is as follows:

• $A_0=\{1,4,9,16,25,\ldots\}$
• $A_1=\{2,5,10,17,\ldots\}$
• $A_2=\{3,6,11,18,\ldots\}$
• $A_3=\{7,12,19,\ldots\}$
• $A_4=\{8,13,20,\ldots\}$
• $A_5=\{14,21,\ldots\}$
• $A_6=\{15,22,\ldots\}$
• $A_7=\{23,\ldots\}$
• $A_8=\{24,\ldots\}$

Each $i\geqslant1$ is in $A_k$ where $k=i-\lfloor\sqrt{i}\rfloor^2$.

For the sake of diversity, let $A_1=\{1\}\cup2\mathbb N$, $$A_2=3\mathbb N\setminus 6\mathbb N,\qquad A_3=5\mathbb N\setminus (10\mathbb N\cup15\mathbb N),\qquad A_4=7\mathbb N\setminus (14\mathbb N\cup21\mathbb N\cup35\mathbb N),$$ and, more generally, let $A_i$ denote the set of positive integers whose smallest divisor not equal to $1$ is the $i$th prime.

Equivalently, the sets $(A_i)$ are disjoint and, for every $i\geqslant1$, considering $(p_n)_{n\geqslant1}$ the ordered list of primes, $$\bigcup_{n=1}^iA_n=\{1\}\cup\bigcup_{n=1}^ip_n\mathbb N.$$

There are several valid answers. I like mine. :)

$A_n$ is the set of integers whose decimal representation contains exactly $n$ '1' digits.

You could also try

(2n-1)ℕ /All odds/

(4n-2)ℕ /All evens not divisible by 4/

(8n-4)ℕ /All other evens not divisible by 8/

(16n-8)ℕ /All other evens not divisible by 16/

...