Wadge Degrees (2015)

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≤_WB (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 nonexistence. 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?

from Hacker News https://ift.tt/31EjJuu