Paradox: increasing sequence that goes to $0$?

Question

It is $10$ o'clock, and I have a box.

Inside the box is a ball marked $1$.

At $10$:$30$, I will remove the ball marked $1$, and add two balls, labeled $2$ and $3$.
At $10$:$45$, I will remove the balls labeled $2$ and $3$, and add $4$ balls, marked $4$, $5$, $6$, and $7$.
$7.5$ minutes before $11$, I will remove the balls labeled $4$, $5$, and $6$, and add $8$ balls, labeled $8$, $9$, $10$, $11$, $12$, $13$, $14$, and $15$.
This pattern continues.

Each time I reach the halfway point between my previous action and $11$ o'clock, I add some balls, and remove some other balls. Each time I remove one more ball than I removed last time, but add twice as many balls as I added last time.

The result is that as it gets closer and closer to $11$, the number of balls in the box continues to increase. Yet every ball that I put in was eventually removed.

So just how many balls will be in the box when the clock strikes $11$?
$0$, or infinitely many?
What's going on here?

Answer 1

[Edit.] I am editing my answer to try to give some more insight, prompted by comments on my original response. I hope to develop a deeper idea into what's going on here.

The short answer is that what is important is not the size of the set of balls at any particular time, but rather how the set of balls changes; and ultimately what the limit of those sets are. The key is to determine what that limit is, and then determine how many balls are in that limiting set. The answer is that the limit is the empty set, which has size 0. The rest of this answer is devoted to describing this in some detail.

Part of what I have added to my answer is to point out that although there are multiple ways of measuring convergence — in terms of various norms on characteristic functions — only one of these actually defines the limit of the sequence, and in this case the limit is well-defined.

What matters is not the number of balls, but the set of balls

In this problem, we have more than just a number of balls which changes with time. What's different is that each of these balls has a unique identity.

This might not seem like it should matter, but it means that the state of the "system" is not a quantity of balls but a set of balls. That set has a certain size, but the size is a derived feature of the system; it follows from which particular set of balls is present. So it is important to determine what the limit of the sequence of sets is.

Description of the problem in terms of sets

Let's consider how the set of balls in the box change with time in the game you present. At step $n$, you add $2^n$ balls, and remove the $n$ lowest-numbered balls. The "state of the system" is given by the following sets:

$S(0) = \{1\}$
$S(1) = \{2,3\}$
$S(2) = \{4,5,6,7\}$
$S(3) = \{7,8,9,10,11,12,13,14,15\}$
$S(4) = \{11,12,\dots,31\}$
etc.

Note that after step 1, the first ball is removed, never to be added again; so it is not an element of the final set. Similarly, at step 2, the second and third balls are removed, never to be added again; so they aren't elements of the final set. And so on. So... none of the balls are in the final set. So then it must be empty! It doesn't matter that the number of balls in the sequence are increasing; what matters is that the number of balls which will never again be in the box is also increasing, and in the limit includes all of the balls.

We can make this more striking by considering, for each step $n$, the set of balls $I(n)$ which is in the set $S(t)$ for all $t \geq n$: that is, $I(n) = S(n) \cap S(n+1) \cap S(n+2) \cap \dots $. Because each ball is eventually removed, never to be added again; this means that

$I(0) = I(1) = I(2) = \dots = \varnothing$

So while the original description makes it look like, moment-to-moment, the final state of the box should be to hold infinitely many balls, a more "forward looking" approach shows that it's clear that the final state of the box is to be empty.

An analysis in terms of characteristic functions

We can contrast the "intuitive" answer of infinitely many balls in the box, and the more precise answer that there ultimately are no balls in the box, using characteristic functions: that is, we replace each set $S(n)$ by a function $f_n : \mathbb{N} \to \{ 0, 1\}$ which is $1$ for those integers belonging to $S(n)$, and $0$ otherwise.

Consider the various $p$-norms on these functions. The cardinality of each set $S(n)$ is precisely equal to the $1$-norm of the function $f_n$ , which grows without bound. The fact that the 1-norm grows without bound — and in particular, the distance between the function $f_n$ and the zero function $\mathbf{0}$ in the $1$-norm grows without bound — is essentially the source of most people's intuition about this problem, and exactly the reason why they find it counterintuitive that the final set should be empty.

But just as the size of a set is a derived quantity, the norm of a function — or of a sequence of functions — is also a derived quantity; and the norm of the limit of a sequence of functions is not necessarily the limit of the norms. In fact, the functions $f_n$ don't converge to anything, in any of the p-norms; it simply diverges to nothing in particular.

But there is at least one notion of convergence which applies to the functions $f_n$, and that is point-wise convergence — the form of convergence which is the broadest, in the sense that it applies to the most cases (and with which all other notions of convergence must agree, if they show that a sequence of functions converges at all). We may simply show that for each $x$, we have $f_n (x) = 0$ for sufficiently large n. It then follows that the sequence $f_n$ converges to $\mathbf{0}$.

The fact that the sequence $f_n$ doesn't converge to $\mathbf{0}$ under any of the p-norms doesn't matter; ultimately what matters is that the sequence converges point-wise, because what we're interested in is the cardinality of the limit itself, which is defined in terms of point-wise convergence. At worst, from a certain aesthetic point of view, one might say that it doesn't converge particularly gracefully (informally speaking) to $\mathbf{0}$; but it does indeed converge, and that is all that matters.

So: using characteristic functions, which is ultimately equivalent to the sets described in the first place, one can show that the sequence of sets does converge, and what they converge to is the empty set. But take comfort that your intuition that they should not reflects a certain awareness of the concept of $p$-norms. :-)

Answer 2

No balls. If $B(t)$ is the number of balls in the box at time $t$, then as you say, $B(t)$ is increasing, and $\lim_{t \to 11}B(t) = +\infty$. But since every ball has been removed, $B(11)=0$. All this is fine. The "paradox" as I see it is that at the outset you expect the function $B$ to be continuous in some sense, but a priori there's no reason why it should be, and indeed it is not.

Answer 3

In my oppinion the answer is pretty simple.

If we have a sequence $A_n$ of sets, the cardinality doesn't always commute with the limit:

$$\lim_n \, {\rm card}(A_n) \neq {\rm card}(\lim_n (A_n)) \,.$$

And somehow this simple result is counterintuitive for us.

Answer 4

I've always thought this sort of puzzle is a wonderful example of the difference between behaviour as you approach a limit, versus behaviour AT the limit.

You can make the puzzle more revealing like this:

Say I have an infinite number of banknotes, each with a unique serial number. I give you bill number 1.

Now, you have two options, either you keep that bill and the game ends, or I give you 10 more banknotes, but you have to burn the lowest numbered bill. It seems obvious that option two is much better. Now, we repeat this game over and over. You keep getting more and more money. But at the limit, every banknote has been burned and you're worse off than you would have been had you just taken the one banknote and left.

Answer 5

• As others have pointed out, there is no mathematical contradiction here. We have a sequence of sets $S_i$ with increasing cardinality whose intersection is the empty set; this is perfectly consistent with the axioms of set theory.

• Nevertheless, there is a serious philosophical problem here. I understand that J. Thompson argued in his paper

  ‘Tasks and Super-Tasks’, Analysis, XV, pp. 1–13, 1954-55,

  that there is indeed a logical contradiction in this scenario. He concluded that such supertasks (i.e. tasks which involve doing an infinite number of actions in finite time) are not merely physically impossible but also logically impossible.

  In lieu of precise definitions of these terms, consider, for comparison, traveling faster than the speed of light. If the theory of relativity is correct, it may very well be physically impossible but its not logically impossible.

  On the other hand, consider a cake that you eat at dinner and that you also don't eat at dinner. This may violate the particular laws of the universe, but its also logically impossible.

• Other philosophers have disputed Thompson's argument, for example:

  ‘Tasks, Super-Tasks, and Modern Eleatics’, P. Benacerraf, Journal of Philosophy, LIX, pp. 765–784, 1962.

  I understand that Benacerraf argued that there is no logical connection between what is inside the box at 11 pm and what is inside the box at any time before 11 pm. Our universe tends to be a "continuous" one, but that is not logically required. Thus Benacerraf concludes there is no obvious reason why supertasks are logically impossible. I believe Benacerraf's refutation is accepted by most of today's philosophers.

• I have not read the original papers. My knowledge of this comes from the book Paradoxes by R.M. Sainsbury, which was assigned reading in my freshman philosophy class. A good source for further reading is the Supertask page of the Stanford Encyclopedia of Philosophy.

Answer 6

During one math class I had the same problem. the professor told us the answer can be a arbitrary integer, depend on how you remove the balls.

Since you said every ball you put in was eventually removed, I will make it simple and assume you first number the balls to natural numbers, and then add and remove the balls with the smallest numbers first.

In this case, the bin will be empty--every ball put in have been removed.

If you define the sequence in the way such that a_n = amount of balls when you do the nth move, then this sequence never get to zero, because there is no n correspond to 11 o'clock.

The increasing sequence doesn't define how many balls in the bin at 11. Therefore there is no paradox.

Answer 7

As other people has said, we model the situation by making a function $F(t)$ that returns the set of balls in the box at time $t$. Within this model, we have $F(\text{11:00}) = \emptyset$. That much is unambiguous.

But it's important to keep in mind that this is only a mathematical model. In the real world, there are many reasons to doubt the model will be accurate. For example, how can you move balls arbitrarily quickly, and how can the box have unlimited volume?. There's no reason to think that, just because the limit is well-defined within our simplistic model, it has to be well-defined in the physical world.

Answer 8

Another approach is to think in terms of functions on the reals. Let $\chi_S(x)$ be the characteristic function of a set $S\subset \mathbb{R}$. Define $f_n(x)=\chi_{[n,2^n]}(x)$ for all integers $n$.

Then the integrals of the $f_n$ increase, but the pointwise limit of the functions is zero.

Of course, this paradox is actually even more "obvious" than that, because if I give you all the balls up front, and then take back, in sequence, all the balls, then at any point before 11, you have infinitely many balls, while at 11 you have none.

Answer 9

If we want to try and pattern this surreal world to mathematical analysis, then it seem we are discussing limits.

The standard mathematical definition of limit of a sequence is well defined (or so I have been led to believe). Meanwhile, the question posed is ambiguous within this context of such limit definition; however, if we infer some sequences from the question, none of these sequences have limits.

A sequence does not have a limit unless at every step beyond some point we are guaranteed to fall within a bounded nearness to the alleged limit point.

For this question, we have the option to call each step the result of the subtractions and the additions together. In this case, we see that at every step we are increasing the size and never decreasing it. We can't argue in this case that all balls added get removed because the addition and subtraction happened at one step, so they are indivisible.

Alternatively, we can label each subtraction and each addition as a distinct step, but, then, to claim a limit exists as per traditional limit analysis, it must be true that at every step we remain within some small arbitrarily small bound (ie, beyond some step N, at each and every single step, the distance to the limit is always less than some epsilon). If we use this interpretation of the question, then we get a sequence that oscillates and deviates way off the alleged limit of zero. There is no limit point.

Alternatively, we can call one step the subtractions taken together and another the additions taken together. We can instead call the first x subtractions a step and .... No matter what path we take, if the over-riding truth is that there is a step at which we have a very large value (note that the additions came after the subtractions.. despite the ambiguities), then we cannot argue with accepted traditional mathematical analysis limit definition that zero is the limit.

To finish by returning to one point in the question, you can't say that every ball is eventually removed if you simultaneously are adding more balls afterward or at the same exact point in time.. any more than I can say that 10 is not really 10 but is instead -100 + 110 and when it becomes 11 we first remove the 110 we had, then add in 121 (or whatever the pattern is that you like). .. You can say it, but that is not a very useful way to reason about infinity (and as far as I can tell, no such 11 o'clock world exists.. so this is just a model).

If we assume that it's also a true statement that all balls were removed, then perhaps it's also true (though not stated in the question) that every ball removed was added back! Or that every ball removed and added back was then removed!! What kind of reality are we describing here?

A lesson is that mathematicians have adopted certain fairly precise ways of thinking about and reasoning about infinities (such as the limit definition) which they have found to be useful in constructing and analyzing models that are useful in the reality that we (or at least I) live in.

[There are models that lead to crazy results, as this "conversation" is demonstrating.]

Given that I don't have enough points to comment in the proper place, let me add some comments here.

@Niel de Beaudrap, you said, "what matters is the set of balls which are at some point added, and then never removed". Why is this what matters? And also, how did you go from saying that the limit of these sets had infinite elements to just declaring the limit had 0 at the very end? For example, that the intersection of "parents" of those individuals in a particular room is the empty set isn't going to be the reason why when that room is blown up that there will be 0 live humans left. In other words, there are many sets that have empty set intersections and you can simultaneously make many other declarations that are totally unrelated to this intersection. So I don't see why you think that 0 intersection means anything special here.

@Nate Eldredge, "But since every ball has been removed, B(11)=0... indeed it is not [continuous]." Unless "every" ball does not mean the full exhaustion of balls that exist at the very end but instead only means "every" ball as we neared the end.