Bill Wadge's Blog

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?

A voting scheme

Don’t buy a single vote more than necessary.
– Douglas William Jerrold

Voting is in the news today as are various voting schemes. However when it comes to voting a proposal up or down, there’s only one simple criterion: majority rule. If the voters are v0, v1, v2, … vn-1 then the proposal is accepted if at least n/2+1 are in favour.

But what if there are infinitely many voters v0, v1, v2, … ? What does it mean for there to be a majority in favour? AC implies that there exists an infinitary voting scheme (this is not obvious) but supplies not a hint about how it could work.

One possibility is to pass the proposal if infinitely many voters voted Aye, but it’s possible that at the same time infinitely many voted Nay.

A vote is an infinite sequence (e..g.) Aye, Nay, Nay, Aye,… and a voting scheme is a function which assigns either Aye or Nay to each voter. A majority is a set of voters such that any motion for which they all vote Aye, passes.

Then we require the following properties to hold:

Given any set of voters, either it or its complement is a majority, but not both
If everyone switches their vote, the result switches
The result of adding any number of voters to a majority is a majority
The result of removing a single voter from a majority is still a majority.
The intersection of two majorities is a majority

There are a number of consequences of these properties we can immediately derive. Let’s call the complement of a majority a minority.

A motion passes iff the set of those who voted Aye is a majority and fails if it is a minority
The set of all voters is a majority and the empty set is a minority
Any finite set is a minority
Any cofinite set is a majority
If the vote is unanimous, the result follows the vote
The union of two minorities is a minority

Sounds simple? Well don’t try to invent a particular voting scheme because you won’t succeed. Any scheme that can be defined concretely will fail at least one of these properties. In fact it’s been shown that it’s consistent with the axioms of set theory and a weak form of the axiom of choice that there is no voting scheme.

Here is a simple argument against the existence of a voting scheme. Let E be the even numbers and O the odds. Either E or O is a majority, say E. But how is O smaller than E?They are isomorphic, if the evens and odds swap votes, we get the same partition but now the former majority voters are in the minority. How?

Nevertheless full AC says a voting scheme exists. The question is, exists in what sense?

Non measurable set

You’ve probably heard of the Banach-Tarski result. AC implies that it is possible to divide a unit sphere into five pieces then reassemble them into two unit spheres (using only translations and rotations, that should preserve volume). This is like proving that 1=1+1 except that four of the pieces can’t be assigned volumes: they are non measurable sets.

AC implies the existence of non measurable sets – e.g. solids that don’t have a volume – but don’t ask to see an example of one. Any set you can describe precisely will be measurable – for example, any Borel set. Analysis texts devote a lot of space to proving that the results of various operations, like countable union, preserve measurability.

These texts could be greatly simplified if they just assumed that all sets are measurable. Of course if they also assumed AC they’d be in trouble but you can do most of analysis with weaker forms of choice, like countable choice, that don’t imply the existence of non measurable sets.

An indeterminate game

You’re all familiar with finite discrete games like checkers and chess. Simplifying a bit, they have the following properties:

Players I and II alternate, I moving first, until the game ends
On each move the mover has a finite choice of moves
On each move the mover plays a natural number
Each player knows the sequence of moves up to the current position
If the last move produces a winning position, the mover wins
If the last move produces a losing position, the mover loses
If the last move produces neither, the game ties

It’s actually quite tricky to make this precise, and I’ll skip the details. The crucial concept is that of a strategy, which is simply a function which given the moves so far, gives the next move for the player concerned. A winning strategy is one that always eventually puts its user in a winning position.

Zermelo showed more than a century ago that if a game always ends, then either one player has a winning strategy, or both have a tying strategy.

But we can also define infinite games. In fact it’s simpler. Given any subset G of the Baire space (set of sequences of natural numbers):

Players I and II alternate, I moving first.
On each move each player plays a natural number
If the resulting infinite sequence a0,b0,a1,b1,a2,b2, … is in G, II wins, otherwise I wins.

A winning strategy for II is a function which takes a0,b0,…an and yields bn. A strategy for I takes a0,b0,…an,bn and yields an+1.

Since there are no ties we might expect that one of the players has a winning strategy (in which case the game is said to be determinate). Not so fast.

AC implies the existence of a nondeterminate game. An example? Don’t look for one, for the usual reasons. Any game you can define will be determinate. In particular, if G is a Borel set, then G is determinate.

There are a number of weaker versions of AC that can be proved directly in ZF. Suppose, for example, that each choice set has exactly two reals. Then choose the smallest! More generally the same idea works if each choice set has a finite set of reals.

A well ordering of the reals

But what if a choice set has an infinite number of reals? Say, all those greater than 0? There is no smallest.

However we could use another ordering of the reals, in which any subset has a least element. This is called a well-ordering. Then any family of sets of reals would have a choice function.

The natural numbers are well ordered (by arithmetic ordering), so every family of nonempty sets of natural numbers has a choice function,

Is there a well-ordering of the reals? AC implies there is, but don’t try to find an example. No ordering you can define will be a well-ordering, otherwise you could prove AC from ZF, which has been shown to be impossible (if ZF is consistent so is ZF+¬AC)

Yet another mathematical object that does not exist in any practical sense.

An infinitesimal

One important application of AC is to prove the compactness property of first order logic. This says that if every finite subset of a set of first order formulas is consistent (has an interpretation), the whole set has an interpretation (this is nontrivial because different finite subsets my have different interpretations).

One application is to prove the possible existence of infinitesimals. An infinitesimal is a number that is greater than 0 but less than 1/n for every natural number n.

For a long time calculus was based on infinitesimals. The derivative f’ of a function f was ‘defined’ as (f(x+𝛆)-f(x))/𝛆. Engineers still think in terms of infinitesimals dx and dy.

In the 1800s infinitesimals were declared inconsistent and abolished, replaced by the 𝛆-𝛅 formalism.

However in the 1960s Abraham Robinson pointed out that compactness implies the existent of an extension of the reals with infinitesimals. If we take all true first order properties of the reals (such as x+y=y+x or log(xy) = log(x) + log(y) and add the formulas

𝛆<1
𝛆<1/2
𝛆<1/3
𝛆<1/4
…

Then every finite subset is consistent. Hence, by compactness, the whole set is consistent. Robinson called the resulting structure the hyperreals and it’s a model of the first order theory of the reals, with infinitesimals.

The only snag is, what is 𝛆, the infinitesimal whose existence is guaranteed by compactness? Don’t ask, because there is no hope of defining it. If 𝛆 works so does 𝛆/2, or 𝛆**2, or √𝛆. There is no infinitesimal distinguished in the same sense that i and -i are distinguished in the complex numbers. So the hyperreals have infinitesimals but don’t try to choose a particular one.

Degrees of Existence

One thing is clear, existence is not a straight forward binary property. It’s a spectrum. On one end there’s the existence of integers like 42 and recursively defined functions like factorial. On the other end is the voting scheme, which seems like pure vapourware.

AC by itself implies only vapourware. However these zombie-like objects like the voting scheme are necessary for the smooth functioning of the mathematical universe. Without them the universe is chaotically irregular.

The universe with AC is like an all-conquering army with straight ranks but ranks filled in part with zombies. Their presence fills us with discomfort but without them we’re lost.

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. Most by Paul DelSignore, not by me}

I used to teach the AI course at the University of Victoria – 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). 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 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 awe-full.

Seek and Ye Shall Find

For a long timeAI was almost a joke amongst non-AI computer scientists. There was so much hype but the hyped potential breakthroughs never materialized. One common quip was that AI was actually natural stupidity.

Many departments, like my own, basically boycotted the subject, maybe only offering a single introductory course

The heart of GOFAI is searching – of trees and, more generally, graphs. For many decades the benchmark for tree searching was chess. Generations (literally) of AI researchers followed the program first proposed by Norbert Wiener in the 40s, based on searching the chess game tree. Every ten years AI evangelists would promise that computer chess mastery was only ten years away

Wiener’s idea, described in his pioneering book Cybernetics, was a min/max search of the game tree, resorting to a heuristic to evaluate positions when the search got too deep.

The chess game tree gets big very quickly and it wasn’t until decades later (the late 1990’s) that IBM marshalled the horsepower to realize Wiener’s dream. They built a special purpose machine, Deep Blue, capable of examining 100 million positions per second. Deep Blue eventually won, first a game, then a whole match, against Gary Kasparov, the world champion.

Deep Blue was the high water mark of GOFAI and there was no real followup. Deep Blue’s successor, Watson, could win at mastermind but commercial applications never materialized.

AlphaGo and AlphaZero

I was impressed by Deep Blue but wondered about the game of Go (Baduk, Wei-chi). The board is 19×19 and the game tree is incomparably bigger than that of chess. If you’d asked me at the time I would have said Go mastery was inconceivable (which, if we had to use GOFAI, was true).

Then in 2016 the unthinkable occurred: a program, called “AlphaGo”, started beating Go champions. It did not use Wiener’s approach; instead it used Machine Learning (ML) (don’t ask me how that works).

AlphaGo trained by playing millions of games against itself. Originally it was given hundreds of thousands of expert level human games but its successor AlphaZero dispensed with them and simply taught itself. It took only a few hours to reach expert level, which for humans took hundreds of years. Variants of the software mastered chess, checkers, and shogi in a similar fashion.

Google Translate

About the same time users of Google Translate noticed a sudden dramatic increase in the quality of its translations, although Google at the time said nothing. In fact Google had switched from statistical to neural networks (don’t ask).

Currently Google’s translations are spectacularly good (and Deepl’s even better). In translating into French, for example, it usually gets the pronouns right as well a well as the gender/number agreements. If you want perfect output you still have to at least proofread the output because occasionally there are mistakes, usually minor.

Here is a translation from today’s Le Monde. It’s perfect.

Since the beginning of the conflict, Russia has refused to describe its invasion of Ukraine as a war, calling it a “special military operation”. Shortly after the conflict broke out, the authorities banned the Russian media from using any information other than official statements on the subject and banned the use of words such as “war” and “invasion”, under penalty of being punished by the law.

GOFAI never produced really good translations, relying as it did on facts and rules. I remember the whole class getting a good laugh out of the mistakes. Once, translating a news article about Iraq from German, it claimed Saddam “warned the US before an attack” when what it should have said was “Saddam warned the US of an attack”. Modern systems would never make such a basic mistake.

Generative Speech

Then comes GPT 3 and the other systems that generate speech. Originally they were merely predictors that would complete incomplete sentences. But now they run on and produce whole articles. Which (usually) make sense. Here’s an example:

Author Prompt: Write me an article about creativity please 

GPT-3 Response: I’ll be honest. I don’t know much about creativity. I’m not a psychologist and I’m not a creative myself. I’m just a guy who likes to read about psychology and creativity. What I can do, though, is write you an article about creativity that’s based on what I have read. That way you get a proper article, but you don’t have to pay for the expertise of a psychologist or a creative person.

GOFAI never achieved anything along these lines. But then my mind was well and truly boggled by …

Generative Art

Along came DALL-E and DALL-E 2. But it wasn’t till Stable Diffusion was released that I started paying attention. Of course there was the pictures of astronauts on horseback and cats wearing sunglasses. But what really impressed me was pictures in the style of well known artists. Here are two of my favourites :

The first is an abstract image in the style of Picasso. I can’t find the original but MidJourney’s version is just marvellous. I’d have no hesitation to print it, frame it, and hang it on my wall.

My second favourite is a wonderful portrait of Superman – ‘by’ Rembrandt! As one observer commented, “those eyes have seen some shit!”

But even the cheesy astronaut image is impressive.

The striking fact is that you can’t see the astronaut’s left leg. The image generator seems to understand that you can’t see through opaque objects (namely, the horse).

GOFAI would need literally hundreds of rules just about what to do when bodies overlap, what to show, what objects are transparent and to what degree etc etc.

On reflection

OK let’s go all in – let’s look at a cat wearing sunglasses. Ew cheesy – but there’s something remarkable about the image.

It’s the reflections in the lenses of the sunglasses. Not only are they visible, but the reflections are, correctly, the same. How does Midjourney coordinate the images in separate parts of the picture?

A closer look

When I see this image I have to ask, where did all this come from? Midjourney is trained on 5 billion images but condenses this training to 5 GB. So there’s not enough room to include exact copies of images found in the training set. We can assume that this (apparent) photo does not exist as is on the internet.

In particular what about the blue feathers on either side of the subject’s neck (they are not mirror images). Where did they come from? Did one of the training images have them?

The mystery is that this image is the result of combining training set images, but how are they put together? The best GOFAI could do is chop up the training images and put them together like a badly fitting crossword puzzle with visible seams and limited symmetry. I’m baffled.

The social implications of AI technology

It is questionable if all the mechanical inventions yet made have lightened the day’s toil of any human being.

~ John Stuart Mill

There is a lot of controversy Midjourney and other generative image programs.

The first question is, are these images art? I think some of the images presented here are definitely art, even good art. If you’re not convinced, have another ‘Rembrandt’.

The second question is, is imitating the style of certain artists fair? I don’t know, but there seems no way to stop it. Currently nothing stops a human artist from studying living artists and imitating their styles. Midjourney etc are just especially good at this.

In a sense, this imitation broadens the exposure of the imitated artists. Now everyone can have, say, a Monet of their own.

Finally, a vital question is, how will this affect today’s working artists? Here the answer is not so optimistic.

Generative AI is not the first disruptive technology. There’s photography, the closest analog, digital art in general, the telephone, the automobile, the record player, the printing press, and so on.

Each of these had the effect of obsoleting the skills of whole professions. It didn’t wipe them out, but the vast increase in productivity put large numbers out of work. And those that remained had to acquire and use the new tools. Because of economic competition they had to work harder than ever to keep up.

Labor saving technology inevitably becomes profit saving technology. The tractor is an example. Initially it (and farm machinery in general) were marketed as labor saving. But eventually competition forced every farmer to get machinery or sell out (which most had to do). The result was the same or more food produced by a fraction of the former number of farmers, working their butts off.

So I predict AI will shrink the number of artists and force them to use Midjourney etc. For art consumers, it will be good news – like drinking from a firehose. A new individual Monet every week. Do it yourself illustrations for personal blogs. But not change in society as a whole.

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 →

Recently my PhD student gave a rehearsal of their 20 minute oral presentation. It was ok. Average.

In other words, (seemingly) long, and boring. Like so many people’s technical talks. What can you do?

What you can do is follow these simple rules I’m going to give. They’re not all my own, you can find most elsewhere. The problem is, most people think they’re impractical and don’t follow them. Result? Bo-ring!

Continue reading →

Two cheers for the World Wide Web
— Ted Nelson

Ted Nelson invented hypertext but not the web. He thinks it hasn’t fulfilled its real potential, and I agree.

One of his good ideas that the web doesn’t really support is stretchtext – text that expands or contracts in response to the reader’s (dis)interest.

Continue reading →

As I’ve said before, PyFL is functional programming for the rest of us. (It’s available at pyflang.com.)

PyFL now has type checking – without type declarations. Instead the type is produced by evaluating the program over the domain of types.

Continue reading →