Introduction to Infinity/ies

To infinity and beyond!
—- Buzz Lightyear (Toy Story)

Cantor invents the ordinals

This illustrates the ordinal ωxω

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 SS1S2S3,… 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.

(from Wikipedia)

The simplest uncountable set is ℘(ω), the set of finite and infinite subsets of ω. Suppose there were a complete enumeration S0S1S2S3,… 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!

Posted in Uncategorized | Leave a comment

Intensional Logic in Context – from philosophy to technology

The most pervasive fallacy of philosophic thinking goes back to neglect of context.

Jon Dewey

What exactly is “intensional programming?” The easy answer is, programming in a language based on intensional logic. But that raises another, more important question, namely what is intensional logic? Logicians have been working on the answer for more than 2500 years.

The short answer is, logic in which the truth-value and more generally the meaning of an expression depends on an implicit context. Let me attempt to give you the full answer.

Continue reading

Posted in Uncategorized | Leave a comment

Just Funnin’ – the infamous “Cowboys” section of the Lucid book

[This is the infamous section of the book Lucid the Dataflow Programming Language where I make fun of everyone working on imperative languages. It was very popular but many people hated it even though no individual is named. In a companion post I cite it as an example of a Career Limiting Move. It didn’t quite kill my career though it didn’t help. I’m sure there were a number of meetings I wasn’t invited to and program committees I was left out of because of it. Hmmm … was that really a bad thing?]

Continue reading

Posted in Uncategorized | 5 Comments

Plotting Propositions – the Mathematics of Persuasion

Sha la la la la la la
La la la
La di da
La di da

Van Morrison (Brown Eyed Girl)

A lot of people have to write as part of their jobs – grant proposals, progress reports, specifications. And there are endless verbal communications – defending code, disputes over features, justifying organization changes, technology explanations, and so on forever.

Well, the good news is that Hollywood can help!

Continue reading

Posted in Uncategorized | 2 Comments

Wadge Degrees – the origin story

I’m fortunate enough to have a mathematical concept named after me. And not just Wadge degrees. There’s also the Wadge hierarchy, Wadge reducibility, and the Wadge game. In fact I’ve seen people say they’re interested in “Wadge theory”. A whole theory!

I’ve posted about this before but that was mainly technical and for most readers not all that accessible. It left out the human element, the passion, the drama, the thrill of victory etc. So here’s the real story.

Continue reading
Posted in Uncategorized | 1 Comment

I/O Without Side Effects – the Lucid experience

Everything you know is wrong.
— Firesign Theater

Everybody knows that output requires side effects.

The logic is irrefutable. When an output occurs, something changes. There is a number on the terminal screen, there is a sheet of printed paper in the printer output tray. Surely the source program, even in a functional language, must contain a command, like print(N), which can’t be understood as a pure data-to-data function.

Everybody is  wrong. Wrongity wrong wrong wrong.

Well, maybe not that wrong. But the experience of Lucid shows that nontrivial I/O  does not necessarily require side effects. Instead, we can have programs that output (pure) data which we send to an output device. This is how Lucid (e.g. pyLucid) works. Not an IO monad in sight.

Continue reading

Posted in Uncategorized | Leave a comment

Lucid – the origin story

I’ve already written about the origins of Lucid but that was a dry, technical, and incomplete post. Here is the real story, with all the drama and passion, the thrill of victory, the agony of defeat.

Well maybe not quite. But with the human element.

Continue reading

Posted in Uncategorized | 3 Comments

Monads and Intensionality – Lucid is not an aberration

Be ahead of your time, but only a little.
– Mason Cooley

Do you understand  monads? I don’t, so I  thought I’d explain them to you.

Then, once you’ve got it, I’ll re-explain Lucid. No Haskell, optional category theory, gluten free.

Continue reading

Posted in Uncategorized | 2 Comments

Popcode, a FORTH-like language with looping

iu-2As part of the popshop project I designed and implemented a  concatenative (FORTH-like) language I called Popcode. It has lists (of commands), which among other things makes loops possible. The first concatenative language was Forth and nowadays the best known is probably Joy. They don’t have looping constructs, only recursion.

Continue reading

Posted in Uncategorized | 1 Comment

The Sin of Sloth – an external module system for C

A while back John Plaice and I invented an external module system for C . It worked pretty well for us but never caught on. Maybe it will be of some use to some of you.

iu-1Sloth was part of an insanely ambitious (for 2 or 3 people) project called the  popshop (I mentioned it in my software success post).

It all started harmlessly enough – why don’t I write a Lucid interpreter?

Continue reading

Posted in Uncategorized | 1 Comment