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.

I arrived in Berkeley (California) fresh from getting a math degree at UBC in Vancouver. I arrived a long time ago, in the Fall of 1966 (!). There was a lot going on on campus – roll on from the previous year’s “Free Speech” movement. And the Vietnam war was raging. Soon after I arrived the Marines set up a recruiting table in the student union building. Hundreds of protesters chased them and the police out of the building and across Sproul Plaza into Sproul Hall, the administration building. That was quite a sight, the first of many. But I’ll talk about that another time.

Anyway, when I arrived I had to choose a couple of grad courses but had no idea what I wanted to study. I sort of liked topology but not with a passion.

I Love Logic

One day I was lunching with the Canadian contingent and they told me about a course they’d looked into – logic, with a professor Addison. They said it seemed pretty interesting and Addison had a great reputation as a teacher.

Only one hitch, it was a second year course with a first year logic course as prerequisite. I never studied any logic at UBC so I had to get special permission from Addison. I went to see him.

He asked if I was the best math student in my year at UBC. I said I was the top Science grad and that seemed to satisfy him. I was in.

The course was a revelation, and I decided I loved logic. There were obviously holes in my background, which I quickly filled in. For example, about three weeks into the course it dawned on me that every first order formula that is true (in all interpretations) is provable!

Typically a first year course is heavy on proof theory and devoted to proving this (the completeness theorem). I’m glad I skipped this and proof theory in general. Maybe this is why I’ve always preferred model theory and semantics.

Addison was the best lecturer I ever experienced. I had a great time and learned a whole lot of logic. Next year I signed up for Addison’s seminar on definability.

Logic PLUS topology!

I learned a lot in the seminar that would serve me well later in my career. In particular I learned of the ‘algorithmic’ approach to the Baire topology on the Baire space.

The Baire space is the set of infinite sequences of natural numbers together with the Baire topology, in which two sequences are close if they have a long common initial segment. The longer, the closer. The Baire space is isomorphic to the irrationals with the usual topology but the representation in terms of infinite sequences (derived from continued fractions) is easier to work with.

Addison presented a fascinating characterization of Baire continuity. Basically, a function is Baire continuous if it can be computed incrementally, continuously consuming finite amounts of the input and producing finite amounts of the output. In other words, in modern terminology, it’s a dataflow filter (in, e.g., the UNIX sense). Little did I realize how important this concept would be in my later research.

I’m certain this characterization was original with Addison but he doesn’t seem to have claimed proper credit for it.

He also told us about infinite games, which he thought (correctly) would be important. And he told us about the axiom of determinateness, which says the in any infinite game one of the players has a winning strategy. Yes, it is possible (and a consequence of the axiom of choice) that every strategy for one player is defeated by a strategy for the other – and vice versa!

Keldysh’ sets

As part of the seminar we got problems to work on. Mine was to find a simpler approach to a result of the Russian mathematician Lyudmila Keldysh. She had shown that a particular series of four subsets of the Baire space was of strictly increasing complexity. The subsets were simple but her proofs were diabolical. Could I do better?

– The first set was the collection of sequences in which 0 appears at least once at some point.

– The second was the collection of sequences in which 0 appears infinitely often.

– The third was the collection of sequences in which some number appears infinitely often.

– The fourth, the collection of sequences in which infinitely many numbers appear infinitely often.

It was frustratingly obvious that these sets are increasingly complex. But how to prove it?

The first step was relatively easy. The first collection is, in topological terms, open. In the Baire topology, that means if a sequence is in the collection, then it has an initial segment all of whose extensions are in the collection. In other words, if a sequence is in the collection, there is a finite amount of information about the sequence that guarantees this fact.

Furthermore the second collection is clearly not open because deciding membership requires an infinite amount of information about the candidate sequence.

That takes care of the first step but after that Keldych’s topological proofs get very complicated.

Prikry’s promenade

At one point I met with Addison to discuss these problems and he taunted me with a story about Karel Prikry, a very smart guy who was also in the seminar. Addison claimed he’d explained the problems to Prikry, who had solved at least some almost immediately.

In particular, Prikry said he’d left the math building mulling over one problem and by the time he reached the library, he found a (topological) proof.

The library was a five minute walk away.

I left Addison’s office thinking about the problem and in five minutes arrived at the library.

I had nothing.

Five minutes later I crossed Sproul Plaza. Still nothing.

Five minutes later I arrived at home to discover that my housemates were making tequila sunrises. No more topology that evening.

Working by analogy

After my pointless preambulation I started to get worried. Even if I did figure out a topological proof, that was hardly the point. I wanted to do better than Keldych (and Prikry).

Fortunately Addison came up with a lead. He gave me a paper by Hartley Rogers in which Rogers solved a similar problem about r.e. sets. Amazingly, his proofs were elementary.

Rogers used many-one reducibility A set A of natural numbers is many-one reducible to a set B of natural numbers if there is a recursive total function f over the naturals such that for any a, a is in A iff f(a) is in B. The idea is that with f we can reduce membership in A to membership in B: to determine whether or not a is in A, we apply f, yielding b, and ask whether or not b is in B.

Sooo … let’s work by analogy.

An analogy is a systematic correspondence between similar parts of two similar things (a kind of informal isomorphism). Rogers’ and Keldysh’ problems are similar, with the problem sets corresponding.

Rogers’ sets are subsets of the set of natural numbers, Keldysh’ sets are subsets of the Baire space. Thus the set of natural numbers corresponds to the Baire space, the set of infinite sequences of natural numbers.

Rogers solved his problem using many one reducibility by recursive function. Maybe we can do the same working by analogy … using reducibility by analogous functions.

This is where Addison’s characterization of the Baire topology comes in. The functions that correspond to recursive functions are the Baire continuous functions.

Remember Addison’s characterization of Baire continuity: A is reducible to B by continuous function means there’s a filter f that consumes elements of the sequence a and incrementally produces elements of a sequence b … in such a way that a is in A iff b is in B …

If the natural numbers corresponds to the Baire space, recursive functions correspond to … continuous functions. So let’s see what it means for a subset A of the Baire space to be reducible to a subset B of the Baire space by a continuous function.

(Remembering Addison’s characterization of Baire continuity) it means there’s a filter f that consumes elements of the sequence a and incrementally produces elements of a sequence b … in such a way that a is in A iff b is in B …

The game is afoot

This all means that it’s possible for player II to win the infinite game with the following rules:

– player I starts and on each move plays a natural number
– player II follows and on each move plays a natural number or passes
– player II can never pass indefinitely
– player II wins iff his sequence of moves b is in B iff I’s sequence a is in A

Call this game G(A,B). Then A is reducible to B by continuous many-one function iff II has a winning strategy for G(A,B).

Thus you can prove that A is simpler (actually, no more complex) than B by winning a game. And just as importantly, you can show the A is not simpler than B by providing a winning strategy for I for G(A,B).

Let’s try this out with the third and second of Keldysh’ sets. A is the set of all a where some number occurs infinitely often in a, and B is the set of all b with infinitely many 0’s. I needs a strategy that guarantees that some number occurs infinitely often in a iff b does not have infinitely many 0’s.

Think about it …

Player I uses a blackboard on which she can write one number. Initially, that number is 0.

On each move I plays the number on the blackboard – unless II has just played a 0. In which case I replaces the number on the board by the current number plus one, and plays it. That is the strategy.

If II plays infinitely many 0’s, the number on the blackboard, and hence I’s plays, will increase indefinitely. None will be repeated indefinitely and I wins.

If II plays only finitely many 0’s, I will finally settle down to playing the blackboard number indefinitely, and again wins.

I is guaranteed the thrill of victory, II, the agony of defeat.

That’s the proof and we haven’t even reached the library yet.

You might want to try your hand at showing the fourth set is more complex than the third. The strategy is similar. Hint: you’ll need an inexhaustible supply of blackboards!

Saved by the bell

When I presented this to Addison he was impressed and made a remark to the effect that I’d salvaged victory from the jaws of defeat. Karel was very encouraging and pointed out that II doesn’t need to actually record her passes (as I had been doing).

Addison encouraged me to systematically study this reducibility and I was happy to do so. I’d found a thesis topic without sweating it.

One of the first discoveries was that (game) determinism implies that the reducibility is almost a linear order. If II has a winning strategy, A is reducible to B. If I has a winning strategy, it follows easily that B is reducible to the complement of A.

In other words, the Axiom of Determinateness (AD) implies that (modulo complementation) the reducibility is a linear order.

I followed up with two further results. First, the Axiom of Choice implies that there are fairly simple sets for which this “semilinear ordering” principle fails. But on the other hand, I proved without AD that it succeeds for countable Boolean combinations of open sets.

This was the first of very many results that ended up filling a 350 page dissertation which didn’t appear till 1983. (The research was done by 1971 but the writing up took 12 more years, including a few lost to procrastination).

Too much of a good thing

In fact I was very lucky to work on Keldysh’ problem when all the parts were there, waiting to be put together. Most been there for a long time but interest in infinite games was relatively new. I couldn’t have solved the problems without games.

In fact things went so well it made my story a little less interesting. It’s always better fo the hero to suffer some adversity. I can’t say I did – other than worrying about missing the seminar deadline. Addison didn’t chew me out for taking my time and Karel was supportive, not an evil nemesis.

Later on, in the world of work, I would learn about lack of respect, but not as a Berkeley grad student.

However I eventually provided my own adversity by trying to put everything I discovered in my dissertation. Three hundred and fifty pages is ridiculous. Big mistake.

I should have made a case for submitting the research I described here, up to and including the results about AD and AC. The remaining 250 pages of material would have made excellent CV filling.

You can’t win them all!