Filling an infinite urn with balls

You have a countable infinity of balls labelled with the natural numbers, and an infinitely large urn which starts empty. After one minute, you put in balls 1 to 10, and remove ball 1. After 1.5 minutes, you put in balls 11 to 20, and remove ball 2. After 1.75 minutes, you put in balls 21 to 30, and remove ball 3. And so on.

After two minutes, how many balls are left in the urn? It seems as though there should be infinitely many, as every time you take one ball out, you put in another ten. In fact there are zero - ball 1 was removed at step 1 (and never put back in), ball 2 was removed at step 2, and in general, ball n was removed at step n.

The counter-argument, used by non-mathematicians (and, I must admit, me, when I first heard this a few years ago) is ``but each step has the net effect of adding an integer number of balls, so surely there should be an infinite number of balls after an infinite number of steps''.

The problem with this argument is that it misuses mathematical induction. The argument is basically:

1. After step1, there are 9·1 = 9 balls.
2. Assume that there are 9k balls after step k. Then, after step k+1, there will be 9k + 10 - 1 = 9(k+1) balls.
3. Thus, by induction, for any natural number n >=1^*, after n steps there will be 9n balls in the urn.
4. Therefore, after an infinite number of steps, there will be an infinite number of balls in the urn.

When stated this way, it becomes relatively obvious that the error lies in going from step 3. to step 4---it holds for every natural number, yes, but `infinity' is not a natural number.

In general, not to sound like a pompous-arsed academic, but your intuitive notions about the nature of the infinite are probably wrong. At least, they do not lead to a consistent mathematical system, and are thus useless to mathematicians.

*: thus sidestepping the question of whether zero is a natural number.

---

Think there are an infinite number of balls left in the urn? Okay, show me a single ball that is in the urn after a countably infinite number of steps. What is its number?

Putting in nine balls and setting one aside is, when you are dealing with infinite quantities, not the same as putting in ten balls and removing the lowest-numbered one. Again, you cannot use common sense when dealing with infinity, at least not if you want an internally consistent system of mathematics.

Okay ,here is another argument to make the paradox more warped. Consider the function f(t) which tells you the number of balls at time t. Clearly f(t) is an increasing function. Since f(1)=9 therefore f(2)>f(1). So f(2) > 0. This doesnt use Mathematical Induction.

The problem here is that f is increasing on the open interval (1,2) and so lim(t->2)f = infinity. However as you have no information about f outside the open interval(you dont know whether its continuous in particular) therefore you cannot say anything about f(2).

A solution to a similar-looking paradox is that there are an infinite number of balls in the urn and an infinite number of balls not in the urn.

Here's our small modification: we have a countably infinite number of balls labeled with the natural numbers. At each step, we take one ball, put it in the urn, and take the next ball, and set it aside -- this seems to be the same as putting it in the urn and taking it out.

So how many balls are in the urn? Clearly after n steps we have put n balls in the urn (by induction), so as n->infinity there are a countably infinite number of balls in the urn. And how many did we take out (i.e., are not in the urn)? At each step we set aside one ball, so at infinity we have set aside a countably infinite number of balls.

This may seem contradictory, but ask yourself how many odd numbers there are -- of course countably infinitely many. These correspond exactly to the balls in the urn. And the even numbers -- also countably infinite -- correspond to the balls we took out of the urn (set aside).

So why does it matter which ball we take out at step n? The reason is that infinite algorithms (also called supertasks) don't behave like finite algorithms, so sometimes we get seemingly contradictory or unintuitive results.