0

What happens if one divides an infinitely large set into two equal parts - or eliminates half the members of the set - an infinite number of times?

Two intuitions:

  1. After each elimination, the remaining set is still infinitely large, thus even an infinite number of eliminations leaves us with an infinitely large set.

  2. Let's eliminate from the set of natural numbers every other member repeatedly. After the first step, only every other number is left. After the second step, only every fourth member is left. After the 3rd step only every 8th. And so on. If one does this forever, no natural number escapes elimination. Therefore the infinite process of elimination leaves us with an empty set.

Is either intuition compelling/correct? And why is the other one deceptive?

Thomas Pogge
  • 447
  • 2
    This is just a case where you have to define the process rigorously. For example, if we toss out of the integers the multiples of $2,$ then the multiples of $3,$ then $5,$ etc, at some point, you remove any integer other than $\pm 1.$ You can design the process to have finitely many or infinitely man remaining elements. (We can’t really talk about “half of” an infinite set.) – Thomas Andrews Oct 01 '21 at 23:03
  • @AlexSweeney depends on what you mean by the limit. If the “limit” is the limit in terms of a sequence of sets, (which here would be the intersection of sets,) the limit can be quite a few things. – Thomas Andrews Oct 01 '21 at 23:07
  • This depends on how you do measure the bigness of a set. – Anixx Oct 02 '21 at 19:59

2 Answers2

2

Given a descending sequence of sets, $$A_1\supseteq A_2\supseteq A_3\supseteq\cdots$$

We can think of the limit of the cardinalities: $$\lim_{n\to\infty}|A_n|,\tag1$$ or we can look at the limit in terms of sets, which here is the intersection of sets:

$$\bigcap_{n=1}^{\infty} A_n\tag2$$

Both might be useful in different circumstances, and the cardinality of $(2)$ might be different from $(1).$

The only thing we know is the cardinality of $(2)$ is $\leq$ the value returned in $(1),$ and if $(1)$ is finite, then $(1)$ and will be equal to the cardinality of $(2).$

A variant of $(1)$ is if you have a measure space. Then you could take $$\lim_{n\to\infty} \mu(A_n)\tag3$$ as your limit, but again, $(3)$ won’t agree with the measure of $(2).$ $(3)$ is an upper bound for the measure of $(2),$ but they are only known to be equal if $(3)$ is finite.

The measure example is the kind of thing leads to some counterexamples in analysis. For example, there are functions $f_n$ such that $f_n(x)\to 0$ at each $x,$ but for which $\int f_n(x)\,dx\to\infty.$

It’s worth noting we can remove just one at a time and still get an empty set for $(2).$ For example, $A_{n}=\{m\in\mathbb N\mid m\geq n\}$ removes one element at s time, and you still have an empty intersection.

Indeed, this is the heart of mathematical induction.

Thomas Andrews
  • 177,126
  • I think you are saying that there is no clear-cut answer to what the cardinalities of (1) and (2) are. If the cardinality of (1) is finite, then it is zero. If so, the cardinality of (2) is also zero - they are equal. For the two cardinalities to be unequal, that of (1) must be infinite and that of (2) must be zero. Right? A third possibility is that both cardinalities are infinite. Can nothing more be said to choose among these possibilities? – Thomas Pogge Oct 03 '21 at 19:00
  • 1
    @ThomasPogge If $(1)$ is infinite, $(2)$ can be infinite or a finite set of any size. If $(1)$ is finite, and the sequence is properly decreasing - $A_n \supsetneq A_{n+1}$ - then yes, $(1)$ is zero. I had $\supseteq$ in my formulation. In the original question, $(1)$ is always infinite. – Thomas Andrews Oct 03 '21 at 20:31
0

If you eliminate from an infinite set of natural numbers its subset, with the remaining set still infinite, its cardinality remains the same, while its numerocity changes.

The numerocity of a subset of integers is the sum of the indicator function over the set, $n(S)=\sum_{k=-\infty}^\infty p(k)$, where $p(k)$ is $1$ if $k\in S$ and $0$ otherwise.

For an infinite set the numerocity will be a divergent series, but one can operate with such series as if they were numbers.

For instance, if the numerocity of all (positive and negative) integers is $\Omega$, then the numerocity of even numbers or odd numbers is $\Omega/2$, the numerocity of (positive) natural numbers is $\Omega/2-1/2$ (that's why the sum $\sum_{k=1}^\infty 1$ has regularized value of 1/2). If you take all even numbers from natural numbers, the numerocity will be $\Omega/4$ and if you take all odd numbers from natural numbers, the numerocity will be $\Omega/4-1/2$.

Anixx
  • 9,119