Any suggestions on the following?

Find three infinite subsets of the naturals N such that the intersection of any two of them is empty and the union of all three is N.

I attempted to divide N into sets containing i)integers with only one prime divisor; ii) those with more than one prime divisor and iii) 0. However, {0} is obviously not an infinite subset. Any suggestions?

  • 4
    $\begingroup$ HINT: Classify by what happens when you divide the natural number by $3$. $\endgroup$ – Brian M. Scott Jun 7 '16 at 23:15
  • $\begingroup$ Why don't you try i) one prime divisor, ii) two prime divisors, iii) three or more prime divisors? $\endgroup$ – bof Jun 7 '16 at 23:20
  • $\begingroup$ You will run into difficulties placing $0$ (if you consider that a natural number) and $1$, but you could place those into one of the other sets arbitrarily. $1$ has no prime divisors (and is the only such number) and does not fall into the categories mentioned. (Actually, technically speaking, $0$ is divisible by every integer except itself since $\frac{0}{n}\in\Bbb Z$ for all $n\neq 0$) $\endgroup$ – JMoravitz Jun 7 '16 at 23:50
  • $\begingroup$ How about the set of primes, the set of squares, and the set of everything else? $\endgroup$ – Akiva Weinberger Jun 8 '16 at 0:13

Note: $\Bbb N$ here is $\{0,1,\ldots\}$

Suppose that you want to find $n$ pairwisely distinct, infinite subsets of $\Bbb N$, $N_0,...,N_{n-1}$, with $\Bbb N = N_0 \cup \cdots \cup N_{n-1}$. The most obvious way to do this is by taking:

$N_i = \{i + kn, k \in \Bbb N\}$, for $0 \le i \le n-1$.

One way to understand this is that for $N_0$, we take $0$ and skip to $n$, then to $2n$, etc. For $N_1$, we take $1$ and skip to $n+1$, etc. This way, we would have included every natural number, the sets are clearly pairwise distinct and infinite.

Another way is to use the Euclidean algorithm, which says:

Given $n \in \Bbb N$ and $m \in \Bbb N$, there exist unique $q \in \Bbb N$ and $0 \le r \le n-1$, such that $m = qn + r$

So, for our $n$, each natural number can be uniquely written as $qn + r$ for some $q \in \Bbb N$ and $0 \le r \le n-1$. Can you now see the reason for that choice of $N_i$'s?


Hint: with two, rather than three, sets, you could let one set be the even naturals and the other be the odd ones. Now could you expand this to work with three sets?


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.