Finding Cantor’s proof that there are transcendental numbers

I’ve just posted a question at Mathoverflow challenging people to come up with examples of proofs that appear to require a sort of “cognitive leap” that humans are surprisingly good at and that it is hard to imagine computers ever being capable of. I don’t myself believe that there is some fundamental way in which humans are better at mathematics than computers are (or rather, could ever be). So this is the first of what may turn into a series, if I have time, of posts in which I shall try to demonstrate that examples that have been suggested are of proofs that a computer program could in principle find too. (Many of the examples suggested are in areas where I have absolutely no hope of doing this: I’m not going to be able to tell you how a computer could have invented Thom’s work on cobordism, for instance.)

In this post I want to tackle a proof that was a pretty radical departure when it first came out: Cantor’s indirect proof of the existence of transcendental numbers.

An initial problem is of course to specify what the computer can be assumed to know already. I suppose the short answer is that it can know the mathematics that Cantor knew before he came up with his argument. Should that include the harmonic analysis that he worked on before he turned to set theory? Perhaps, but I won’t make use of that in this account. However, what we can assume is basic facts about the real numbers and sequences, such as the convergence of bounded monotone sequences, the Bolzano-Weierstrass theorem, the nested-intervals property, and so on. And of course, the major thing that we cannot assume is anything that remotely smells of the definition of countability.

It’s very hard to get the proof (by which I mean the one that uses nested intervals, which was Cantor’s first proof) out of one’s head enough to think about this. I feel a strong temptation to give the usual steps and explain why they are sensible — but that is justifying with hindsight, which is easy.

Now one idea that was already around, since it was what Liouville did, was that you could produce a transcendental number as the limit of a sequence. In fact, and this is something that’s only just occurred to me, you can even think of Liouville’s argument as a sort of unnecessarily complicated diagonal argument. What do I mean by this? Well, he shows that for any height (by which I mean largest modulus of a coefficient of the minimal polynomial), any degree and any closed interval of positive length there is a closed subinterval of positive length that contains no algebraic numbers of at most that height and degree. His number is just an explicit number that lies in the intersection of some intervals that between them rule out all algebraic numbers. So the differences between Liouville’s argument and Cantor’s argument are (i) that Liouville rules out whole sets of algebraic numbers all at once, whereas Cantor picks them off one by one, and, much less interestingly, (ii) Liouville actually chooses an explicit collection of intervals that does the job, when it’s obvious that there are all sorts of numbers that are transcendental for the same reason.

Let’s suppose that Cantor was thinking hard about Liouville’s argument. (This has switched from “How could a computer do it?” to “How could a human do it?” but I regard these two questions as essentially the same, as long as you don’t appeal to moments of genius, flashes of inspiration, etc.) He would have noticed (perhaps not completely consciously) the following very important feature: Liouville does not produce the number all in one go, so to speak. For instance, he does not choose a number such as or Rather, he constructs a sequence such that its limit is algebraic.

Now how does constructing a sequence make things easier for Liouville? The answer is that it allows him to split the problem up into a whole lot of subproblems: make sure you avoid these algebraic numbers, then these ones, then these ones, and so on.

It’s not all plain sailing though, since if you are taking the limit of a sequence, then at stage you don’t know what’s going to happen later on. So you must make little promises as you go along: I promise that whatever I do later on, the limit will be close enough to this number here that the argument so far remains valid. But for that to be possible, you have to find not just a single point that rules out a whole bunch of algebraic numbers, but an entire interval of points. (Or rather, it isn’t obvious that you absolutely have to go for an interval, but it is a lot easier to ensure that the limit lies in an interval than it is to ensure that it lies in a more complicated set. And in any case, Liouville’s proof does give an interval.)

If you hadn’t seen Liouville’s argument either, then it is quite easy to imagine being stuck in the following rut. The proof that there is an irrational number goes, “Here’s an irrational number.” So it’s sort of obvious that if you want to find a transcendental number then you have to do the same sort of thing: you go out and find some numbers like and and you do your best to prove that they are transcendental. The idea of constructing a number using a limiting process is rather different. Having said that, it is not without precedent. By the time of Liouville, the intermediate value theorem had been proved, so anyone who had thought carefully about why exists would be familiar with the idea of limiting processes.

But to go back to Cantor, he might have had the following kind of thought: “Liouville created a sequence with a transcendental limit. What is the most general form of this argument I can come up with?” (It is an interesting question whether computers could do this kind of stepping back and generalizing. I think that under certain circumstances they should certainly be able to. A particularly simple example is generalizing hypotheses — e.g. when you’ve proved something additive about the integers mod , see if you can prove it for all groups — or removing them entirely.) “Well, if I’m creating an increasing sequence, I’ve got to make sure that the first term has some property that stops it being equal to some bunch of algebraic numbers, and that if I perturb it slightly then it still has that property. Hmm, which numbers did Liouville rule out by insisting that his number was very close to 0.1100010000…0001? If you look carefully at what he actually proved, you see that no number that is very close to this one can be a root of a polynomial of degree at most some d with coefficients that aren’t too large in modulus. What can we say about the set of such polynomials? Well, it’s obviously finite for a start. But hang on! If it’s finite, then that’s only finitely many roots of polynomials that Liouville has ruled out by this stage. We didn’t need some special number to do that! It’s obvious that we can find an interval that avoids a finite collection of numbers. What was Liouville thinking? Actually, if we pursue this thought we have a very nice abstract version of Liouville’s argument. By gradually increasing the degree and the maximum size of a coefficient, we admit all roots of polynomials, but we admit only finitely many at a time. So inside the first interval I can find another interval that misses another bunch of algebraic numbers, and inside that I can find another one — wow, I don’t need any of that rational-approximation stuff that Liouville went on about.

“In fact … I don’t even need the numbers to be algebraic! This is crazy! All I need to know is that I can divide up the numbers I’m trying to avoid into a sequence of collections of numbers, each of which is finite. Of course, if I can do that, then I can put my numbers in a sequence, since I can just write out those finite collections in increasing order. Conversely, a sequence of numbers is basically a sequence of collections of numbers where each collection contains just one number. What I seem to have proved here is that for any sequence of real numbers I can find a real number that is not equal to any term in that sequence. Wow, I quite like that — it seems to get to the heart of why there are transcendental numbers but be massively more general.

“But hang on a moment. That’s quite strange, because it’s sort of saying that if I match each positive integer to a real number, then I must miss out a real number. In some sense, there seem to be genuinely more real numbers than there are positive integers. It’s almost as though we’ve got an infinity that’s ‘bigger than infinity’. Hmm … I’ll think about that tomorrow.”

I think some kind of account like that shows that even though Cantor’s argument came as a big shock and was resisted by many, we do not have to make a lazy appeal to his genius (and still less his madness) to explain how he could have come up with the idea. It was a radically new approach, and yet it grows naturally out of the old.

That is not to belittle Cantor’s achievement. It is hard to imagine, writing comfortably in the twenty-first century, what kinds of background assumptions Cantor must have been taught and must have had to set aside. Perhaps that is what we really mean by genius in this instance — not that the idea popped into his brain by means of some utterly inexplicable process, but rather that he was sufficiently flexible to follow his thoughts where they naturally led, without letting himself be distracted by hidden assumptions. (This makes me think of special relativity — perhaps it is reasonable to say that the genius there was mainly daring to question “obvious truths” such as that velocities add and that simultaneity is an absolute concept. The mathematics itself is not hugely hard.)

A natural question at this point is how Liouville might have thought of his argument. I’ll leave that one for another day.

One final note: I did not introduce the word “countable” into my fictitious account of Cantor’s thought processes. Apparently Cantor didn’t do so for some time after he came up with the argument. If you present the argument in the usual way — first we prove that the algebraic numbers are countable, then that the reals are uncountable, and from that it follows that there exists a transcendental number — then you are making it look as though the idea of countability springs from nowhere. But in fact it can emerge naturally from the observation that Liouville’s sequence deals with finitely many algebraic numbers at a time and eventually deals with all of them.