Can you partition an infinite set, into an infinite number of infinite sets?
Partitioning an infinite set
-
0When you say infinite set, do you mean unbounded or do you mean having an infinite amount of elements? – 2010-12-01
-
0@Raskolnikov: Having an infinite number of elements – 2010-12-01
-
0See also: http://math.stackexchange.com/questions/12213/can-a-collection-of-subsets-of-n-such-that-no-one-set-contains-another-be-uncoun – 2010-12-01
-
1See: http://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel – 2010-12-01
7 Answers
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$.
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 byjection. 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}$.
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)$$
-
0This is for an uncountable set though. – 2016-03-28
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 ..
: :
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
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$.
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 = \{ S^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.