Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
When you say infinite set, do you mean unbounded or do you mean having an infinite amount of elements? – Raskolnikov Dec 1 '10 at 15:33
    
@Raskolnikov: Having an infinite number of elements – utdiscant Dec 1 '10 at 15:47
    
See also: math.stackexchange.com/questions/12213/… – Aryabhata Dec 1 '10 at 16:20
1  
up vote 22 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
    
This is for an uncountable set though. – atulgangwar Mar 28 at 13:55

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

share|cite|improve this answer

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 ..
            :  : 
share|cite|improve this answer

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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