But Did Homer Catch the Bus?

Before we get on to the continuum hypothesis, let’s talk briefly about what we did in the last post because it’s a nice introduction to an important idea. We saw that it was possible to add up infintely many things. Let’s discuss this in the context of one of the paradoxes we introduced last time.

Let’s think back to Homer running for the bus (introduced at the start of the previous post). Suppose the distance to the bus is 100 metres. The way the paradox is phrased makes it seem as though, by splitting up 100 into infinitely many bits, it is impossible for Homer to traverse the entire distance because he cannot do infinitely many journeys in a finite amount of time. The mathematical definition we discussed last time (that of a series summing up to a finite quantity – one of the basic ideas of mathematical analysis) ignores this potential problem.

We said that, in order to catch the bus, Homer must first get half-way there, at which point he still has to travel a distance of 100/2 metres. We then said that in order for him to get half-way there, he must first get a quarter of the way there, at which point he’d still have to travel a distance of 100/2 + 100/4 metres. Having got an eigth of the way there, he’d still have 100/2 + 100/4 +100/8 metres to go, and so on. Now, we can try to analyse this repetetive procedure by claiming that the total distance travelled is

100/2  +  100/4  +  100/8  +  100/16  +  100/32 + …

But does this series make any sense? Does it settle down and add up to a finite quantity? Well, this series really ought to sum to 100 and indeed it does, in the manner alluded to in the previous post: Provided we can add up as many terms of the sequence as we like, we can get as close as we want to 100. If you add up the first fifty terms (which is not that many considering it goes on forever)  you get 99.999999 to six decimal places. If you continue, you only get closer. The point of the mathematical definition of convergence is that this phenomena is precisely saying that the series sums to 100: The definition eliminates any potential ambiguity and allows us to go back to work, though it does not address the philosophical issues of the paradox.

The point I’m taking time out to make is that mathematics is just mathematics and cannot answer the paradox for us. We have a very good definition of when a series can be summed up: It is practical and genuinely useful and allows mathematicians to do all sorts of things and think about things that they wouldn’t otherwise be able to – including genuine real-world applicable things, but the definition is still, in a sense, an artificial construction put in place to make things neater for us. When you really start asking questions (as Zeno did, although this well before the advent of mathematical analysis of this kind) you are no longer in the realm of mathematics in my view.

Did Homer catch the bus? The analyst says of course he did/I don’t care. The philosopher still isn’t so sure and probably still cares.

Sizing Up

So, we’ve seen that some infinite sets can be put into bijection with the natural numbers (their elements can be paired off, one-by-one with the set {1,2,3,…}). These sets are called countably infinte sets. It is in this way that the natural numbers are the prototypic countable set. Some infinite sets are not countable (because no such bijection exists). These sets are called uncountable.

We have seen that the set of square numbers is countably infinite, as is the set of prime numbers, or the set of rational numbers (i.e. “fractions” or numbers whose decimal expansion just stops, like 0.4 for example). On the other hand, the power set of the natural numbers (the set of all subsets of the natural numbers) and the set of real numbers (numbers that can be represented by any sort of decimal expansion) are both uncountable.

Despite this neat characterization of infinite sets into countable and uncountable, a number of questions arise: Which is bigger, the power set of the natural numbers or the real numbers? Are there infinite sets which are bigger than both? Are there sets which are bigger than the natural numbers but smaller than both?

The Continuum Hypothesis

The first question we will dispense with by just coming out and saying that they’re the same size: There exists a bijection between the power set of the natural numbers and the set of all real numbers. We won’t go into how this is done, but it isn’t advanced.

The second is a bit more interesting. The ‘smallest’ infnite sets are countable sets and then the next biggest sets we’ve seen are sets which are as big as the real numbers, like, for example, the power set of the naturals. Can we get even bigger uncountable sets? The answer is yes, though it is not uncommon for sets that are larger than the real numbers to be thought of as monstrously large. An straightforward example of one such set is the power set of the real numbers: Just think, the real numbers are already bigger than the natural numbers, so the set of all subsets of the real numbers must be really huge! Though we haven’t rigorously proved that it is bigger, one can do so without too much trouble and, moreover, answering the question in this way also answers extensions of the same question: Are there sets which are bigger than the power set of the reals? Why yes, the power set of the power set of the reals is bigger…

The third question is very interesting: As before, on the one hand we have the natural numebrs – representing countable sets, and on the other hand we have the real numbers – representing the smallest uncountable set we have encountered so far. Is there a smaller uncountable set – a set which is bigger than the natural numbers but smaller than the real numbers? (For example, a subet of the real numbers which does not biject with either the naturals or the reals.)  The assertion that there is not such a set is called the Continuum Hypothesis.

Resolution

Georg Cantor, who I mentioned in the first post of the series, was the man who first put forward the hypothesis in 1877. After some very serious work in logic by Kurt Gödel in the 1930’s (which I mention in this post on the film Inception), the way was paved for Paul Cohen to unravel the mystery of its elusive proof. Cohen was an extremely impressive mathematician who, after starting off his career as a formidable analyst, went on to receive the highest honour in mathematics, the Fields Medal, for his work in set theory on the Continuum Hypothesis.

Taking Cohen’s work together with Gödel’s, they’d proved that one can neither prove nor disprove the continuum hypothesis, using the standard (most widely-accepted) rules of set theory. It simply isn’t possible to rigorously decide whether or not it is true or false. It is an undecideable proposition.  Probably why Cantor had so much trouble trying to prove it.

Advertisements