Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible to construct a disjoint sequence of infinite subsets of $\mathbb{N}$ whose union is not $\mathbb{N}$?

I am thinking this must be possible.

I've considered trying to define each sequence as the range of some function. I have to find a way to hop over natural numbers in some way to leave infinitely many left for each subsequent subset of $\mathbb{N}$. Thinking about just leaving out $1$ so then the union isn't $\mathbb{N}$. I haven't tried to do anything like this before. Any possible hints on how this can be done and I can think a little more to see if I can come up with something? If not I may just ask for an answer heh.

Thanks much for your time and input I appreciate it very much.

share|improve this question

4 Answers 4

up vote 7 down vote accepted

Consider $A_n = \{ p_n^k : k \geq 1 \}$ where $p_n$ is the $n$th prime number.

share|improve this answer
I tried to think of something with prime numbers, thank you. –  Starlight Mar 16 '13 at 6:04
@Wishingwell: You're welcome! –  Arthur Fischer Mar 16 '13 at 6:38

Sure. For $k\in\Bbb N$ let $A_k=\{(4k+1)2^n:n\in\Bbb N\}$. It’s easy to check that the sets $A_k$ are infinite and pairwise disjoint, and their union contains no number of the form $(4k+3)2^n$.

Or let $\{A_k:k\in\Bbb N\}$ be any partition of $\Bbb N$ into infinite sets. For $k\in\Bbb N$ let $B_k=\{2n:n\in A_k\}$. Then $\{B_k:k\in\Bbb N\}$ is a partition of the set of non-negative even integers into infinite sets, whose union therefore contains none of the odd integers.

share|improve this answer

An all-too-easy answer: choose your favorite way of mapping $\mathbb{N}$ to a subset of $\mathbb{N}$ (say, the even numbers). Now, take a partition of $\mathbb{N}$ into disjoint infinite subsets (e.g., via the inverse of the pairing function), and apply that map to each of the subsets.

share|improve this answer

You can just do arithmetic progressions:
Choose distinct $x,y \in \mathbb{N}$

Define $$b: |x-y|+1 $$ $$ O = \bigcup_{x \in \mathbb{N}, x \ne 1} \{x,x+2b,x+3b,\ldots\} $$ Now just ensure that you omit at least one progression from your collection, (by the $x\ne 1$ condition), and their disjoint, infinite union will not be $\mathbb{N}$.

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