To infinity and beyond!
—- Buzz Lightyear (Toy Story)
Cantor invents the ordinals
Cantor (Georg Cantor, the founder of set theory) did not set out to revolutionize mathematics. He was working on a respectable problem of analysis (roughly, generalized calculus): proving that the Fourier series of a representable function is unique. He stumbled on the ordinals (or, if you will, he invented them).
He developed an approach where problems with uniqueness were limited to a set S0 of ‘bad’ points. But he discovered that patching could eliminate the problem for isolated points – points that have a minimum distance from other points in the set.
Wikipedia accurately describes the procedure:
Cantor had discovered a procedure that produced another trigonometric series that had S1 as its set of zeros, where S1 is the set of limit points of S. If Sk+1 is the set of limit points of Sk, then he could construct a trigonometric series whose zeros are Sk+1. Because the sets Sk were closed, they contained their limit points, and the intersection of the infinite decreasing sequence of sets S, S1, S2, S3,… formed a limit set, which we would now call Sω, and then he noticed that Sω would also have to have a set of limit points Sω+1, and so on. He had examples that went on forever, and so here was a naturally occurring infinite sequence of infinite numbers ω, ω+1, ω+2, ..
So in pursuing this elimination approach he first ran through the natural numbers 0, 1, 2, 3, … but realized that this did not exhaust the possibilities. There was a stage, which he labeled 𝜔, at which all the original isolated points had been removed.
This was a new invention, the first infinite counting number (now called an ordinal)
The ordinal 𝜔 has a good claim to be “infinity”. It’s the limit of the sequence of natural numbers, and in some sense contains them all. (We’re going to use modern notation and conventions, including the convention that each ordinal is the set of all smaller ordinals. Thus 0 is the empty set, 5 (e.g.) is {0,1,2,3,4}, and 𝜔 is {0,1,2, … }.)
Even in Cantor’s day mathematicians were familiar with iterative series, for example, summing an infinite series like 1+1/2+1/4+… which adds up to 2 at stage 𝜔. In fact, Fourier series themselves are infinite series whose limit is reached at stage 𝜔. So they were experienced with “infinity” in this sense and didn’t really need to add 𝜔 as a new object.
The difference, however, with Cantor’s procedure is that it didn’t stop at 𝜔.
Infinity and beyond
If you throw out all the points discarded at finite stages you’re left with a set which (deserves to be) called S𝜔. The trouble is, S𝜔 will in general have newly isolated points, whose neighbors were eliminated at the finite stages. So we need at least another step, whose index is obviously something we should call 𝜔+1.
This hardly ever happens in Computer Science (e.g. we need only 𝜔 steps to close out a context free language under derivation). However it happened to me and my collaborator, P. Rondogiannis. We were working on a minimal model semantics for Prolog with negation as failure and ended up with an iteration that doesn’t finish at 𝜔. More on this in a future post.
It usually doesn’t happen in regular math either, but when it does, the naive idea that 𝜔 is the ultimate infinity breaks down. Cantor recognized this and that’s why he was finally able to solve the representation problem.
So what is 𝜔+1 exactly? The modern convention is that it is the set of previous ordinals, namely {0,1,2,…,𝜔}. It is another infinity!. And not the last. In general S𝜔+1 has isolated points, as do S𝜔+2, S𝜔+3, S𝜔+4, … etc.
But they are not actually bigger infinities. Already Galileo had assumed that two sets have the same ‘number’ of elements iff they can be put in one-to-one correspondence. It is not hard to see that (e.g.) 𝜔+3 (={0,1,2,…,𝜔,𝜔+1,𝜔+2}) can be put in one-to-one correspondence with 𝜔: we match 𝜔 with 0, 𝜔+1 with 1, 𝜔+2 with 2, 0 with 3, 1 with 4, and so on.
A set which can be put in one-to-one correspondence with 𝜔 we call countable. Countable sets are well behaved and are closed under pairing and countable union. In particular the rationals are countable as is the set of all (arbitrarily long) words over a finite (or even countable) alphabet.
So Cantor discovered that he needed a whole sequence of different but countable infinities
𝜔, 𝜔+1, 𝜔+2, 𝜔+3, …
whose limit obviously deserves to be called 𝜔+𝜔 (={0,1,2,…,𝜔,𝜔+1,𝜔+2,…), or better, 𝜔x2.
And, no surprise, S𝜔x2 will in general have isolated points.
Then we get another series
𝜔x2, 𝜔x3, 𝜔x4, 𝜔x5, …
with limit 𝜔x𝜔. (It’s not hard to verify that these are all countable.) This limit is clearly should be expressible as 𝜔2
It’s still possible that S𝜔x𝜔 has isolated points and so we must continue to steps
𝜔3, 𝜔4, 𝜔5, 𝜔6 …
whose limit must be 𝜔𝜔
At this point it becomes clear that this process goes on forever (and way beyond that ability of wordpress to express it). For example, next we should look at three 𝜔s in an exponential ladder but you need latex for that.
The first uncountable
Of course forever doesn’t mean forever any more. All these countable ordinals must have a least upper bound (their union as a set). This union nowadays is called 𝜔1 but I prefer the more old-fashioned Ω.
What about Ω, is it countable? No, because then it’s least upper bound (Ω) would be a member of Ω, impossible. So Ω is an uncountable set – a ‘bigger’ infinity than 𝜔.
That was shocking enough but then Cantor went on to consider the set of real numbers – could they at least be countable?
No, as Cantor found out using the now-famous diagonal argument. We can think of it as a version of Cantor’s proof using binary notation, except we avoid complications involving repeating ‘decimals’.
Eventually he refined it to the point that it can be presented in a paragraph.
The simplest uncountable set is ℘(ω), the set of finite and infinite subsets of ω. Suppose there were a complete enumeration S0, S1, S2, S3,… of ℘(ω). Consider the set R={i in ω: i is not an element of Si}. Simple logic shows that R cannot be any of the Si because R differs with Si on membership of i: because i is in R iff i is not in Si.
This argument generalizes to any set X: X is not equinumerous with ℘(X). Let’s define the cardinality of a set to be the least ordinal equinumerous with it (not obvious that it always exists, but it does). Then the generalized diagonal argument implies the existence of a sequence ℶ0 (=𝜔), ℶ1(= cardinality of ℘(ω)) , ℶ2 (the cardinality of ℘(℘(ω))), … each greater than the previous, with a ℶ for each ordinal. Infinitely many distinct infinities!
Cantor proved that the cardinality of the reals is ℶ1, that of all subsets of the reals is ℶ2. and so on. It turned out that the cardinality of the plane, the cube etc is also ℶ1.
A century of ZFC
Around this time Zermelo and Fraenkel axiomatized Cantor’s vision. Their axioms, along with the axiom of choice, have been basis of modern mathematics for more than a century. No irresolvable paradoxes have emerged in all that time. It’s extremely unlikely that ZFC is inconsistent, vindicating Cantor’s intuitions.
There was one last question that wasn’t settled for decades. The ℵ sequence
ℵ0, ℵ1, ℵ2, …, ℵ𝜔, ℵ𝜔+1, ℵ𝜔+2, … ℵ𝜔x2, …, ℵ𝜔x3, …, ℵ𝜔x𝜔, …, ℵ𝜔x𝜔x𝜔, …
enumerates the cardinals, so that ℵ0 is 𝜔, ℵ1 is the first uncountable ordinal, ℵ2 the second, and so on. The question arises, what is the relationship between the ℵ sequence and the ℶ sequence
ℶ0, ℶ1, ℶ2, …, ℶ𝜔, ℶ𝜔+1, ℶ𝜔+2, … ℶ𝜔x2, …, ℶ𝜔x3, …, ℶ𝜔x𝜔, …, ℶ𝜔x𝜔x𝜔, …
The axiom of choice implies that the cardinals are linearly ordered, which means every ℶ appears in the ℵ sequence. But where?
Cantor was absolutely convinced that the sequences are the same. In particular, he believed that ℶ1, the ‘power if the continuum’, is ℵ1 (i.e. Ω, the first uncountable ordinal).
The idea that ℵ1 = ℶ1 is called the continuum hypothesis (CH). The generalization, that ℵ𝜅 = ℶ𝜅 for all ordinals 𝜅, is the generalized continuum hypothesis (GCH). Cantor throughout his whole career tried to prove GCH or at least CH, without success. He searched for a counterexample; namely an uncountable subset of the reals that does not have the power of the continuum; but never found one. This convinced him that ℵ1 is indeed ℶ1 and he spent decades trying to prove it, also without success. These strenuous efforts took a toll on his health.
Decades after his death mathematicians were able to show that his efforts to prove (or disprove) the “continuum hypothesis” were doomed. In 1940 (!) Gödel proved that the GCH is consistent with the axioms of set theory plus the axiom of choice (ZFC). He did this by showing that GCH is true in the universe of constructible sets, sets that can be defined inductively by first order logic in terms of ordinals.
Finally in 1963, 45 years after Cantor’s death, Paul Cohen produced a model of ZFC in which the hypothesis fails. So it cannot be proved, even with the axiom of choice. In fact it fails badly: for example, it’s consistent, for any finite n, that ℶ1 = ℵn. The general consensus among mathematicians is that CH is ‘false’, namely, shouldn’t be assumed and added as an axiom to ZFC. But there is no consensus as to what ℶ1 should be.
One thing is sure, though. No one will ever be able to produce a counter example, an explicitly defined uncountable set of reals that does not have the power of the continuum. A general rule of thumb is that any set that can be concretely defined will be countable or have the power of the continuum. In other words you can’t exhibit a counterexample to the continuum hypothesis. Does that make it true? Good question!
Are there actual infinities in the real world? A difficult question, but one mathematicians don’t have to answer. There are infinities in our mathematical universe – by design.
Summing up (to infinity)
Well there you have it – it wasn’t so bad. Real world infinities are one thing – if they exist at all – but mathematical ones are harmless. They are our own creations and exist only in our collective imaginations. Being afraid of them makes as much sense as being afraid of Daenerys’ dragons.
That’s not saying we can’t go wrong. It took centuries for mathematicians to work out the rules for dealing with infinities. Summing infinite series is a good example. It’s easy to accept 1/2 + 1/4 + 1/8 + … = 1 but what about 1 – 1 + 1 – 1 + … ?
It took a long time before it dawned on people that the latter doesn’t have a sum. And it took a while to realize that the terms in a series like 1 – 1/2 + 1/3 – 1/4 + … can’t be rearranged at will (not absolutely convergent).
The real danger of using infinity is making a mistake in reasoning. In the best case you get a blatant contradiction like 0=1. But more insidious is the possibility that your get a false result. So using infinity is like using a power saw – effective but dangerous. You might cut yourself and to avoid this you should know the rules. It took a long time to figure our these rules but in the end they’re not that complicated.
One small problem …
In a sense we’ve left the best (or worse) till last. We can think of 𝜔 as an infinitely big number. What about the other direction? Infinitely small quantities, what everyone calls infinitesimals.
An infinitesimal is a number that is greater than 0 but less than 1/n for every natural number n. It is infinitely small but non zero.
Infinitesimals have a long history going back to Archimedes. Leibniz and Newton appealed to them as the basis of the calculus: dy/dx was thought of as the ratio of two infinitesimals. The infinitesimal dx was an infinitesimal change in x and dy the corresponding infinitesimal change in y.
Infinitesimals seemed to give the right answers – usually – for a couple of centuries but mathematician became increasingly uncomfortable with them. In the mid 1800s when they began formalizing the continuum there was no room for them. Instead, Cauchy reformalized calculus on the basis of the epsilon/delta notion of limit. Infinitesimals were uniformly rejected as illogical.
All that changes in the 1960s when Abraham Robinson used the first order compactness property to construct a model of the first order theory of the reals with an infinitesimal. The logician J. Keisler wrote a calculus text using Robinson’s hyperreals but students found the rules too tricky.
Nevertheless Robinson’s work made infinitesimals respectable. One often sees proofs that there are no such quantities. But these refer to the standard reals and the reason there are no infinitesimals there is because we haven’t put them there.
(Incidentally the minimal model semantic of negation in Prolog can be understood in terms of infinitesimal truth values.)
One irony is that Cantor was totally opposed to infinitesimals. He called them an “abomination” and even produced a bogus proof that they couldn’t exist.
So even Cantor had bouts of apeirophobia!
As part of the popshop project I designed and implemented a 
Sloth was part of an insanely ambitious (for 2 or 3 people) project called the popshop (I mentioned it in my 