Problems that involve infinity have a tendency to read a little like Zen koans. Take, for example, this problem: Suppose we have three bins (labelled “bin A”, “bin B” and “bin C”) and an infinite number of tennis balls. We start by numbering the tennis balls 1,2,3,… and so on, and put them all in bin C. Then we take the two lowest numbered balls in bin C (that’s ball 1, and ball 2 to start) and put them in bin A, and then move the lowest numbered ball in bin A from bin A to bin B (that would be ball 1 in the first round). We repeat this process, moving two balls from bin C to bin A, and one ball from bin A to bin B, an infinite number of times. The question is, how many balls are in bin A and how many balls are in bin B when we’re done? Think carefully!

The difficulty is in being sure of your answer*. We require a way to think consistently and coherently about such matters. So what is the answer? bin A has *no tennis balls* in it, while bin B has an infinite number! Does that sound wrong? It certainly seems confusing: we are consistently putting two balls into bin A and only taking one out at each step, so how can we end up with no balls in bin A? The key is to think in terms of a finished state, when the infinite process is somehow “complete”. Every ball is eventually moved to bin B, thus after an infinite number of steps all the balls must have been moved to bin B. The counterintuitive aspect is that we don’t expect moving one ball at a time to ever catch up with moving two balls at a time, yet oddly this happens.

Another tale that highlights this point is that of the hotel with an infinite number of rooms**. The story usually begins with the hotel finding itself full one evening. A lone traveller then arrives, very weary, and asks the hotel manager if there is any chance at all that he can get a room. The hotel manager ponders this for a moment, and then has an idea. He asks each guest to move to the room numbered one higher than their current room. Since every number has a number one greater, and there are an infinite number of rooms, everyone is housed; and yet room number 1 is now empty, and the traveller has somewhere to stay. It doesn’t end there though. After the lone traveller, an infinite tour bus arrives, carrying an *infinite* number of passengers all looking for rooms. After having solved the first problem, however, the hotel manager isn’t phased. He asks each guest to move into the room with number twice that of their current room. Again, each number has a number twice as large, and there are an infinite number of rooms, so again everyone is housed; this time, however, everyone is housed in even numbered rooms, which leaves infinitely many odd numbered rooms in which the bus-load of tourists can be put up for the night.

This brings us a little closer to the sticky point where our intuitions start to go astray. For any finite number n we expect there to be (roughly, it depends on whether n is odd or even) half as many even numbers less than n than there are natural numbers less than n; when we have infinitely many numbers, however, there seems to be exactly as many even numbers as natural numbers. It’s this sort of unexpected equality with a set we initially intuitively think should be half as big that allows the tennis ball problem to fool us. In a sense, looking back from a completed infinity, 1 and 2 look pretty much the same. What it really comes down to, however, is the very simple question of what we mean by “how many”. As we’ve often seen before, the devil is usually in the details, and even simple things that we think we know and understand bear some thinking about if we want to be sure we actually know what we mean.

What happens when we count things? Because counting is a fairly innate skill for most adults it is helpful to consider what children, for whom counting is still somewhat new, do. Usually they count on their fingers (or other similar things), making a correlation between objects counted and fingers held up. At the more advanced adult level we do much the same thing, but we correlate with abstract objects (numbers, which by that time we’ve solidly beaten into instinctual memory). The point I’m trying to get at here is that counting is a matter of correlation; more importantly it is a very particular kind of correlation: in mathematics it is known as a one-to-one correlation. This means that each object corresponds with exactly one other object, and vice versa — in practice each object corresponds to exactly one number in our count, and each number in the count corresponds to exactly one object. If you can accept that, at the heart of it, it is that one-to-one correspondence that matters in counting, that it is the correspondence that ultimately determines what we mean by quantity, then we can pull out the mathematicians handy tool of abstraction and forget the other unimportant trivialities we might associate with counting, and use the idea of one-to-one correspondence to “count” infinite quantities. It might not be counting exactly as you would normally do it, but it will have the same core properties that matter about counting and quantity, and in the end as long as we can agree as to what important parts need to be preserved we can happily abstract all the rest away.

So how do we count infinite sets with one-to-one correspondences? Rather than actually counting infinitely many things, we provide an explicit process by which the count could (in theory) be done. Thus, we simply try to set up a one-to-one correspondence just as before, the difference being that it will be given as a rule we can apply element by element as needed, rather than having every single element to element correspondence laid out ahead of time. If such a correspondence exists then the sets have the same infinite quantity. And that is exactly what we are doing, for example, with the infinite hotel story. First we are comparing the sizes of the sets {1,2,3,…} and {2,3,4,…} by noting that we have a correspondence

1 | 2 | 3 | 4 | ⋯ | n | ⋯ |

↕ | ↕ | ↕ | ↕ | ↕ | ||

2 | 3 | 4 | 5 | ⋯ | n+1 | ⋯ |

and that since both sets are infinite we will have exactly one element in the second set for every element in the first set, and vice versa; a one-to-one correspondence. The sets have the same quantity — thus we can shuffle everyone down one room and still house them all. When the tour bus shows up we end up comparing the sizes of the sets {1,2,3,…} and {2,4,6,…} by making the correspondence

1 | 2 | 3 | 4 | ⋯ | n | ⋯ |

↕ | ↕ | ↕ | ↕ | ↕ | ||

2 | 4 | 6 | 8 | ⋯ | 2n | ⋯ |

where again the infinite sets ensure that each element corresponds to exactly one element in either direction; another one-to-one correspondence, demonstrating the sets have the same quantity — we can move everyone to even numbered rooms and still house them all.

At this point most people are happy enough to accept that there are the same number of even numbers as there are natural numbers. Their argument runs roughly “well there is an infinite number of both, and infinity is as big a number as there can be, so of course they’re the same”. There is, possibly, a little squirming under the fact that the what is clearly only a part apparently has the same size as the whole, but that tends to get swept under the rug of “infinity is as big as you can go, so we don’t have a choice”. The real problems start, however, when we come to the realisation that using this same idea of quantity (determined in terms of one-to-one correspondences) we can find sets with sizes larger than the set of natural numbers: there may be infinitely many natural numbers, but that is not as large as you can go!

The classic example of something infinite and larger in size than the natural numbers is the continuum (at least as classically conceived; the constructivist/intuitionist continuum is a little more tricky on this front) as discussed in Paradoxes of the Continuum, Part II. In that post we determined that points on the continuum were able to be identified with Cauchy sequences, which were akin to (though a little more technical than) infinite decimal expansions. We’ll stick with infinite decimal expansions here as most people have a better intuitive grasp of decimals than they do of Cauchy sequences or Dedekind cuts. To make things simple we’ll consider the continuum ranging between 0 and 1; that is, all the possible infinite decimals between 0 and 1, such as 0.123123123… We do have to be a little bit careful here since, as you should recall from Paradoxes of the Continuum, Part II, in the same way that there are many fractions that represent the same ratio, there were many Cauchy sequences that represent the same point in the continuum, and in particular there are different decimal expansions that represent the same point, such as 0.49999999… and 0.50000000… ***. To be careful we have to make sure we always pick and deal with just one representative in all such cases; to do this we can simply only consider representations that have infinitely many non-zero places. Showing this is sufficient, and still covers all real numbers between 0 and 1 isn’t that hard, but amounts to some technical hoop jumping that is necessary for formal proofs, but not terribly elucidating for discussions such as this. Suffice to say that it all works out.

The catch now is that we need to show not just that we are incapable of finding a one-to-one correspondence between these points on the continuum and the natural numbers, but that no such correspondence can exist. We do this by the somewhat backwards approach of assuming there is such a correspondence, and then showing that a logical contradiction would result. From that we can conclude that any such correspondence would be contradictory, and thus can’t actually exist (at least not in any system that doesn’t have contradictions). So, to begin, lets presume we have a correspondence like so****

1 | 2 | 3 | 4 | ⋯ |

↕ | ↕ | ↕ | ↕ | |

0.a_{1}a_{2}a_{3}… |
0.b_{1}b_{2}b_{3}… |
0.c_{1}c_{2}c_{3}… |
0.d_{1}d_{2}d_{3}… |
⋯ |

where the a_{1} etc. are just digits in the decimal expansion. The trick is to show that despite our best efforts to set up a one-to-one correspondence, the list of points in the continuum given by this correspondence (and since we haven’t specified what the correspondence actually is, *any* such one-to-one correspondence) is actually incomplete: we’ve missed some. We do this by constructing a decimal as follows: for the first decimal place, choose a digit different from a_{1}, for the second decimal place choose a digit different from b_{2}, for the third choose a digit different from c_{3}, and so on. Now clearly this decimal is between 0 and 1, and hence ought to be in our list somewhere, but by its very manner of construction it isn’t! How can we be sure of that? Consider any decimal on the list, say the nth one; now since in constructing our new decimal we specifically chose the digit in the nth decimal place to be different from the nth decimal place of the nth decimal on the list, even if our decimal agrees at every other decimal place, we know it differs at at least one — and if it differs at one decimal place, then it is a different decimal. Since that argument applies to every single decimal on the list, we are guaranteed that our constructed decimal is different from every decimal we’ve listed! Thus despite our assumption that we had a one-to-one correspondence, it isn’t, since we’ve found a point in the continuum for which there is no corresponding natural number. Given such a contradiction, the only conclusion we can draw is that we cannot create a one-to-one correspondence between natural numbers and points in the continuum — no matter how we try, we’ll always end up with extra points in the continuum for which there is no corresponding natural number; that is, there are more points in the continuum than there are natural numbers.

What all of this means is that we have to come to terms with the fact that some infinities are bigger than others. In fact, it gets even worse: some infinities are entirely incompatible with others. This particular catch hides in a slightly over-zealous abstraction of numbers. For the most part we do not differentiate between numbers describing order (2nd position, as opposed to 5th position, etc.) and numbers describing quantity (which is generally the notion of number with which we’ve been dealing). There is a perfectly good reason for this: when it comes to using and manipulating numbers using standard arithmetic, the numbers describing order (so called *ordinal numbers*) behave completely identically to those describing quantity (which we call *cardinal numbers*). As so often happens with abstraction (indeed, it essentially is the core idea of abstraction) if there are no practical differences (at least as far as the practical purposes we care about are concerned) between objects, we simply forget that there are any differences at all. And, indeed, for finite numbers this is a perfectly reasonable thing to do. The catch is that, once we start dealing with infinities, ordinals and cardinals start behaving rather differently — it is no longer safe to consider them the same, or even, for that matter, comparable to one another.

I won’t go into the rather technical theory of transfinite ordinals here, and instead just give you a precis of where the difficulties lie. To start, lets’ introduce some standard mathematical notation, and let ℵ_{0} denote the first infinite *cardinal* (that is, the quantity of natural numbers), and let ω denote the first infinite *ordinal* (that is, the first position reached after we’ve exhausted all finite positions). Now, as we’ve already seen, if we have infinite rooms, we can house an extra guest even if they’re all full; that is, ℵ_{0} + 1 = ℵ_{0}. On the other hand, if we tack on an extra position after ω and all the finite ones, i.e. we have 1st,2nd,3rd,…,ω,ath, then the ath position turns out to be appreciably different to all the positions before it. In other words ω + 1 ≠ ω. Now, whereas with finite numbers where are adding one produces the same result for both ordinals and cardinals, for infinite numbers it makes a huge difference (in one case we simply end up with what we started with, and in the other we end up with something entirely new). It shouldn’t be too hard to see that, from that simple difference, whether you have are dealing with a cardinal or ordinal transfinite number is going to matter for arithmetic operations; we can no longer ignore the difference; cardinals and ordinals have to be considered as quite separate and distinct kinds of objects!

At this point you might be trying to reconcile the fact that ℵ_{0} + 1 = ℵ_{0} with the previously observed fact that there are bigger cardinal infinities. How can we get to a bigger infinity if adding to ℵ_{0} ends up going nowhere? To answer that I’m going to need to discuss power sets. Given a set A (and for now we’ll keep things informal, the finer technicalities of what actually is and is not a set will come further along our road), the *power set* of A is the set of all possible subsets of A. An example will help clarify. If we have a set A = {a, b, c}, then the power set of A is ℙ(A) = {{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. Thus each element of the set ℙ(A) is itself a set, and in particular, a subset of A; note that we consider both the empty set and A itself to be subsets of A. With a little combinatorics you can see that if a set has n elements (where n is finite), then its power set will have 2^{n} elements (to make a subset we have to decide if each element is either in, or out, of the subset, thus we have 2 choices, multiplied together n times, or 2^{n}). The trick is that, using an argument that closely parallels the previous argument showing that there is not a one-to-one correspondence between the natural numbers and points in a continuum, we can show that even if a set has infinite cardinality it’s power set will have a larger cardinality. Thus, borrowing notation from the finite case, ℵ_{0} < 2^{ℵ0}. Using this trick, which applies to any infinite set, we can develop an entire hierarchy of different orders of infinity:

ℵ

_{1}= 2^{ℵ0}< ℵ_{2}= 2^{ℵ1}< ℵ_{3}= 2^{ℵ2}< ⋯

A similar, but different, hierarchy of infinite ordinals also exists (above and beyond the obvious option of simply adding one to an existing infinite ordinal to get a larger one), spiralling ever higher, this time using the concept of tetration***** rather than exponentiation. Contrary to initial expectation, infinities exist in infinite variety. How many infinities are there? We cannot say, on pain of paradox, since such a statement would only reflect back on itself in a vicious circle of contradiction.

While we began with just a hazy view of the infinite, the mists have cleared to reveal a strange and remarkable valley; a transfinite landscape with a veritable zoo of infinities of different kinds and sizes; it is, indeed, a whole new landscape of numbers and possibilities to explore; a hidden valley of the infinite. Running through the middle of the valley is a large river, and if we wade in we will find very deep waters. It is all a matter of asking the right questions. The question we can start with seems innocently simple:

Is the cardinality of points on the continuum bigger, smaller, or the same as ℵ

_{1}= 2^{ℵ0}?

The answer is deceptively complex. It can be established, with a little work, that the number of points in the continuum is not bigger than ℵ_{1}, which leaves us with either smaller, or the same size as ℵ_{1}. From there things get complicated quickly, and mired in a certain degree of technicality, but essentially the result is that the answer “doesn’t matter”. What I mean by that is we may assume that the number of points in the continuum is ℵ_{1} and no problems or contradictions will arise, yet at the same time we can equally well assume that the number of points in the continuum is *strictly less than* ℵ_{1} and still no problems or contradictions arise. Indeed, whether there is any cardinal number between ℵ_{0} and ℵ_{1} falls into this category. There is, in a sense, no “truth” here, merely preference.

This highlights deep facts about mathematics. When our journey began we considered numbers, and fractions, and algebra. Relatively speaking these are fairly simple abstractions, and, more importantly, they are abstractions that we tend to use each and every day (particularly in the case of numbers and fractions). Through a mix of immediate concrete associations due to the relatively low level of abstraction, and the sense reality imbued by constant use and exposure, we tend to think of numbers, fractions, algebra, and even mathematics itself, as something real, fixed, and concrete. That is, we think of mathematics as describing some platonic reality, that the objects it describes, while abstract, have some real existence. It is natural, then, to think that a number between ℵ_{0} and ℵ_{1} either exists, or doesn’t exist, in some real and concrete way — yet that is not how things have worked out. Imagine being told that whether the number five existed or not was quite optional, arithmetic would work just fine either way! We have, in essence, been told that existence is merely a preference, not a reality; “truth” is up for grabs, an option rather than a cold hard absolute.

Going all the way back to the first entry, On Abstraction, things start to get a little clearer however. As long as we view mathematics as a matter of making effective and powerful abstractions from the real world, rather than describing some platonic universe, having a choice of abstraction doesn’t seem so bad. We can choose how to interpret the continuum to suit our needs — indeed, we can even reject transfinite arithmetic and opt for the intuitionist conception of the continuum if we wish; we choose the abstraction that best suits our purposes for the moment. You could view it as little different than choosing to work at the genetic level as a molecular biologist instead of the considering subatomic particles as a physicist would: the level and manner of abstraction matters only with regard to the level and manner of detail you wish to obtain in the way of results. The more layers of abstraction we apply, the greater the chances of running into quandaries and choices; by abstracting away more and more detail, and by piling abstractions upon abstractions, we push further and further into the realm of pure possibility. This has the potential to lead us to strange and confusing trails, but it also gives us the power to see beyond our own limited horizons. In broadening our minds to embrace worlds of possibility we conceive of realities that transcend our conceptions, and probe our own reality in ways far beyond the limits evolution has shackled our perceptions with.

It has been a steep climb, but we have left the plains of ordinary finite numbers far behind us. We’ve crested the peak, and found a world that is strange and new. It gives us a chance to stretch our minds and our conceptions, and to begin to change how we look at the world. Equally importantly, it gives us a foundation for the further climb to come, providing a glimpse of the dance between logic and mathematics that will follow. We passed by the crossroads of unreality some time ago, yet there is still a very long way to go.

* If you are sure of your answer then either you already know a decent amount of transfinite theory, or you’re most likely wrong — don’t be disappointed about being wrong though; the very reason we need clear logical guidelines for reasoning about the infinite is *precisely because* our intuitions are woefully inadequate and misleading.

** The story is usually attributed to David Hilbert, but this is my own spin on it; errors and lack of clarity that may have crept in via the retelling are, of course, mine.

*** People have a tendency to object to this, and other similar claims, such as that 0.99999… is equal to 1. The easiest way to see this simple but slightly unintuitive fact is to note that we should be able to take 0.99999…, move the decimal place right one place, subtract 9, and arrive back at the same value (this is akin to shifting the hotel guests down one room to make a spare room at the front, but in reverse). That is, if x=0.99999… we can say that 10x – 9 = x. A little simple algebraic manipulation quickly yields x=1. This sort of sleight of hand with infinite expansions will also play a role if and when we come to p-adic numbers, and discover that, in that case, negative numbers are really just very big positive numbers!

**** The wary should be asking how we can even have a first element among points in the continuum (keeping in mind, of course, that there are cunning ways of ordering fractions such that there is a first element). This question quickly wades into very deep waters indeed — we can appeal to the Well Ordering Principle, which essentially just asserts that this can be done, or its equivalents such as the Axiom of Choice, or Zorn’s Lemma; all of these are somewhat contentious and tricky. If you’re interested it is well worth doing a little reading about them. We may come to discuss these issues ourselves later when we start to cross back and forth between mathematics and logic further down the road with Topos theory.

***** Tetration is kind of like exponentiation on steroids; or, more accurately, it’s the next layer of abstraction up: whereas the number in exponentiation counts the multiplications to be performed, the number in tetration counts the exponentiations to be performed. Thus the 4th tetration of 3, written ^{4}3 is equal to 3^{(3(33))}, which is 3^{19683}, or really rather remarkably large.

July 3, 2007 at 1:37 am |

an excellent post Jed.

I especially like where you’ve ended up, and where you seem to be going.

July 3, 2007 at 6:12 pm |

You lost me at the “Is the cardinality of points” question (I’m not a mathematician), so I had to skip some, but what I understood was very interesting, thanks!

July 4, 2007 at 3:56 am |

That last exponent should be ℵ2.

I assume by this you mean something like CH is independent of ZFC. How can you distinguish truth from preference here? From the start, in setting everything up, independent choices were being made. Why do they get a greater, lets say, “truth rank”?

I don’t see this as “making” abstractions, but as choosing paths through a greater platonic world to explore. I may even reverse your statement and say that it is the platonic that does the describing, rather than being described. Kinda like Max Tegmark stuff..

(Didn’t mean to be too negative here – I agree with torshin’s comment, nice post, as usual.)

July 4, 2007 at 4:22 am |

[…] read more | digg story […]

July 4, 2007 at 3:39 pm |

Jesse: You’ve provided a reminder that I need to do a better job of greasing the rails for closet platonists. To be honest I tend to have enough trouble believing that people are closet platonists that I tend to just assume they’ll be rouhgly in line with my way of thnking. That, of course, is far from the case. Let me elaborate on the whole “truth” issue with regard to things like the CH.

We can make the statement “the next largest number after ℵ0 is ℵ1”. That statement is (in classical logic anyway) either true or false. Except it isn’t. Not in ZFC, and not in NBG (which is to say any set theory of note that admits transfinite numbers). In both ZFC and NBG it is neither true, nor false, but rather something that you have to declare one way or the other.

You ask, reasonably, why the axioms of ZFC or NBG get to be called “true”, yet our choice of making the CH go one way or the other axiomatically doesn’t. The answer, from my point of view, is that ZFC and NBG aren’t “true” either, just yet more convenient abstractions. I could also go with intuitionist set theory and have the CH become incoherent, or make other choices again. At that point I’m not just deciding on mathematical facts, but logical ones (and we’ll see, eventually, hopefully, that these are actually deeply intertwined anyway), thus I can pick my logic, and even my conception of truth. Now absolutely everything is up for grabs. There’s no bedrock to stand on, no platonist “reality” that is somehow “out there” and (*pound the table*) “real”, just a whole slew on conditional options and consequences.

You can try and take the result as exploring different paths within a “greater platonic world”, but with no base to start from that world and its “reality” have become meaningless, since absolutely everything and anything is “real” somewhere in that world, sayign something is “real” or “exists” becomes moot and meaningless; it carries no distinction, and tells us nothing.

Perhaps it helps to make it clear that I’m a logical pluralist; I don’t believe in the “reality”, or “truth” of any logical system, but rather their convenience, utility an effectiveness. I don’t view mathematical objects as “real” and “out there”, but rather as useful fictions that are “in here”. We can still “discover” mathematical facts, as in uncover previously unconsidered consequences of the system we have chosen to consider; I just don’t see that as uncovering some underlying real “truth” that is out there and fundamental to reality somehow — that would require an absolute bedrock on which to ground basic “truth”, which I don’t see that we have.

In essence I see he CH as providing the first step on this slippery slope. People tend to think of numbers as “real” because they seem to have a concrete solidity, to exist in some substantive way, and to be describing some fundamental truth. If I were to say that “the next number after 4 is 5” is a purely optional “truth”, that you can accept it, or deny it (or, perhaps that “2+2=4” is purely optional) many people would be rather appalled; for them numbers are real, and facts about numbers are something concrete. Yet in ZFC transfinite cardinals are every bit as real as integers, and yet we have almost exactly that statement turning out to be purely optional. The concrete reality of numbers is in practice not so concrete, and the deeper you dig the more everything falls away.

July 6, 2007 at 1:16 am |

Thank you for that long response, though I’m surely getting in over my head.

Could you tell me what some of the consequences of this choice are?

I agree, in a way.

I am much more interested in these options and consequences than the reality of the ideas. In my head I keep getting the image of mathematics as a giant directed graph, with edges for implications.

Right – whether it is part of the world is not important. However, the structure of the world is.

“Reality is that which, when you stop believing in it, doesn’t go away”, according to Philip K. Dick. I don’t know about you, but I rather like that definition.

July 6, 2007 at 6:13 pm |

Jesse: The main consequence is how “rich” a universe of sets you end up with. If you reject CH then you get a much “richer” wild and woolly universe of sets, while accepting it gives you a universe populated only by constructible sets (which is rather more restrictive, but not as restrictive as constructive sets).

With reagrd to directed graphs — that’s a reasonable view. What we are looking at here is the realisation that there is no “true” choice of root nodes, merely convenient ones. Results are not “real” or “true” in any absolute platonist sense, but instead just “true” in the local universe you’ve deemed it convenient to work in. There is no absoluteness, no solidity. The trick is realising that this isn’t a bad thing.

This sort of localised pluralist view is, of course, much easier in Topos theory where each elementary topos provides a local language and local set theory. You simply pick the topos in which you wish to work, and that’s a matter of convenience of efficacy, not of “truth” or “reality”.

July 6, 2007 at 9:23 pm |

Nice article. While I was familiar with most of the things you talked about, I enjoyed the way you expressed them.

I have a question about your very first example, though. Something about that process seems… “divergent”, if I can use that word in an non-rigorous manner. Isn’t it more appropriate to say that there is in fact no “done” state?

Thinking about it for a while, I can see how you can say that no balls end up in A if you think of all the transfers happening instantaneously. But the original problem is posed as a process with an infinite number of steps, and with such things it’s usually only meaningful to talk about a final state if the process shows convergence of some kind. It feels very similar to the problem of summing 1 – 2 + 3 – 4 + …*. And if you’ll allow me to make a computer science analogue, a computation with an indefinitely increasing stack probably wouldn’t be considered a terminating computation, even if you were permitted infinite time to run.

* I have no idea whether Euler’s answer of 1/4 is at all relevant here. I don’t understand that solution very well in any case.

July 7, 2007 at 3:41 am |

Rahul: It may help to actually draw out what happens for a few steps. If the starting state (bins A & B empty) is step 0, and each step consists of both moves, then ball number N will get to bin B at step N. Bin A never even overtakes bin B in size.

July 7, 2007 at 3:49 am |

Another explanatory idea: instead of thinking about bins, image the stack of integers and two arrows pointing between where the bin borders would be. So at step 1, the pointers are at 1.5 and 2.5. At step 2, they’re at 2.5 and 4.5. At step N, they’re at N+1/2 and 2N+1/2. Both pointers just steadily slide upward; the higher one doesn’t really matter, the lower one will pass everything eventually.

July 7, 2007 at 8:31 am |

Sure, Jesse, I understand that. If you think about what happens to, say, the i-th ball, it’s pretty obvious that it’ll end up in bin B at step i and stay there. That’s a perfectly formal argument, and I’ll grant that what I said in my previous comment was quite informal in comparison. I’m still rather wary, though, because it seems that an indefinitely increasing number of balls is being swept under the rug of infinity here. Here’s what worries me: you can easily “prove” that 1 + 2 + 4 + 8 + … is less than zero, by an apparently rigorous series of steps:

S = 1 + 2 + 4 + 8 + …

2S = 2 + 4 + 8 + …

S – 2S = 1

S = -1

The only problem is that if you expand S to any finite number of terms, you have an arbitrarily large power of two left over after the subtraction in the third step, so the series doesn’t ever converge at all, let alone go below zero. It seems to me that this is pretty similar to what’s happening with the balls trick — you have a growing number of balls in bin A, and you tuck them away into the elliipsis and expect them to all disappear “at infinity”, and of course you end up with an apparently impossible result.

Here’s another thought: why does the order in which you choose the balls matter? If I choose to move the *largest* numbered ball from A to B, I’ll end up with all the odd balls in A and all the even balls in B, even though at each step I’m moving exactly the same number of balls as you are. The trick also depends crucially on the balls being *distinguishable* — if they were completely identical balls, or equivalently if I close my eyes and move *some* ball from A to B without knowing which, you can’t really say anything other than that lots of balls will end up in A and lots of them in B, and the process doesn’t really have a nice stable termination state.

So all I’m trying to say is that you can either go ahead with an apparently rigorous derivation of a counterintuitive result and say that infinity is nonintuitive (which it is, but my complaint is with this example), or you can decide that the process is divergent and its result is not well-defined at all. That’s pretty much what people do in real and complex analysis all the time when dealing with infinite series, in order to avoid applying otherwise exact formulae like 1 + 2 + 4 + 8 + … = 1/(1-2) = -1. I’m not sure if things are different in number theory.

July 7, 2007 at 1:58 pm |

Rahul: Yep, you can get into some sticky situations with this stuff. E.T. Jaynes does a pretty good job of explaining in his book Probability Theory: The Logic of Science. Some old fragments of the book can be obtained here:

http://omega.albany.edu:8008/JaynesBook.html

Appendix B contains the especially-relevant section ‘Our “Cautious Approach” Policy’ (B.2 in the final book). (Also, the final book has “B.6 Counting infinite sets?”, though I don’t see that in the online fragments). Jaynes emphasizes the importance of the *process* by which you take a limit.

In your ‘move the largest ball from A to B’ example, ball N will end up in A at step (N+1)/2 if odd, or B at N/2 if even. In your ‘pick randomly’ example, its true that you can’t say exactly when a ball will end up in B. At step N there will be a 1/(N+1) chance for each ball in A that it’ll move to B. Hmm.. since B has size N at step N, maybe you could say there is a 1-to-1 correspondence between steps and the number of numbers in B.

Maybe this doesn’t address your worries; just thinking aloud..

July 7, 2007 at 4:45 pm |

Rahul: Yes in some sense things are getting swept under an infinite carpet, but strangely legitmately so. These problems are deep, and the technicalities tricky, and our intuitions remarkably poor. Perhaps a better way to see what’s at work with the tennis balls is to consider the infinite hotel instead. If we convert that example into a progressive process as well, we find the same “problem” arising. Start with a hotel with only 2 rooms, then one with 4, then one with 6, then 8, and so on. If we try to move guests to rooms twice their current room number we find that a number of guests are left without rooms. As the number of rooms in the hotel increases, the number of roomless guests increases. And yet when we have infinite rooms most people can see, and agree, that in some way there are no roomless guests after the move. The tennis balls work essentially the same way.

In some sense it is the difference between building a bridge toward infinity via limits as discussed in Paradoxes of the Continuum, Part I, and contemplating a whole and complete infinite. It is that “already complete” infinite that makes the difference, as subtle a distinction as that sounds at first. It is also a philosophical issue; some, such as intuitionist/constructivist mathematicians will reject any conception of a

completedinfinite and only accept thepotentialinfinite of limits. Perhaps you fall in that camp. Personally I view neither as more true, or more real than the other; they are simply different approaches with differing value depending on the perspective you wish to take.July 9, 2007 at 2:47 pm |

Hi, am not a mathematician (nor do I play one on TV), came here via SlashDot. On the subject of the “Infinite Tennis Balls” problem, I’d say that at the end of the run, there would be *infinite* balls in *all* bins.

That’s the problem with infinity. It doesn’t end, so you can’t really put a limit on it or speak in terms of a state of completion. Our little human pea brains just don’t have the circuits to deal with such thinking.

Good article, though. I still believe having a firm grasp of logic will help any programmer: the more you can abstract the task, the smaller & cleaner the code, the less to debug.

Take care!

July 9, 2007 at 3:43 pm |

Carl: I suggest you glance back through some of the previous entries. Here we are discussing the theory that would result if we are to consider completed infinities — that is, specifically, infinities that we’ve gotten to the end of. You can, if you wish, posit only potential infinities and disallow the notion of a completed infinity, but that simply results in a rather different theory. If that is what you wish to go for then I suggest you look into constructivist mathematics, which specifically disallows completed infinities. This raises issues with how to handle continuums (see Paradoxes of the Continuum, Part I, and II, and the potential paradoxes that result).

On the other hand, if we accept completed infinities, and develop the transfinite theory as described here, we can use that to create a powerful conception of the continuum, and mathematics that allows us to contemplate and work with continuums very effectively.

July 12, 2007 at 10:46 pm |

Leland: I think you nailed it in the last paragraph of your penultimate comment — the difference arises in whether one thinks of infinity as the limiting case, rather than a “completed” entity in its own right. I’ve been arguing from the former camp, probably because I’m more familiar with real analysis and numerical methods than, what should I call it, the mathematics of discrete infinities? In those areas, you’re pretty much guaranteed to shoot yourself in the foot if you don’t worry about convergence.

From the other point of view, I can see that the all-balls-in-B result would not be considered paradoxical. Interestingly, I thought a bit more about the variation I suggested of moving a randomly chosen ball rather than the lowest numbered one — it turns out that any given ball has zero probability of staying in bin A. I had originally hoped that it might converge to a finite nonzero probability, which would have been a strong argument that the setup of picking the lowest numbered ball was simply an pathological special case, but I was wrong there.

It’s been fun thinking about all this though. I’ll have to go read your previous posts on Paradoxes of the Continuum sometime. Cheers!

August 7, 2007 at 1:17 am |

[…] in exactly the same pattern of marbles, is something we discussed and resolved in our parallel road considering the nature of the infinite. And so now, having scaled the heights, we find we can look back, out across the vast bay with an […]

August 7, 2007 at 10:53 pm |

This is a fascinating concept to me. I’m looking at the problems from the angle of computation theory and I’ve always held the opinion that by introducing a finite limit, all problems are generally solvable (just as Bin A will have generally have as many balls as Bin B). The idea that there are no balls in Bin A is about as realistic as saying a problem is uncomputable – both may be strictly provable but not within the realm of experience (before the numbers fall off the table and start making a mess on the floor).

I’m all in favour of rearranging number theory to add a special finiteness limit where a line be drawn to say, “OK, we’ve reached the edge of Flatland, we have completed X rounds of ball tossing and the result is X balls in Bin A, X balls in Bin B and Deep Thought can simulate all particle interactions for an entire solar system (and pass the Turing Test with ease)”. “Beyond that line, Bin C doesn’t feed Bin A as fast as Bin A feeds Bin B” and Deep Thought has given up hope”. Oh and there are an infinite number of Quaternions in infinite complex dimensions (the assumption of just i & J on the Z axis is Flatland talk).

Back to the Bin problem – if bin A is always fed before bin B, there will always be an equal number of balls (since bin c is infinite and never runs out). Also you mention the balls being moved in a ‘process’ which is repeated an infinite number of times. Is that number of times more or less infinite than the number of balls ? As I recall there are more infinite numbers on a curved number line than a straight one.

Congrats on the Phd BTW and thanks for the smiley at the bottom of the page !

August 8, 2007 at 7:21 pm |

When discussing INFINITY, even the best mathematicians,physicists, philosophers, minds, etc, get themselves into trouble. Infinity, as you have pointed out several times, is a MATHEMATICAL ABSTRACTION. There is in fact no such thing!, (except in fairyland). Your “infinite number of balls in bin A” is an example of a rubbish statement. A ball, a bin, are

PHYSICAL ENTITIES, they exist in the real world. To use such real world examples to explain a concept that exists only in the mind is ludicrous.

The poor finite mind can be easily duped through the skilfull use of WORDS to follow the stupidest of arguments to ‘feel’ as though they “get it”. They have been lulled into a mind trap! Beware all arguments that invoke the concept of INFINITY.

john.

When the purely imaginary notion of infinity is introduced into scientific discourse, ANYTHING IS POSSIBLE!

August 9, 2007 at 3:24 pm |

John: Yes, infinity is a mathematical abstraction, but so are finite numbers. Finite numbers “don’t exist” either; at least they have no physical existence. Perhaps the distinction you can make is that examples of sets having the property of a finite number of elements exist, while perhaps no sets with inifnite elements exist… but this then runs afoul of the continuum, and the problems mentioned in Paradoxes of the Continuum, Part I. You either need a very different conception of the continuum, or to deny the existence of any continua — to claim that time and space are discrete; a claim for which there is no evidence other than your philosophic distaste.

As to the existence of the balls and bins; I would point out that, unless you decided to be very literal and go and fetch some bins and balls, they did not, in fact, exist in the real world, but rather as an abstraction in your own mind as a mental thought experiment. The balls and bins under consideration are every bit as imaginary (or as real for that matter) as infinity: they are abstract mental ideas and we can do as we wish with them to explore the realm of the possible (rather than the mere actual).

As to your final comment that introducing infinity to scientific discourse results in nonsense: I would point out that calculus and the vast majority of modern physics rests very solidly on such notions of infinity and continua. “Anything is possible” only if you fail to work rigorously through things. Infinity has constraints, just like any other number, and in practice it provides a very good model for a great many actual phenomena in the real physical world.

August 13, 2007 at 8:26 am |

I had the same problem as Rupert there – my background is in computer science, and I pictured the process as one that at every point of its infinite execution time has a finite state – if you simulated the process on a turing machine (infinite memory, infinite execution time), on step N you would nave N balls in both A and B, and (+inf – 2N) balls in bin C, just as Rupert has already pointed out.

The problem, I found, was in that infinities tend to “propagate”* in computations, which is oh-right from a mathematical and logical standpoint, but seems kind of useless in such simulations.

Now that I thought about it, I found myself asking why we need such “finished state infinities” if they give such counterintuitive and and so different results from our simulation on a turing machine – they obviously aren’t useful for modeling infinite simulations. I therefore think that the example is just chosen poorly – it is given as an algorythm, a sequence of finite states, a process – and you cannot accurately model an infinite process by infinities, as my argument goes.

It is because of this I think that the hotel analogy is much better to illustrate infinities – and, at the same time, not equal to the bin case (as has been suggested), even though they both (potentially) distill into the same set of equations – equations for the bin process are flawed.

* by propagate I mean (+inf – N) = (+inf), (+inf / 2) = (+inf) etc. Any modifiers you apply to infinity result in the result being infinity.

—

Since it’s my 1st time posting here: Great work, I like the articles a lot. I have chosen to study maths (at university) and your articles are very encouraging, even though I already know most of the stuff in them, even the not-so-much-facts-about-maths details. They make me long for the start of the semester so I can dig into the nitty-gritty of all the different subjects you just skim over here. Thank you, and keep it up.

August 13, 2007 at 5:57 pm |

Gasper: This is the difference between the

potential infinite, and thecompleted infinite. Computational infinity is, and will only ever be (as long as we’re talking about Turing machines)potentially infinite, it can never actually complete the infinity, only approximate it with ever larger finite values. The completed infinite has its philosophical difficulties, as well as being incompatible with a computational approach, but it also has its own qualities and usefulness. Thinking in terms of completed infinites is hard, especially if you’re used to only considering potential infinites, but that doesn’t make the reasoning false. I suggest you consider my responses to Rahul and Carl earlier, as it applies here to you as well.September 27, 2007 at 8:06 pm |

Leland McInnes had asked:

“We repeat this process… an infinite number of times. The question is, how many balls are in bin A and how many balls are in bin B when we’re done? Think carefully!”

It was a trick question, of course The correct answer is, you’re never done.

October 1, 2007 at 6:34 pm |

Geoffrey: The question is hypothetical, an abstraction, and presumes the existence of completed infinities. Indeed, if you read Paradoxes of the Continuum, Part II you will see why we are contemplating completed infinities — there is good reason, and as long as we are working in the abstract (and really, that’s what mathematics is, we may asssume what we wish, as long as we are clear on what our assumptions are) we are free to do so and contemplate what the consequences would be. Of course you are equally free to take a different philosophical stance, but that does not negate the validity of the reasoning contingent upon the assumption of completed infinities. Instead you have a different task, which is to resolve issues without having to ever resort to contemplating anything but potential infinities. This is a very different road, and leads to constructive and/or intuitionist mathematics, which hs its own interesting sticking points. Eventually I hope to come around and develop calculus in a world without completed infinities, using a very different conception of the continuum — that is not now however, we need more background before we can begin to explore that line of thought in the manner I would wish.

April 11, 2008 at 6:32 pm |

“Is the cardinality of points on the continuum bigger, smaller, or the same as ℵ1 = 2^ℵ0?”

IANAST (set theorist), but I don’t think that’s correct. The CH question asks, “Is ℵ1 = 2^ℵ0?” It has been established that the cardinality of the continuum is c = 2^ℵ0. Negation of CH is the same as “c = 2^ℵ0 > ℵ1”.

June 9, 2008 at 11:55 pm |

The problem is not stated clearly. What if Bin C is empty? Do we still move a ball from A to B?

You make the assumption that the steps are unrelated, whereas most people would assume that they are linked. Once Bin C is empty, would you STOP moving balls from Bin A to B. If not, then it is clear that B will have all of the balls. If you WOULD stop, then would you change your answer?

If the problem were restated to be:

…we take the two lowest numbered balls (always one odd and one even numbered ball) in bin C and put them in bin A, and then move the odd numbered ball in bin A to bin B (that would be ball 1 in the first round). We repeat this process, moving two balls from bin C to bin A, and one ball from bin A to bin B, an infinite number of times.

It’s clear that Bin A and B have the same number of balls, odd and even.

It seems like a similar one-one correspondance could be made in your problem between the number of balls in A and B, but I can’t think of a way at the moment. It’s troubling, because another variant is:

…we take hundred lowest numbered balls in bin C and put them in bin A, and then move the lowest numbered ball in bin A to bin B (that would be ball 1 in the first round). We repeat this process, moving 101 balls from bin C to bin A, and one ball from bin A to bin B, an infinite number of times.

Would you say that all the balls would be in Bin B, because any particular ball has non-zero chance to be moved?

Even more interesting is:

…we take hundred lowest numbered balls in bin C and put them in bin A, and then move the HIGHEST numbered ball in bin A to bin B (that would be ball 100 in the first round). We repeat this process, moving 101 balls from bin C to bin A, and one ball from bin A to bin B, an infinite number of times.

It seems that it should be provable that ball #1 will never be moved.

An interesting problem. Thanks!