Sunday 14 July 2019

Infinite arithmetic and the parable of the bingo balls

Hilbert's (or The Infinite) Hotel is a well-known setting for thinking about infinite sets, and in particular for thinking about their sizes. There's a less well-known approach that I think complements it nicely. I don't know who came up with it, so I'll just call it the parable of the bingo balls.

The Setting

Here's the idea. You have two baskets. One of them, basket A, contains a collection of bingo balls, one labelled with each positive integer. The other, basket B, is empty.

At 12 noon, you transfer some of the of balls from basket A to basket B: ball \(1\) up to ball \(n_1\), where \(n_1 \ge 1\). At 12:30, you remove some number of balls from basket B, and transfer some balls, ball \(n_1+1\) to ball \(n_2\), where \(n_2 \ge n_1+1\) from basket A to basket B. At 12:45, you remove some more balls from basket B, and transfer the next collection of balls, always choosing the ones with the the next available labels, from basket A to basket B. You repeat this process whenever the amount of time until 13:00 is halved. Clearly you need infeasibly fast hands to do this in practice: fortunately, we don't need to worry about this, we're just thinking about an ideal mathematical process.

What is in the baskets at 13:00?

It's not hard to persuade yourself that basket A is now empty. Whatever \(n\) you think of, ball \(n\) was removed on or before the \(n^{\text{th}}\) operation. But what about basket B?

It turns out that this depends on the process.

Basket B is empty

In the simplest case, at the first operation you move ball \(1\) from basket A to basket B, and at each subsequent operation you remove from basket B the ball that just got put in, and transfer the next ball from basket A to basket B.

The after each operation, basket B has one ball in it. Indeed, after any number of operations, basket B has one ball in it.

You might naively think that since there is one ball in basket B after every operation, there will be one ball in basket B at 13:00. But funny things happen with infinity.

Ball 1 isn't in basket B, because that was removed at the second operation. Ball 2 isn't, because it was removed at the third. Ball 3 isn't, because that was removed at the fourth. And so on. Whatever ball you name, say ball \(n\), it was removed at operation ball \(n+1\). So after we finish, there are no balls at all in basket B.

A bit more surprising is the fact that I can move as many balls as I like from basket A to basket B at each stage and basket B still ends up empty.

For example, suppose I move two balls from A to B at each stage, so in operation \(n\) I move balls \(2n-1\) and \(2n\) from A to B. Then after \(n\) operations, I've moved \(2n\) balls from A to B, and removed \(n-1\) balls, so there are \(n+1\) balls in basket B. The number of balls in basket B is growing larger and larger. Isn't it obvious that there will be infinitely many balls in basket B when I finish?

But no. We can use exactly the same argument as before. Ball \(1\) is removed at the second operation, ball \(2\) at the third, and so on. Whatever ball you think of, it is removed at some stage (though balls with a big value of \(n\) have to lie about in basket B for quite a while before they are removed).

Something funny is happening here. At stage \(n\), there are \(n+1\) balls in basket B, but after infinitely many steps there are none. Am I trying to say that when \(n\) gets really large, \(n+1\) is somehow getting near to 0?

No, I'm not that crazy. What I'm saying is that the number of balls in basket B at the end cannot be thought of as somehow being approached more closely to by the number of balls in basket B after \(n\) operations, as \(n\) gets bigger and bigger.

It's not hard to see that it doesn't matter how many balls I move from basket A to basket B at each stage, eventually all of them get removed from basket B, and basket B ends up empty.

In fact, I can even delay the process of removing balls from basket B as often as I want, or do it as rarely as I want (as long as I don't stop), and the result is the same. If I wait until operation \((n+1)^2\) to remove ball \(n\), then all the balls in basket B are eventually removed, even though I am putting balls in at every operation, and taking out a single ball at larger and larger intervals.

Here's a fun example. At operation \(1\) I move over one ball, then at operation \(2\) I remove one and move over three, and then at operation \(n\) I remove one and I move over \(n+1\) balls. After then \(n^\text{th}\) operation there are \(n\) more balls than there were before. Then after \(n\) operations, there are \(1+2+\ldots+n\) balls in basket B. So it looks like after I'm finished, there ought to be \(1+2+3+\ldots\) balls in basket B, but in fact there are none.

Of course, I'm not trying to say that \[ 1+2+3+\ldots = 0 \] any more than I would try to say that \[ 1+2+3+\ldots = -\frac{1}{12}. \]

You could even try to persuade yourself that this is reasonable: I put infinitely many in, and I take infinitely many out, so there are none left.

But there's more to it than that.

Basket B isn't necessarily empty

I put in a single ball at each operation. But I wait until after \(N+1\) operations before I start removing balls.

I could do this by first removing ball \(1\), then ball \(2\) and so on, and basket B would end up empty.

But I could also do it by first removing ball \(N+1\) in operation \(N+2\), then ball \(N+2\), and so on. When 13:00 rolls along, every ball with a label of \(N+1\) or more is gone, but balls \(1\) to \(N\) are still there.

So I can arrange for basket B to have any number of balls I want in it by choosing my removal strategy appropriately.

In fact, I can even arrange for basket B to have infinitely many balls in it.

One way to go about it is to move ball \(n\) from basket A to basket B at operation \(n\), and then alternate removing nothing from basket B and removing the next even-numbered ball. This leaves all the odd-numbered balls in basket B at the end, which is an infinite collection.

You may feel that's somehow cheating: you're only taking a ball out on every second operation: but I could also just remove the ball with the next number, so on operation \(2n\) I remove ball number \(n\), and that way I'm left with basket B empty.

Alternatively, I could move two balls from basket A to basket B on each operation, and take out one of those balls at the next operation.

So, the net effect of removing an infinite set from an infinite set can be to leave nothing at all, a finite set of any size you like, or an infinite set of the same size as the one you started with.

What does this tell us?

You can extract more than one possible message from this.

One message is that arithmetic involving the infinite has some counter-intuitive properties.

I think this is the commonest point of view: We have a game with all sort of interesting properties to explore, so we do. It's certainly mine.

If you take this point of view, you find that the infinite sets I've been looking at are only one kind: a set whose elements can be matched up with the positive integers is called countable, and what I've been calling infinite is really countably infinite. There are bigger (and bigger and bigger) kinds of infinity to play with, once you've sorted out what you mean by bigger when you're talking about infinite sets.

If this sounds like fun to you, then you might like to check out the properties of cardinal numbers.

Another is that arithmetic involving the infinite has unacceptable properties, so you reject it as a part of mathematics.

Some people take this point of view very seriously. They will accept the notion of integers of any size, no matter how big, but regard it as illegitimate to talk about a set of all integers, because that would have infinitely many elements, and they find the price too bit to pay.

If that sounds like you, or like you want to be, you might find it interesting to check out finitism .

Acknowledgement

Thanks to Adam Atkinson for pointing out some ambiguity in the first version.