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.



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.

  • $\begingroup$ 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}$. $\endgroup$ – Martin Brandenburg Oct 25 '12 at 15:00

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}

  • $\begingroup$ 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. $\endgroup$ – GEdgar Oct 24 '12 at 21:28

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

  • $\begingroup$ 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? $\endgroup$ – LarsH Oct 24 '12 at 17:48
  • $\begingroup$ @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. $\endgroup$ – Martin Sleziak Oct 24 '12 at 17:52
  • $\begingroup$ Thank you. I was getting there, but you confirmed what I was gradually inferring. :-) And that takes care of (2) as well. $\endgroup$ – LarsH Oct 24 '12 at 17:54
  • $\begingroup$ Hahaha, damn it you're to good - I was just about to give the same answer. :D $\endgroup$ – C-Star-W-Star Nov 3 '15 at 13:55

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

  • $\begingroup$ Sorry @AsafKaragila, but i cant understand you answer, can you explain me please. "My english is too bad". $\endgroup$ – Tomás Oct 24 '12 at 12:55
  • 3
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Oct 24 '12 at 13:10
  • $\begingroup$ Ok thanks, i understood. $\endgroup$ – Tomás Oct 24 '12 at 13:11
  • $\begingroup$ 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. $\endgroup$ – Yoni Rozenshein Oct 24 '12 at 19:49
  • $\begingroup$ And if you insist that $0\in \mathbb{N}$, then toss it in too. $\endgroup$ – asmeurer Oct 24 '12 at 20:46

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

  • 2
    $\begingroup$ "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". $\endgroup$ – LarsH Oct 24 '12 at 17:40
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Oct 25 '12 at 13:54
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Oct 25 '12 at 13:59
  • $\begingroup$ 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. $\endgroup$ – LarsH Oct 25 '12 at 14:39

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