When I was a young grad student at UC Berkeley, I invented what are now called “Wadge degrees”. Not to mention “Wadge reducibility”, “Wadge games”, “Wadge’s Lemma” and the “Wadge hierarchy” (there’s a Wikipedia entry on the latter).

“So”, I am often asked, “what is this all about?”

Short answer: Wadge reducibility is a simple way to compare the complexity of two properties (sets) of real numbers. If A and B are two such sets, A≤_{W}B (or simply A≤B) iff there is a continuous total function f such that for all reals a

a is a member of A iff f(a) is a member of B

In other words, f allows you to reduce the membership question for A to the membership question for B. Since continuous functions are considered to be especially simple, we conclude that A’s membership ‘problem’ is at most as difficult as B’s.

A more concise formalization is as follows: A≤B iff A = f^{-1}(B) for some continuous f.

A small technical point: by “reals” we actually mean infinite sequences of natural numbers – the *Baire space*. The Baire space is homeomorphic to (topologically the same) as the irrationals with the induced topology. It has some technical properties that make it easier to work with.

It is easy to describe the Baire topology informally. Two sequences are close if they have a common initial sequence; the longer this sequence, the closer they are. A set is open iff whenever a sequence is a member, so are all the sequences that are close enough to it. A function is continuous iff f(x) and f(y) are close whenever x and y are close enough.Another way of putting this is that a finite initial segment of f(x) is determined by a finite initial segment of x.

For example, let A be the set of all sequences in which 0 occurs at least once, and B the set of all sequences in which 0 occurs infinitely often. Then it can be shown (not obvious from the definition given above) that A is reducible to B but B is not reducible to A.

The definition is simple enough but you need one tool to make it usable: infinite games.

Suppose there are two sets A and B and two individuals, Believer and Doubter. Suppose that Believer thinks that A≤B and wants to prove it to Doubter, who thinks they are not reducible.Believer has to come up with a continuous function that performs the reduction. It follows easily from the description of continuity that we can think of f as a black box that transforms initial segments of a into initial segments of b. This black box is therefore a continuously operating machine that incrementally produces b0, b1, b2, … one by one from a0, a1, a2, … one by one (not necessarily at the same rate). In data flow terminology, it’s a *filter*.

Doubter will try and refute the filter by choosing a0, a1, a2, … so that a∈A⇔b∈B fails, and Believer hopes that his black box will produce a b that makes it succeed. To get the game, we let Believer replace the black box and play the b’s directly in response to the a’s (Believer is allowed to pass, but not indefinitely). Then (maybe not obvious) A≤B iff Believer has a winning strategy for the game. (This is the *Wadge game*; since it depends on A and B, it is written G_{W}(A,B), or simply G(A,B).)

For example, for the particular A and B described earlier, Believer’s strategy in G(A,B) is simply to copy Doubter’s moves until (if ever) Doubter plays a 0. At that point Believer too plays a 0, and continues playing 0’s for the rest of the game.

Believer doesn’t have a winning strategy for G(B,A) but it can be hard to prove *non*existence. We don’t have to – to prove there does *not* exist a winning strategy for Believer, we simply come up with a winning strategy for Doubter. It’s not hard to find one: in G(B,A), Doubter plays 0’s until (if ever) Believer plays a 0, at which point Doubter stops playing 0’s and plays 1’s instead.

In general, it might seem like, whatever A and B are, either Believer or Doubter has a winning strategy (since there are no ties). If this is the case, the game is said to be *determined*. Unfortunately, using the axiom of choice you can cook up games that are not determined. This raises complex foundational issues.

Fortunately, if the sets involved are not too complex, for example if they are Borel sets, then G(A,B) is determined. And the determinacy of G(A,B) has a simple but important consequence.

We’ve seen that a winning strategy for Believer in G(A,B) proves that A≤B. What about a winning strategy for Doubter? Some elementary calculations show that a winning strategy for Doubter can be converted to a winning strategy for Believer in the dual game G(B,-A). This in turn proves B≤-A.

In other words, if G(A,B) is determined, then A≤B or B≤-A. (This is *Wadge’s lemma*.)Thus if we restrict ourselves to Borel sets A and B, so that G(A,B) is determined, ≤ is *almost* a linear order.

Pretty simple stuff! Of course there’s a lot more to tell, but not in this post. I’ll leave you with a challenge. Let A be the set of all sequences in which some number occurs infinitely often, and B the set of all sequences in which all but a finite number of numbers eventually appear. How does ≤ relate them?

Pingback: Wadge Degrees – The Origin Story - GistTree

Pingback: Wadge Degrees – The Origin Story | صحافة حرة FREE PRESS