Partition of N into infinite number of infinite disjoint sets? [duplicate]

Is it possible to have a countable infinite number of countable infinite sets such that no two sets share an element and their union is the positive integers?

-

marked as duplicate by Alex M., Dominik, graydad, Tom-Tom, user1551Sep 8 '15 at 15:08

– Jason DeVito Jul 12 '11 at 20:34
Funny how all the answers here were given there, despite the fact that this is a more specific question - in which the axiom of choice is not involved, whereas the more general question can be countered under the negation of AC. – Asaf Karagila Jul 12 '11 at 20:38
@Asaf: Presumably most people read the other question as 'some infinite set' rather than 'any infinite set' and exhibited examples for the simplest infinite set of all... – Steven Stadnicki Jul 13 '11 at 0:52
@Steven: Yes, you are correct. I did not say that the statement is "for all", but it can be shown that without AC it is consistent that it is not for all and only for some, while in this case it does not require much choice. – Asaf Karagila Jul 13 '11 at 9:05

Sure. For example, let $A_n$ be the natural numbers with exactly $n$ ones in their binary expansion.

Alternately, pick your favorite way of decomposing $\mathbb{N}$ into two disjoint infinite subsets $A, B$, and pick a bijection $f : B \to \mathbb{N}$. Then $f(B)$ can be decomposed into two disjoint subsets $A, B$, hence $B$ can be decomposed into two disjoint subsets $f^{-1}(A), f^{-1}(B)$. Rinse and repeat. This argument is fairly general and works for any infinite set which admits a decomposition into two disjoint subsets of the same cardinality as it (which under the Axiom of Choice is all of them).

-

Maybe we can start slowly, by doing a decomposition of $\mathbb{N}$ into $2$ disjoint sets, say the odds and the evens.

Let's now go for a decomposition into $3$ disjoint sets. Leave the odds alone, and decompose the evens into those divisible by $2$ but no higher power of $2$, and those divisible by $4$. To put it another way, we are using the odds, twice the odds, and the rest.

Continue, and let's introduce some notation. Let $W_0$ be the set of odd positive integers. Let $W_1$ be the set of positive integers which are $2^1$ times an odd number. Let $W_2$ be the set of positive integers which are $2^2$ times an odd number. In general let $W_n$ be the set of integers which are $2^n$ times an odd number.

It is clear that the $W_k$ are all infinite, pairwise disjoint, and that their union is all of $\mathbb{N}$.

-

Let p_n be the nth prime and let A_n be the positive integers whose smallest prime divisor is p_n (throw 1 in with A_1). This is basically applying the sieve of Eratosthenes to the entire set of positive integers.

-

Easily.

Let $P=\{2,3,5,7,11,\ldots\}$ be all the prime numbers. Take for $p\in P$, any prime number let $A_p = \{p^n\mid n\in\mathbb N, n\neq 0\}$ and take $A_1 = \{n\in\mathbb N\mid n \text{ have at least two different prime divisors}\}\cup\{0\}$.

Every $A_i$ is disjoint of the rest, and every natural number has to appear in at least one.

However if one requires the sets to be disjoint then it is possible to show that you cannot split $\mathbb N$ to more than a countable number of disjoint sets.

Suppose $A_i$ for $i\in I$, for some indices set $I$, is a partition of $\mathbb N$ to disjoint sets. Map each $i\in I$ to the minimal $n\in A_i$.

Since $A_i\cap A_j=\varnothing$ we have that the minimal element of $A_i$ cannot be in $A_j$, let alone its minimal element. Since every $A_i$ is non-empty then it has a minimal element. Therefore we have an injective mapping from $I$ into $\mathbb N$ and thus $I$ is countable (countably infinite, or finite in this case).

Another fine example is to take your favourite bijection between $\mathbb N$ and $\mathbb N\times\mathbb N$, call it $f$. Now take $A_n=f^{-1}[\{n\}\times\mathbb N]$, then $A_n\cap A_m=\varnothing$ for $n\neq m$ and easily enough this is a partition as you like. This can be generalized to any cardinal number such that $|A|=|A\times A|$.

-

While all of the answers here are obviously excellent, I'll throw in one more: imagine the points of $\mathbb{N}^2$ drawn out as an infinite grid of cells (the positive quadrant of the plane, essentially); then fill the cell $(1,1)$ with $1$, the cells $(2,1)$ and $(1,2)$ with $2$ and $3$, and in general all of the cells $(n,1)$ through $(1,n)$ that sum to $n+1$ with the numbers from $\left({1\over 2}n(n-1)\right)+1$ to ${1\over 2}n(n+1)$. This provides an easy arithmetic pairing function $\langle\cdot,\cdot\rangle$ from $\mathbb{N}^2$ to $\mathbb{N}$, mapping $(i,j)$ to $\langle i,j\rangle = {1\over2}(i+j-2)(i+j-1)+i$ (and with explicitly definable inverse functions $j_0(n), j_1(n)$ such that $\langle j_0(n),j_1(n)\rangle = n$ for all $n$, though I won't write those out); $\mathbb{N}$ can then be partitioned into the sets $\mathbb{N}_k = \left\{\langle k,i\rangle: i\in\mathbb{N}\right\}$. This is the approach usually taken in recursion theory, in particular, where the explicit $\Delta_0$ definability of the pairing function and its inverses is important.

-

Let $$A_0 = \lbrace 1,3,5,7,9,\ldots \rbrace$$ and $$A_1 = \lbrace 2^n 1 : n \in \mathbb{N} \rbrace,$$ $$A_2 = \lbrace 2^n 3 : n \in \mathbb{N} \rbrace,$$ $$A_3 = \lbrace 2^n 5 : n \in \mathbb{N} \rbrace,$$ $$A_4 = \lbrace 2^n 7 : n \in \mathbb{N} \rbrace,$$ $$A_5 = \lbrace 2^n 9 : n \in \mathbb{N} \rbrace,$$ $$\cdots.$$ Noting that for any two distinct elements $r_1$ and $r_2$ of $A_0$ it holds $2^{n_1}r_1 \neq 2^{n_2}r_2$ $\forall n_1,n_2 \in \mathbb{N}$, we have that the $A_i$ are disjoint. On the other hand, let $2k$, with $k \in \mathbb{N}$, be an arbitrary even natural number. Considering its prime factorization, it is necessarily of the form $2k = 2^n r$, where $n \in \mathbb{N}$ and $r \in A_0$. Hence $2k \in \cup _{i = 1}^\infty A_i$, from which it follows that $\cup _{i = 1}^\infty A_i = \lbrace 2,4,6,8,10,\ldots \rbrace$, and so $\mathbb{N} = \cup _{i = 0}^\infty A_i$, with all the $A_i$ disjoint and countably infinite.

The sets $A_i$, $i = 1,2,3,\ldots$, correspond to the rows $$2,4,8,16,32, \ldots,$$ $$6,12,24,48,96, \ldots,$$ $$10,20,40,80,160, \ldots,$$ $$14,28,56,112,224,\ldots,$$ $$18,36,72,144,288,\ldots,$$ $$\cdots,$$ while the sets $W_i$, $i=1,2,3,\ldots$, in user6312's answer correspond to the corresponding columns, that is to $$2,6,10,14,18,\ldots,$$ $$4,12,20,28,36,\ldots,$$ $$8,24,40,56,72,\ldots,$$ $$16,48,80,112,144,\ldots,$$ $$32,96,160,224,288,\ldots,$$ $$\cdots.$$
For each integer $n$ put it in $A_i$ if $i$ is the smallest integer such that $n-i$ is a square. Or you can replace square with any even-degree polynomial with integer coefficients for a whole family. Or you can say n-i must be a prime.
Also: $A_i$ = all integers with exactly $i$ prime-factors, counting multiplicity.