Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Partitioning an infinite set
Partition of N into infinite number of infinite disjoint sets?

Is it possible to find a family of sets $X_{i}$, $i\in\mathbb{N}$, such that:

  • $\forall i$, $X_i$ is infinite,

  • $X_i\cap X_j=\emptyset$ for $i\neq j$,

  • $\mathbb{N}=\bigcup_{i=1}^{\infty}X_i$

Maybe it is an easy question, but I'm curious about the answer and I couldnt figure out any solution.


share|improve this question
In order to unify the various answers: The question is equivalent to write down a bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$. There are lots of known examples, for example $(m,n) \mapsto m+\frac{(m+n)(m+n+1)}{2}$ or $(m,n) \mapsto (2m+1) 2^n$. Of course, $0 \in \mathbb{N}$. –  Martin Brandenburg Oct 25 '12 at 15:00
add comment

marked as duplicate by Jason DeVito, Hagen von Eitzen, rschwieb, Asaf Karagila, Douglas S. Stones Oct 25 '12 at 20:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4 Answers

up vote 18 down vote accepted

An explicit one. $\mathbb N = \{1,2,3,4, \dots\}$. For each $i$, let $A_i$ be the set of odd multiples of $2^{i-1}$. \begin{align} A_1 &= \{1,3,5,7,\dots\} \\ A_2 &= \{2,6,10,14,\dots\} \\ A_3&=\{4,12,20,28,\dots\} \\ &\dots \end{align}

share|improve this answer
We can think of $f(n,m) = 2^{n-1}(2m-1)$ as a very explicit bijection $f: \mathbb N\times\mathbb N \to \mathbb N$ for Martin's answer. –  GEdgar Oct 24 '12 at 21:28
add comment

Take any bijection $f: \mathbb N\times\mathbb N \to \mathbb N$. (There are many such bijections, see Wikipedia article Pairing function.)

Define $X_i=f[\mathbb N\times\{i\}]$.

share|improve this answer
Pardon my ignorance as I try to understand this definition. (1) Does f[N × {i}] mean the same as f(N × {i})? In other words, do the square brackets mean the same thing as parentheses? –  LarsH Oct 24 '12 at 17:48
@LarsH This is the notation which I use for image of a subset; i.e. it means that $f[A]=\{f(a); a\in A\}$. Some texts use $f(A)$ instead of $f[A]$. In this case you should be careful not to confuse it with image of an element. –  Martin Sleziak Oct 24 '12 at 17:52
Thank you. I was getting there, but you confirmed what I was gradually inferring. :-) And that takes care of (2) as well. –  LarsH Oct 24 '12 at 17:54
add comment

Let $p_n$ be the $n$-th prime number. That is $p_1=2; p_2=3; p_3=5; p_4=7$ and so on.

For $n>0$ let $X_n=\{(p_n)^k\mid k\in\mathbb N\setminus\{0\}\}$.

For $X_0$ take all the rest of the numbers available, namely $k\in X_0$ if and only if $k$ can be divided by two distinct prime numbers, or if $k=1$.

share|improve this answer
Sorry @AsafKaragila, but i cant understand you answer, can you explain me please. "My english is too bad". –  Tomás Oct 24 '12 at 12:55
@Tomás: $X_1$ is all the powers of $2$ (the first prime), $X_n$ is all the powers of the $n$th prime, $X_0$ is $\{1\} \cup $ all numbers with at least two distinct prime factors. –  Ross Millikan Oct 24 '12 at 13:10
Ok thanks, i understood. –  Tomás Oct 24 '12 at 13:11
Another possibility with primes: Let $X_1$ be all the numbers divisible by $2$. Let $X_2$ be all the numbers divisible by $3$ but not $2$. Let $X_3$ be all the numbers divisible by $5$ but not $2$ or $3$, etc. Finally, throw $1$ into the set you like best (such as $X_{17}$) and you're done. –  Yoni Rozenshein Oct 24 '12 at 19:49
And if you insist that $0\in \mathbb{N}$, then toss it in too. –  asmeurer Oct 24 '12 at 20:46
show 1 more comment

This is much like the answer by GEdgar, but takes into account the fact that $0\in\Bbb N$. Define $X_i$ to be the set of numbers whose representation ends with exactly $i$ digits $1$ (so in particular $X_0$ is the set of numbers that do not end with a digit $1$; it is obviously infinite (and $0\in X_0$; this is why I didn't take digits $0$), and you can get $X_i$ from $X_0$ by adding $i$ digits $1$ to the end of each element). I was originally thinking of binary representation, but it actually works for any base, in particular for base $10$.

share|improve this answer
"the fact th[at] 0∈N" -- according to en.wikipedia.org/wiki/…, "There is no universal agreement about whether to include zero in the set of natural numbers". –  LarsH Oct 24 '12 at 17:40
@LarsH: Yes, but if you don't think $0 \in \mathbb N$, let $X_i$ be the set of numbers that end in $i-1 \ 1$'s and it works the same. –  Ross Millikan Oct 25 '12 at 13:54
@LarsH: I know about the controversy, as sad afair. But according to the law of the excluded middle, $0\in\Bbb N$ either is true or it is false; one cannot let it depend on ones mood, or convenience for a particular question, which one. (Though possibly it is independent of the axioms, like the continuum hypothesis :-). As anyone knows who does serious business with natural numbers, like combinatorialists or in a lesser degree set theorists, it is in fact true. Indeed, counting (as here final digits $1$) can (and often does) result in $0$, si it had better be a counting number. –  Marc van Leeuwen Oct 25 '12 at 13:59
I agree that $0 ∈ \Bbb N$ is either true or false, i.e. either it is a fact or it is not a fact, within a given system of conventions; and that in order to do business with natural numbers, you need to be very clear about whether you are including 0 or not (and that it is very convenient to do so). On the other hand, it is also a matter of convention, and experts differ on this defn. "Counting numbers" of course is a distinct term, which can be defined independently of "natural numbers" (with the same, or different definitions). Again I'm relying on the same wikipedia article. –  LarsH Oct 25 '12 at 14:39
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.