7
$\begingroup$

This question already has an answer here:

This is a somewhat hand wavy question but I'm not sure how to ask it more precisely.

If we have a countably infinite sequence (or set), can we take away infinitely many elements from the sequence infinitely many times and still be left with infinitely many elements? Or is it the case that we must be left with 0 or finitely many elements?

$\endgroup$

marked as duplicate by Martin Sleziak, Marc van Leeuwen, N. F. Taussig, user147263, Morgan Rodgers Nov 11 '15 at 12:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

44
$\begingroup$

Here's a construction on the natural numbers.

First remove all powers of $3$. Then remove all powers of $5$. Then remove all powers of $7$. Then remove all powers of $11$. Continue in this way, removing all powers of each odd prime. Clearly these removed sets are disjoint (a number cannot be a power of both $3$ and $5$, for example), and infinite.

But what we have left is also infinite. For example, it contains all powers of $2$, and this is an infinite set.


Another possibility (not using any facts from number theory) - let $S$ be the set of all finite $0-1$ sequences (for example, $010001110, 1001, 000\in S$). Remove all sequences starting with $01$. Then remove all sequences starting with $001$. Then remove all sequences starting with $0001$, and continue in this way. Once again, we remove infinitely many elements infinitely many times, but what we have left (namely, the set of sequences starting with a $1$, plus the constant $0$ sequences) is still infinite.


Update: You have assumed in your question that it is possible to remove infinitely many elements from a set infinitely many times. Well, if you can do that (and you can), then just leave off removing the first infinite set. Then what you have left at the end will be infinite.

$\endgroup$
8
$\begingroup$

Yes, this is possible.

For example, consider the set of all natural numbers $\mathbb N$. In your first move, remove every number that is a power of $2$. In your second move, remove (from the remaining set) every number that is a power of $3$. In your $n$-th move remove all numbers that are a power of the $n$-th prime.

After you have done this infinitely many times (once for each prime), there are still infinitely many numbers left - namely those with at least 2 distinct prime factors (and also the number 1).

$\endgroup$
  • 2
    $\begingroup$ In fact $1$ is a power of every prime; it gets removed (each time if it could). $\endgroup$ – Marc van Leeuwen Nov 11 '15 at 6:36
3
$\begingroup$

Let $P_1$ be the set of odd prime numbers which are congruent to $1$ modulo $4$. It is well known that such a set is infinite.

Start with $X:=\mathbb{N}$.

For each prime $p\in P_1$ define $X:=X-p\mathbb{N}$ i.e. take away the set of integers that are divisible by $p$ (this is an infinite set).

Now doing this for each $p\in P_1$ we get $X$ containing $3^n$ for all $n\geq 0$ so this is still infinite.

$\endgroup$
3
$\begingroup$

Other possibilities:

  1. Take the natural numbers. First remove the numbers that are divisible by 2, but not by 4. Then remove the numbers that are divisible by 4, but not by 8. Then remove the numbers that are divisible by 8, but not by 16. In general, in the $n$th step, remove the numbers that are divisible by $2^n$, but not by $2^{n+1}$. You are left with the odd numbers.

  2. Take the rational numbers. At the $n$th step, remove all rationals that are between $n-1$ and $n$. You are left with the negative rational numbers.

$\endgroup$

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