8
$\begingroup$

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.

Thanks

  • 0
    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}$.2012-10-25

4 Answers 4

5

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

  • 0
    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.2012-10-25
18

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

  • 0
    Hahaha, damn it you're to good - I was just about to give the same answer. :D2015-11-03
18

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}

  • 0
    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.2012-10-24
10

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

  • 0
    @asmeurer: Note that $0\in X_0$ since it can be divided by any number, in particular by more than one prime number.2012-10-25