33
$\begingroup$

Can you partition an infinite set, into an infinite number of infinite sets?

$\endgroup$
5
  • $\begingroup$ When you say infinite set, do you mean unbounded or do you mean having an infinite amount of elements? $\endgroup$ Dec 1, 2010 at 15:33
  • $\begingroup$ @Raskolnikov: Having an infinite number of elements $\endgroup$
    – utdiscant
    Dec 1, 2010 at 15:47
  • $\begingroup$ See also: math.stackexchange.com/questions/12213/… $\endgroup$
    – Aryabhata
    Dec 1, 2010 at 16:20
  • 1
    $\begingroup$ See: en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel $\endgroup$
    – Ami
    Dec 1, 2010 at 21:11
  • 2
    $\begingroup$ Consider $$\mathbb N_{>0} = \bigsqcup_{k \geq 0} \{ n \in \mathbb N_{>0} | v_p(n)=k\},$$ where $v_p$ is the $p$-adic valuation (for a fixed prime $p$). $\endgroup$
    – Watson
    Nov 19, 2019 at 18:34

8 Answers 8

44
$\begingroup$

Yes.

First, note that it's enough to do it for countably infinite sets. For if $X$ is uncountable and $Y$ is a countably infinite subset, then $Z = X-Y$ is also infinite. Then, if we divide $Y$ into infintely many infinite sets, we've divided $X$ into infinitely many infinite sets.

So, let's consider a countable set $Y$. Of course, we may as well label the elements of $Y$ as $0,1,2,...$. In short, I'm going to break $\mathbb{N}$ into infinitely many infinite sets.

First note that there are infinitely many prime numbers. Further, if $p$ and $q$ are prime numbers, and if $p^a = q^b$, then we must have $p=q$ and $a=b$. This follows from unique factorization of numbers.

So, for each prime $p$, consider the set $Y_p = \{ p^a$ with $a>0\in\mathbb{N}\}$. Then, e.g., $Y_2 = \{2,4,8,16,32,64,128,...\}$ and $Y_3 =\{3,9,27,81,243,...\}$.

Clearly, each $Y_p$ is infinite. Further, if $Y_p$ and $Y_q$ have anything in common, then by what we said before, we must have that $p=q$. In other words, for different primes $p$ and $q$, the sets $Y_p$ and $Y_q$ have no overlap.

Since there are infinitely many primes, there are infinitely many $Y_p$ with no overlap. Finally, let $Z$ be all the naturals which are NOT powers of a prime number. $Z$ is also infinite since, for example, it contains $2*3, 2*3^2, 2*3^3, 2*3^4,...$

Thus, we've dividied $\mathbb{N}$ into infinitely many infinite sets: $Z$ and each of the $Y_p$.

$\endgroup$
15
$\begingroup$

Certainly. Look at the Cantor pairing function that shows a correspondence between the naturals and pairs of naturals. You have $f:\mathbb{N}\mapsto \mathbb{N\times N}$ which is a bijection. All sets of the form $(x,y)$ for a given $x$ are infinite. So the sets of $n$ that go to $(x,y)$ for a given $x$ are infinite.

On second thought, this is too complicated. $(x,y) \in \mathbb{N \times N}$ is infinite. The sets of the form $(x,1)$ are infinite, as are $(x,2)$, as are $\ldots$. So we have divided an infinite set into an infinite number of infinite sets. The pairing function just projects this onto $\mathbb{N}$.

$\endgroup$
14
$\begingroup$

The natural numbers organized in an infinite number of rows and an infinite number of columns:

1  2  4  7 11 16 ..
   3  5  8 12 17 ..
      6  9 13 18 ..
        10 14 19 ..
            :  : 
$\endgroup$
10
$\begingroup$

For another example with a somewhat different flavour, chop the real line up at integers, dividing it into countable union of unit intervals, each of which has uncountably many points:

$$ \mathbb{R} = \bigcup_{n \in \mathbb{Z}} [n,n+1)$$

$\endgroup$
1
  • $\begingroup$ This is for an uncountable set though. $\endgroup$
    – PleaseHelp
    Mar 28, 2016 at 13:55
6
$\begingroup$

Here's a quick way to divide the positive integers into infinitely many infinite sets:

Let $U_1$ be the set of positive odd numbers: $$\{1,3,5,7,\dots\}$$ Let $U_2$ be the set of twice the positive odd numbers: $$\{2,6,10,14,\dots\}$$ Let $U_3$ be the set of four times the positive odd numbers: $$\{4,12,20,28,\dots\}$$ …

Let $U_n$ be the set of $2^{n-1}$ times the positive odd numbers.

That is, the numbers in each set are twice the numbers in the last set. Now, the positive integers have been partitioned into the infinite sets $U_n$.

$\endgroup$
3
  • $\begingroup$ How do we know the sets do not have any overlap? How do we know the sets altogether will cover all natural numbers? $\endgroup$
    – Pooya
    Dec 28, 2023 at 19:06
  • 1
    $\begingroup$ @Pooya For the first: suppose $a2^n=a'2^{n'}$ for $a,a'$ odd. Wlog $n>n'$. Then $a2^{n-n'}=a'$ and $a'$ is even, contradiction. $\endgroup$ Dec 28, 2023 at 19:14
  • 1
    $\begingroup$ For the second: by induction. Base case, $1$ is in $U_1$. Induction step, suppose $1,\dots,n-1$ are each in one of these sets. If $n$ is odd it's in $U_1$; if $n$ is even then $\frac n2$ is in $U_k$ for some $k$ by the induction hypothesis, and $n$ is in $U_{k+1}$. $\endgroup$ Dec 28, 2023 at 19:15
4
$\begingroup$

A simple way to split the set of natural numbers.Take the sets $S_n$ of numbers with sum of digits $n$ for each all $n$. Obviously no sets overlap and each $S_n$ contain numbers of the form $1111..0000...$ where the string of 1's contain $n$ of them, and as many zeros as you wish

$\endgroup$
1
$\begingroup$

An (imo) beautiful practical example from Elementary Number Theory.

As you know, any equivalence relation, partitions a set.

Now, if you partition the Natural numbers $(\mathbb{N})$ = {1, 2, 3, ... } ( 0 of course NOT included ), based on the relation "Prime Signature", you have what you are looking for.

Based on the Main Theorem of Arithmetic we can map any natural number to two ordered lists:

$$ n = \Pi_{i=1}^{\omega(n)} p_i^{\alpha^{i}}. $$

For example: $12 = 2^2 3^1$, 30= $2^1 3^1 5^1$, and so on, where $12$ belongs to the partition $\{2,1\}$ and $30$ belongs to the partition $\{1,1,1\}$.

We call the ordered list of ${\alpha_{i}}'s$ the "Prime Signature". ( Example: $1000$ has signature $\{3,3\}$ ).

What makes this infinite partition so 'beautiful' is that every subset of $\mathbb{N}$ in this infinite partition corresponds to a partition of a natural number.

$\endgroup$
1
$\begingroup$

Note: I wrote this up because it is interesting, and 'rounds out' the theory, that we can partition $X$ into an infinite number of blocks with each on being countably infinite.

I am marking this as community wiki. If several people downvote this and/or post comments that they disagree with my sentiments, I'll delete this.


Proposition 1: Every infinite set $X$ can be partitioned into blocks with each one being countably infinite.
Proof
Choose a well order $\le$ on $X$ that has no maximal elements (see this) and let $\sigma$ denote the successor function on $X$. Let $L$ denote the elements of $X$ that do not have an immediate predecessor. For each $\alpha \in L$ define

$\tag 1 L_\alpha = \{ \sigma^n(\alpha) \, | \, \text{integer } n \ge 0\}$

This family partitions $X$ (see this) and each set must also be countably infinite. $\quad \blacksquare$.

If $L$ is finite take any $\alpha \in L$ and partition the countably infinite set $L_\alpha$ into an infinite number of blocks (see the many fine answers in this thread). So we have

Proposition 2: Every infinite set $X$ can be partitioned into an infinite number of blocks
with each one being countably infinite.

$\endgroup$
1
  • 1
    $\begingroup$ Did you mean $\sigma^n,$ rather than $S^n$? $\endgroup$ Mar 5, 2023 at 21:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .