# Showing there are infinitely many mutually disjoint subsets of $\mathbb{N}$.

Problem: Show that there exists an infinite number of mutually disjoint subsets of the set of natural numbers.

My idea: Let $P$ denote the set of all prime numbers. We know $P\subseteq\mathbb{N}$ and that there are infinitely many primes (thanks, Euclid). Let $P_k$ denote the singleton set whose element is the $k$th prime number. Also let $I$ denote the set of indices for all primes, where $i$ and $j$ are arbitrary elements of $I$ and $i\neq j$. Then $$\bigcup_{k=1}^\infty P_k\subseteq\mathbb{N}\qquad\text{and}\qquad (\forall i,j\in I)(P_i\cap P_j=\varnothing).\;\blacksquare$$ Am I missing something? This problem was labeled as a more theoretical/abstract problem--the prime numbers immediately came to mind when I read the question. I just wanted to make sure I wasn't off base. Is there a "better" solution in mind perhaps? The prime numbers seemed optimal to me to use as an example, but 1) is my existence proof correct, and 2) are there any easier examples or more clever ones?

• Your proof is fine. The only thing I'd mention is that you don't use primality, so your strategy could apply to any infinite subset of $\mathbb{N}$. In particular, you could let your $i$th set be the $i$th natural. – Josh Keneda Mar 4 '15 at 18:52
• Using the prime is overkill. Just let $N_i=\{i\}$ the singleton set containing $i$ then you get $\Cup_{i\in\mathbb{N}}=\mathbb{N}$ and $\forall i,j (i\neq j)\implies (N_i\cap N_j=\emptyset)$. Also note it's what I wrote as the second thing that is mutually disjoint not the intersection over all of them. – DRF Mar 4 '15 at 18:54
• @JoshKeneda Right that was actually the first thing that came to mind, but it seemed kind of lame. I also thought about the positive even/odd integers. I mean there seem to be so many ways to prove the statement in the problem. Makes me wonder if the author had something else in mind or left something out. – riddler Mar 4 '15 at 18:55
• @riddler I would assume that there should be another infinite in the statement of the problem. "Show that there exists an infinite number of mutually disjoint infinite subsets of the set of natural numbers." – DRF Mar 4 '15 at 19:03
• What you wrote is not what you are being asked. Your proof is fine, but what you wrote is that the intersection of all the sets is empty, what you need is that the intersection of any two of them is empty. – Andrés E. Caicedo Mar 4 '15 at 19:04

For each natural number $n$, let $A_{n, 1} = \{1, 2, ..., n\}$ and, for $k \ge 2$, $A_{n, k} = \{n+k-1\}$.
Then, for each $n$, $A_{n, k} | _{k \in \mathbb{N}}$ are mutually disjoint subsets of $\mathbb{N}$ that together make up $\mathbb{N}$.
• Isn't it even simpler? $\mathbb N = \{1\}\cup\{2\}\cup\cdots$ Or am I missing something here? – Math1000 Mar 4 '15 at 23:42