*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 S_{0} 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

S_{1}as its set of zeros, whereS_{1}is the set of limit points ofS. IfS_{k+1}is the set of limit points ofS_{k}, then he could construct a trigonometric series whose zeros areS_{k+1}. Because the setsS_{k}were closed, they contained their limit points, and the intersection of the infinite decreasing sequence of setsS,S_{1},S_{2},S_{3},… formed a limit set, which we would now callS_{ω}, and then he noticed thatS_{ω}would also have to have a set of limit pointsS_{ω+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 *S*_{0}, *S*_{1}, *S*_{2}, *S*_{3},… of ℘(*ω*). Consider the set R={i in *ω*: i is not an element of S_{i}}. Simple logic shows that R cannot be any of the S_{i} because R differs with S_{i} on membership of i: because i is in R iff i is not in S_{i}.

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!