Bill Wadge's Blog

The fear of infinity is a form of myopia that destroys the possibility of seeing the actual infinite
~ Georg Cantor

Recently NETFLIX released a documentary on mathematical concept of infinity, titled A Trip to Infinity. NETFLIX’s trip is a bad one.

The first twenty minutes or so are reasonable but after that it descends into mysticism, sensationalism, speculation and mathematical nonsense. The average intelligent viewer will be left confused and intimidated and will have a poorer understanding of infinity than they had before watching Trip.

The worst mistake they make is referring to infinity in the singular, as if there is only one infinity. In fact in the first twenty minutes they make it clear that there is more than one, then return to talking about “infinity” instead of “infinities”.

Many infinities

When people talk about “infinity” they think first of the natural numbers and the set {0,1,2,3,…}. But there is also the set of points on the real line between 0 and 1. It’s not obvious but these infinities are not the same.

The study of infinities was initiated by Georg Cantor more than 100 years ago. He was the first to realize that there are many infinities and that they are linearly ordered by size – given two infinities one is at least as big as another.

He had a very simple rule for comparing infinite sets: S1 ≤ S2 (S2 has at least as many elements as S1) if there is a one-to-one comparison between S1 and a subset of S2. In particular, he proved that is S1 ≤ S2 and S2 ≤ S1, there is a one-to-one correspondence between elements of S1 and S2.

For example, if E is the set of even numbers and S the set S of square numbers then E ≤ S because the correspondence 2n ⟷ n² is a one-one correspondence between E and S. The reverse correspondence shows that S≤ E and so S≡E; the ‘number’ of squares is the same as the number of even numbers.

Similar arguments show that S and E have the same number if elements as {0,1,2,3,…} (this set is called 𝜔). In fact any infinite set whose elements can be enumerated has the same number of elements as 𝜔. The number of elements of a set is called its cardinality. The cardinality of 𝜔 is the smallest infinity and is called ℵ₀

Is it the only one? It’s not hard to see that any other infinity must be larger than ℵ₀.

This is where Trip goes off the rails. We need to compare 𝜔 and the set ℛ of real numbers.

The cardinality of ℛ

Cantor proved that the cardinality of ℛ is greater than ℵ₀ with a famous proof that has been modified and adapted many times.

Suppose we could enumerate the elements of ℛ. We could lay out the enumeration in a two dimensional table, like this

1 .3 1 4 1 5 ..
2 .2 7 1 8 2 …
3 .3 3 3 3 3 …
4 .1 4 1 5 9 …
5 .6 9 3 1 4 …
…

Now consider the diagonal number . 37354 … . This number might be somewhere in the list. But let’s take it and change each digit, say by adding 1 mod 10, giving .48465 … . This number can’t be in the list because it differs from the n_^th number in the n^th digit (we have to take care of repeating 9s). So the set of real numbers between 0 and 1 can’t have cardinality ℵ₀.

This is Cantor’s diagonal argument and it shows ℵ₀ < the cardinality of ℛ. There are at least two infinities. The cardinality of ℛ is called ℶ₁.

By this point Trip goes back to talking about “infinity” and the experts are staring at what looks like a billiard ball which its supposedly the universe …. or something.

Meanwhile back in mathland it gets even more interesting. ℵ₀ and ℶ₁ are good for very many sets. The set of pairs of natural numbers and in fact the set of finite sequences of natural numbers has cardinality ℵ₀. Thus there are only ℵ₀ many polynomials with integer coefficients.

The same is true of the set Q of rational numbers and the set of finite sequences of rational numbers. That means only ℵ₀ many polynomials with rational coefficients

Similar results hold for ℛ. There are ℶ₁ polynomials with real coefficients.

The cardinals ℶ₂, ℶ₃, ℶ₄, ,…

But now consider drawings on the plane. If every pair of rationals is a pixel which can be black or white, there are ℶ₁ possible images. And if every pair of reals is a pixel, there are more than ℶ₁ possible images.

How many more? Cantor’s diagonal argument can be generalized to show that the set of subsets of a set has a bigger cardinality than that of the set. If the set has cardinality 𝜅 then the powerset ℘(S) (the set of all subsets of S) has cardinality 2^𝞳, which is bigger than 𝜅.

An image on the plane is a subset of ℛxℛ and the set of such images has cardinality 2^ℶ₁. So now there are three infinities. (2^ℶ₁ is called ℶ₂)

We can continue taking power sets and generate a sequence ℶ₁, 2^ℶ₁ (=ℶ₂), 2^ℶ₂(=ℶ₃), … of bigger cardinalities. So there are at least ℵ₀ many infinities.

Nothing of this, which is mind boggling, is described in Trip. Instead they’re speculating about an orange in a box … which supposedly disintegrates then reassembles itself.

The continuum hypothesis

Back to the math, which really gets interesting. When Cantor discovered the power-of-two series ℶ he naturally started wondering if they were all the cardinalities. In particular, he wondered if there is a set of reals whose cardinality is greater than ℵ₀ but less than ℶ₁. (Incidentally ℶ₁ = 2^ℵ₀).

He tried for many years to settle the question but never succeeded, neither finding such a set nor proving that none exists. He was forced to leave what he called the “continuum hypothesis” (CH) unresolved.

It wasn’t till 1938 that any progress was made. The famous logician Kurt Gödel proved that it’s not possible to refute the continuum hypothesis. So it’s either true or else …

… the or else was demonstrated in 1963 by Paul Cohen. He showed that it is not possible to prove the continuum hypothesis either. In other words, CH is independent of the usual axioms of set theory (which are taken to be the axioms of modern math).

A lot of progress was made after Cohen’s proof but nothing decisive. It turns out that the axioms of math have little to say about the cardinalities between ℵ₀ (=ℶ₀) and ℶ₁. There could be a couple or ℵ₀ many or more.

This is interesting, even mind boggling, but none of it shows up in Trip. At this point they’re speculating that eventually the heat death of the universe will kill off humanity.

Constructibility

Since Cantor, mathematicians have been searching for a plausible extra axiom that will settle the continuum hypothesis. There is no consensus.

In my opinion, however, there is one obvious candidate, namely the axiom of constructibility.

This axiom, sometimes written “V=L”, says that every set is “constructible”. Roughly speaking, the constructible sets are those that are definable in terms of simpler constructible sets, and aren’t just introduced arbitrarily at random.

Gödel introduced the constructible sets to prove his partial independence results. V=L implies the general continuum hypothesis (ℵ_𝛂 = ℶ_𝛂 for all 𝛂) and the axiom of choice plus a whole lot of other results.

My championing of V=L is probably due to my computer science background, where we encounter many recursive definitions. As a general rule we take the meaning of a recursive definition X = f(X) to be the least fixed point of the equation. And we calculate the least fixed point by starting with nothing (∅) and iterating ∅,f(∅),f(f(∅)),f(f(f(∅))),… then taking the limit.

The ordinary axioms of math imply that any family F of sets is closed under definitions; so the family V of all sets satisfies the recursive definition V = ∅ ∪ 𝒟(V), where 𝒟(X) = sets definable from X. If we apply the iterative/cumulative procedure described above, we get L, the family of constructible sets.

I’m sure that this is the ‘right’ thing to do and that the axiom of constructibility should be considered as ‘true’.

Beware of Pop Science

So Trip to Infinity is bad news. Unfortunately it’s not alone. Trip veered into physics and almost every pop explanation of physics is just as bad.

Speculation, sensationalism, paradoxes, misinformation. Blackholes, wormholes, time travel and the like.

One frequently repeated example of false facts is the claim that bodies are collections of atoms with nothing in between. In reality the space between atoms is filled with fields: electromagnetic, gravitational, who knows what else. Every physicist knows this, but only too many are willing to go before the public and declare otherwise.

This rotten pop science is basically a plot to make people feel stupid. They’re intimidated because what they see doesn’t make sense and they conclude they’re not smart enough for science.

A good example in Trip comes when they discuss cardinal arithmetic (cardinals can be added, multiplied etc like integers). They show the equation ∞ + 1 = ∞, which is true if ∞ is an infinite cardinal,
then proceed to subtract ∞ from both sides, giving 0=1, a howling contradiction. And that’s where they leave it.

What is the viewer supposed to make of this? That infinity is a contradiction?

In fact, all it means is that not all the rules of finite arithmetic apply to cardinal arithmetic. No big deal. There’s nothing wrong with your brain and 0 is not equal to 1.

Pop science has tried to scramble your brains.

Art is what you can get away with.
– Marshall McLuhan

[All the images in this post were produced with generative AI – Midjourney,DALL-E 2, Stable diffusion.]

I’d like to give you my thoughts on the recent amazing developments in AI (Artificial Intelligence).

I’m a retired (emeritus) professor of computer science at the University of Victoria, Canada. I ought to know a bit about AI because I taught the Department’s introduction to AI course many times. 

All I can say is thank God I’m retired. I couldn’t have kept up with the breakthroughs in translation, game playing, and especially generative AI.

When I taught AI, it was mainly Good Old Fashioned AI (GOFAI). GOFAI is largely searching of trees and graphs. I retired in 2015, just before the death of GOFAI. I dodged a bullet.

I am in awe of NFAI (New-Fangled AI) yet I still don’t completely understand how it works. But I do understand GOFAI and I’d like to share my awe of NFAI and my understanding of why GOFAI is not awesome.

Continue reading →

Everyone’s all, “Wow, chatGPT, amazing, a real milestone, everything will change from now on”. And they’re right – but probably don’t realize that this is not the first time something like this has happened. In fact there’s been wave after wave of computing technological innovation ever since the industry got started in the 1950’s. Here are some of the waves I’ve experienced personally

The Stone Age of computing.

When I got into computing, in 1965 at UBC in Vancouver, it was all very primitive. I took a numerical analysis course while doing a math degree.

I learned Fortran and later, that summer, IBM 7040 assembler, which I got pretty good at. However when I moved on to Berkeley to do a math Phd I almost completely dropped computing because I thought it was primitive – punched cards and Fortran – and not really going anywhere. But I kept my hand in.

LISP

While I was at Berkeley I was introduced to LISP and again my mind was boggled. I was very taken by recursively defined algorithms working on hierarchical structures. FORTRAN didn’t support recursion nor did it have hierarchical data structures.

Given that FORTRAN was my first language these omissions could have scarred me for life but instead I really took to LISP. In retrospect LISP was a major milestone because it took recursion into the mainstream.

However the first LISP systems were pretty sluggish and I mistakenly dismissed LISP as being impractical. I continued my math research into what would be known as Wadge degrees.

I was wise to pursue my interest in computing because by the time I finished my PhD the math job market had collapsed. My first teaching position was in computer science, at the University of Waterloo. In those days there weren’t enough CSC PhDs to staff a department so they hired mathematicians, physicists, engineers etc.

Time Sharing

Between my time at UBC and my arrival at Waterloo there was one big milestone – time sharing. Dozens of people could share connections to mainframes, which had gotten bigger and more powerful. This was mind-boggling, because before you had to wait your turn for computer access. At UBC I punched my program on to cards and left the deck at reception. I’d come back one or two hours later (the “turnaround time”) when the programs in the “batch” had been run and get the output. Which would typically contain an error report.

It took forever to produce a correct program. Time sharing cut turnaround time to seconds and greatly speeded up the software development process. Thus was born “interactive” computing.

Time sharing needed a lot of supporting technology. An operating system with files. Terminals for users, running some form of file browser, compilers and file editors.

UNIX

All this technology quickly arrived with the UNIX operating system, a non-official project at Bell Labs developed on an abandoned computer. UNIX conquered the world and still dominates to this day.

When UNIX arrived in a department it was like Christmas because there was a whole tape full of goodies. You got the C language and its compiler, the vi screen editor, and utilities like yacc, awk, sed, and grep. UNIX was a huge leap forward and an unforgettable milestone.

Soon there was a whole ecosystem of software written in C by UNIX users. Unix was a real game changer.

Terminals

One of the UNIX utilities was the shell (sh), a simple CLI. It was easy to set up a terminal, like a vt00, to run the shell. The shell allowed the user to define their own shell commands, and allowed recursive definitions. An irreplaceable command was vi, the screen editor. It replaced line editors, which were very difficult to use.

The end result was that anyone with a UNIX terminal had at their disposal the equivalent of their own powerful computer. At first the terminals were put in terminal rooms but gradually they were moved into individual offices.

Digital typesetting

About the time UNIX showed up, departments started receiving laser printers that could print any image. In particular they could print beautifully typeset documents, including ones with mathematical formulas. The only question was, how to author them?

UNIX had the answer, a utility called (eventually) troff. To author a document you created a file with a mixture of your text and what we now call markup. You ran the file through troff and sent the output to the printer.

The only drawback was that you had to print the document to see it – a vt100 could only display characters. This problem was solved by the next milestone, namely the individual (personal) computer.

Workstations

A personal computer (often called a “workstation”) was a stand-alone computer designed to be used by one individual at a time – a step back from timesharing. The workstations were still networked and usually ran their own UNIX. the crucial point is that they had a graphics screen and could display documents with graphs, mathematics, and even photographs and other images.

As workstations became more common, timesharing decreased in importance till only communication between stations was left.

EMAIL

Originally communication was by file transfer but this was quickly replaced by email as we know it. At first senders had to provide a step-by-step path to the receiver but then the modern system of email addresses was introduced.

At this point many computer people relaxed, thinking we’re finally reached a point where there are few opportunities for innovating – boy were they wrong!

The Web

At CERN in Switzerland Tim Berners-Lee decided that email lists were inefficient for distributing abstracts and drafts of physics papers. He devised a system whereby each department could mount a sort of bulletin board. This was the origin of the Web.

Unfortunately at first no one used it, until Berners-Lee put the CERN phone directory on the Web and its popularity took off. Soon there were thousands of web sites opening every day.

If anything the Web was a more significant milestone than even UNIX or timesharing. I remember playing around and discovering Les Tres Riches Heures du Duc de Berry – medieval images in glorious color on the Web (via a Sun workstation). My mind was, of course, boggled, and obviously not for the first time.

Minor milestones

After Timesharing, UNIX and the Web there are other important milestones that seem almost minor by comparison. There’s Microsoft’s Office suite including the spreadsheet Excel. Then there’s the iPhone and other smart phones, People with a phone carry around a computer thousands of times more powerful than the old 7040 I learned computing on.

And yet the innovation doesn’t stop. For a long time AI was a bit of a joke amongst computer scientists-we called it “natural stupidity”. The translations were of poor quality and although they mastered Chess a more complex game like Go (Baduk) was beyond their reach. Periodically industries and granting agencies would get discouraged and an “AI winter” would set in.

AI Summer

Then a very few years ago this changed dramatically. Go was solved and the translations became almost perfect (at least between European languages). What I call the “AI Summer” had arrived.

This was all thanks to employing new strategies (ML, neural nets) and using the vast stores of data on the internet.

And now we have Midjourney etc and chatGPT. Very significant milestones but not, as we have seen, the first – or the most significant.

Everyone’s heard about chatGPT, the latest and most sophisticated chatbot to date.We all know it can bs proficiently about ‘soft’ topics like English literature. I decided to quiz it about a hard topic, mathematics. As you probably know, I have a PhD in math, so I won’t go easy.

Continue reading →

The axiom of choice (AC) seems harmless enough. It says that given a family of non empty sets, there is a choice function that assigns to each set an element of that set.

AC is practically indispensable for doing modern mathematics. It is an existential axiom that implies the existence of all kinds of objects. But it gives no guidance on how to find examples of these objects. So in what sense do they exist?

Continue reading →

Power concedes nothing without a demand.
-Frederick Douglass

When the late Ed Ashcroft and I invented Lucid, we had no idea what we were getting in for.

Continue reading →

When Ed Ashcroft and I invented Lucid, we intended it be a general purpose language like Pascal (very popular at the time.)

Pascal had while loops and we managed to do iteration with equations. However in Pascal you can nest while loops and have iterations that run their course while enclosing loops are frozen. This was a problem for us.

Continue reading →

Recently there was a post on the HN front page pointing to a GitHub repository containing an old (2019) version of the source for PyLucid (I don’t know who posted it). It generated a lot of interest in Lucid but unfortunately the 2019 version is crude and out of date and probably put people off.

I’m going to set things right by releasing an up to date version of PyLucid (Python-based Lucid) and up to date instructions on how to use it to run PyLucid programs. The source can be found at pyflang.com and this blog post is the instructions. (The source also has a brief README text file.)

Continue reading →

I recently graduated my 17^th and last PhD student, Monem Shennat. This is the abstract of his dissertation with my annotations (the abstract of a University of Victoria dissertation is limited to 500 words).

The problem he tackled was that of dimensional analysis of multidimensional Lucid programs. This means determining, for each variable in the program, the set of relevant dimensions, those whose coordinates are necessary for evaluating individual components.

Objective: to design Dimensional Analysis (DA) algorithms for the multidimensional dialect PyLucid of Lucid, the equational dataflow language. 

Continue reading →

I have some theories about these modes – for example, cropping one into the other. I tried them out on the Monna Lisa and … read on!

Continue reading →