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?

  • $\begingroup$ 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. $\endgroup$ – Josh Keneda Mar 4 '15 at 18:52
  • 2
    $\begingroup$ 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. $\endgroup$ – DRF Mar 4 '15 at 18:54
  • $\begingroup$ @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. $\endgroup$ – riddler Mar 4 '15 at 18:55
  • 1
    $\begingroup$ @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." $\endgroup$ – DRF Mar 4 '15 at 19:03
  • 3
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Mar 4 '15 at 19:04

This seems too simple:

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

  • $\begingroup$ By "this" do you mean the problem or that my proof was incorrect? I added in a quantification I forgot by accident. $\endgroup$ – riddler Mar 4 '15 at 23:35
  • $\begingroup$ Isn't it even simpler? $\mathbb N = \{1\}\cup\{2\}\cup\cdots$ Or am I missing something here? $\endgroup$ – Math1000 Mar 4 '15 at 23:42
  • $\begingroup$ By "this" I mean my solution. It has nothing to do with your solution. It reflects my belief that the problem, as stated, is quite simple, almost too simple. $\endgroup$ – marty cohen Mar 4 '15 at 23:42
  • $\begingroup$ @Math1000: I am not sure whether the problem wants one set of disjoint sets or an infinite number. $\endgroup$ – marty cohen Mar 4 '15 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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