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

Is it possible to partition the positive integers into an infinite number of disjoint large sets ?

share|cite|improve this question
Since I was thinking of how to partition into small sets, I'll share my thoughts as a comment rather than an answer. Define for each $n \notin \{0,1\}$ the set $S_n = \{n^k \mid k \in \mathbb{N}\}$ (i.e., $S_n$ contains all powers of $n$). Each $S_n$ is small, since the terms grow exponentially. Now, "disjointify" the $S_n$. That is, let $A_1 = S_1$, $A_2 = S_2 \setminus A_1$, $A_3 = S_3 \setminus (A_1 \cup A_2)$, and so on. The collection $\{A_i \mid i \in \mathbb{N}\}$ is a partition of $\mathbb{N}$ into small sets (provided you throw $0$ into $S_1$, say). – Austin Mohr Jan 25 '14 at 20:45
up vote 27 down vote accepted

Yes. $D=\{1,3,5,7,9,\dots\}$, the set of all odd numbers, is a large set; so is $2D=\{2,6,10,14,18,\dots\}$; so are $4D,8D,16D$, etc.

share|cite|improve this answer
The sets indeed form a partition since every natural number can be written uniquely as $2^m(2n+1)$. – Austin Mohr Jan 25 '14 at 20:37
I don't quite see how those sets are disjoint. – E.P. Jan 26 '14 at 2:30
@episanty If an integer was present in any two sets, then it could be written both as $2^x n_1 \in 2^x D$ and $2^y n_2 \in 2^y D$, where $n_1, n_2 \in D$. By the fundamental theorem of arithmetic, this implies that $x = y$ and $n_1 = n_2$. – Thomas Jan 26 '14 at 2:41
Apologies, I read this too hastily. That's correct, of course. – E.P. Jan 26 '14 at 2:44

Similar, a squarefree number is $1,2,3,5,6,7,10,11,13,15,\ldots$ so let your disjoint sets be $m n^2$ for squarefree $m.$ These sets are called squareclasses, I like to write it as one word. The equivalence relation is that two numbers are equivalent if and only if their ratio is a rational square. As we are dealing with integers, that is the same as saying that two numbers are equivalent if and only if their product is a square.

This simple idea underlies a good deal of integer coefficient quadratic form theory. In particular, we speak of squareclasses in the $p$-adic numbers $\mathbb Q_p$ and the $p$-adic integers $\mathbb Z_p.$ See, for example, Cassels, Rational Quadratic Forms.

share|cite|improve this answer
@OldJohn, no such number is a square multiple of another. If we had $m_1 n_1^2 = m_2 n_2^2,$ we would then have $m_1 m_2 = k^2$ and $m_1 = m_2.$ – Will Jagy Jan 25 '14 at 20:51
@OldJohn, took me a while, evidently Maggie was saying she would not celebrate Burns Night any more if Scotland voted to move even farther out of the U.K. – Will Jagy Jan 25 '14 at 20:53
@AsafKaragila, you should say And Toto Too. – Will Jagy Jan 25 '14 at 20:55
I think we should just let them go, so long as they still sell us their whiskey! – Old John Jan 25 '14 at 20:55
@OldJohn, good that you understand your priorities. – Will Jagy Jan 25 '14 at 20:58

Let $N_k$ be the integers with exactly $k$ prime factors (counting with multiplicity). The $N_k$ for $k \ge 1$ partition the integers and are all infinite, if you just agree to stow $1$ somewhere.

share|cite|improve this answer
An infinite set isn't the same as a large set, as far as I understand – DanZimm Jan 25 '14 at 23:46
This answer needs to be expanded to show the $N_k$ are large, i.e. $\sum_{n\in N_k}\frac1n=\infty$. One can prove this by taking the product of the first $k-1$ primes $p_1,\ldots,p_{k-1}$ with the sequence of all the others, so that $$\sum_{n\in N_k}\frac1n\geq\frac{1}{p_1\cdots p_{k-1}}\sum_{j=k}^\infty \frac1{p_j}=\infty.$$ – E.P. Jan 26 '14 at 2:37
Thanks episanty, for completing the argument. – ncmathsadist Jan 26 '14 at 2:38

I understand that the question has already been answered, and answered well, but here is another very quick, but slightly different argument:

The usual proof that $\sum \frac{1}{n}$ diverges uses the fact that there are an infinite number of disjoint finite blocks of numbers whose reciprocals add up to more than $\frac{1}{2}$: $$\{1\} , \{2,3\}, \{4,5,6,7\}, \{8,9,10,\ldots,15\}, \ldots$$ Call these blocks $B_{1}, B_{2},\ldots$

It is obvious that any set of integers that contains an infinite number of these blocks must be a large set. So, just partition $\mathbb{N}$ into an infinite number of infinite sets $\{A_{i}\vert i\in \mathbb{N}\}$, and define the large set $L_{i}$ as $$L_{i}=\bigcup_{x\in A_{i}}B_{i}.$$

share|cite|improve this answer

Your Answer


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.