6
$\begingroup$

This is part of a bigger problem I'm trying to prove, but my argument relies of the validity of the following idea. Note that when I say countable, I don't mean finite -- I mean countable infinity.

Consider the set of natural numbers, $\mathbb{N}$. Now take a countable subset of them, call it $\mathsf{S}_1$. Then take a countable subset of $\mathbb{N}\setminus{\mathsf{S}_1}$ and call it $\mathsf{S}_2$. Then take a countable subset of $\mathbb{N}\setminus\{{\mathsf{S}_1}\cup{\mathsf{S}_2}\}$ and call it $\mathsf{S}_3$. Continue in this manner to construct $\mathsf{S}_i$'s such that ${\mathsf{S}_i}\cap{\mathsf{S}_j}=\emptyset$ for $i≠j$.

My question is this: is it necessarily the case that eventually there will be finitely many $\mathsf{S}_i$'s with $\mathbb{N}\setminus\bigcup_{i}{\mathsf{S}_i}={P}$ where $P$ is either empty or finite? My guess is yes, but I'm not how to prove it or how to find a counterexample.

$\endgroup$
6

6 Answers 6

Reset to default
23
$\begingroup$

No, this isn't the case. For example, if we take $S_i$ to be the set of numbers $n$ such that $2^i\mid n$ but $2^{i+1}\nmid n$, then all of $S_i$ are countably infinite and pairwise disjoint. Hence taking out these sets will never leave you with a finite or empty set.

$\endgroup$
0
17
$\begingroup$

Since $\mathbb{N}$ and $\mathbb{Q}$ have the same cardinality, it suffices to provide a counterexample for $\mathbb{Q}$. Take $S_i = \mathbb{Q} \cap (i,i+1)$.

$\endgroup$
15
$\begingroup$

Let $p_1,p_2, \dots$ be the primes. Set $S_n = \{p_n^k: k\in \mathbb {N}\}.$ The $S_n$ are pairwise disjoint and countably infinite, and $\mathbb {N}\setminus (S_1\cup S_2 \cup \dots)$ leaves $1$ and the natural numbers with more than one prime factor.

$\endgroup$
13
$\begingroup$

The following is a recipe for generating lots of counterexamples to your claim. Pick your favorite bijection $\langle\cdot, \cdot\rangle$ between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$ - say, the Cantor pairing function. Now let $$S_n=\{\langle n, x\rangle: x\in\mathbb{N}\}.$$ Basically, we transform $\mathbb{N}$ into a $\mathbb{N}$-by-$\mathbb{N}$ array, and then let $S_n$ be the $n$th column of that array.

$\endgroup$
2
  • 5
    $\begingroup$ By the way, a good exercise: show that there is an uncountable family of subsets of $\mathbb{N}$ $\{S_i: i\in I\}$ which are almost disjoint - that is, such that $S_i\cap S_j$ is finite for $i\not=j$. In fact, we can find such a family of size continuum! $\endgroup$
    – Noah Schweber
    Commented Oct 26, 2015 at 3:03
  • $\begingroup$ A solution to your exercise: For each subset $A\subseteq\Bbb N$, construct the set $F(A)=\{A\cap[1,n]:n\in\Bbb N\}$. This is a subset of the countable set $[\Bbb N]^{<\omega}$, the collection of finite subsets of $\Bbb N$. Then given $A\ne B$, there is some $n\in A\setminus B$ (or vice versa), so if $A\cap[1,k]=B\cap[1,m]$, then $n\notin A\cap[1,k]$, so $k<n$ and hence $A\cap B\subseteq\{A\cap[1,k]:k<n\}$ which is finite. (You can do the same trick with the finite approximations to an infinite sequence in $2^\Bbb N$, or the approximations to the cantor set containing a given point.) $\endgroup$
    – Mario Carneiro
    Commented Nov 10, 2015 at 20:03
7
$\begingroup$

Edit: @ErickWong is right (see his comment below). This doesn't answer the question. I did cover myself with the caveat "If I understand ...". I may leave this nonanswer up for a while since others may learn from it.

If I understand your question correctly here's another way to show you can have an infinite set left over. Just carry out your construction on the countably infinite set of even numbers. All the odds will remain.

$\endgroup$
2
  • $\begingroup$ This doesn't answer the question. The odds remain, but after only a finite number of removals, leaving open the question of whether the remaining numbers can be removed with finitely many operations. You need to apply this bootstrapping infinitely many times, after which you get essentially Wojowu's answer. $\endgroup$
    – Erick Wong
    Commented Nov 29, 2015 at 21:24
  • $\begingroup$ @ErickWong Thanks. See my edit. $\endgroup$
    – Ethan Bolker
    Commented Dec 6, 2015 at 15:58
4
$\begingroup$

It's easy to construct counterexamples in a variety of ways, as the other answers show. I wanted to point out that once you construct some countably infinite $S_1$ with $\mathbb{N}\,\backslash\,S_1$ also countably infinite, then you can construct each subsequent $S_i$ in the same manner that you constructed $S_1$.

For example, suppose you start with $\mathbb{N}$, and choose $S_1=\{0,2,4,6,8,\ldots\}$, i.e. the even numbers.

Then you can take the set $\mathbb{N}\,\backslash\,S_1=\{1,3,5,7,9,\ldots\}$, order it in an increasing sequence, and then let $S_2$ be the elements of that sequence there with an even index, i.e. $S_2=\{1,5,9,13,\ldots\}$. Then you can repeat the process to construct $S_3,S_4,\ldots$ ad infinitum.

I'll express this idea more formally:

Since $S_1$ has the same cardinality as $\mathbb{N}$, there is some bijective function $f:\mathbb{N}\to S_1$, for example the function $f(n)=2n$.

Since $\mathbb{N}\,\backslash\,S_1=\{1,3,5,7,\ldots\}$ also has the same cardinality as $\mathbb{N}$, there is some bijective function $g_1:\mathbb{N}\to\mathbb{N}\,\backslash\,S_1$, such as $g_1(n)=2n+1$.

Now we can construct

$$S_2=\{g_1(f(n))\,|\,n\in\mathbb{N}\}=\{1,5,9,13,\ldots\}$$

And you can continue to construct $S_3$, given a function $g_2:\mathbb{N}\to\mathbb{N}\,\backslash\,(S_1\,\cup\,S_2)$, such as $g_2(n)=4n+3$: $$S_3=\{g_2(f(n))\,|\,n\in\mathbb{N}\}=\{3,11,19,27,\ldots\}$$

And in general for any $k$ you can construct $S_{k+1}$, given a function $g_k:\mathbb{N}\to\mathbb{N}\,\backslash\,(S_1\,\cup\,\ldots\,\cup\,S_k)$:

$$S_k=\{g_k(f(n))\,|\,n\in\mathbb{N}\}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .