Wadge Hierarchy - Wadge and Lipschitz Games

Wadge and Lipschitz Games

The Wadge game is a simple infinite game discovered by William Wadge (pronounced "wage"). It is used to investigate the notion of continuous reduction for subsets of Baire space. Wadge had analyzed the structure of the Wadge hierarchy for Baire space with games by 1972, but published these results only much later in his PhD thesis. In the Wadge game, player I and player II each in turn play integers which may depend on those played before. The outcome of the game is determined by checking whether the sequences x and y generated by players I and II are contained in the sets A and B, respectively. Player II wins if the outcome is the same for both players, i.e. is in if and only if is in . Player I wins if the outcome is different. Sometimes this is also called the Lipschitz game, and the variant where player II has the option to pass (but has to play infinitely often) is called the Wadge game.

Suppose for a moment that the game is determined. If player I has a winning strategy, then this defines a continuous (even Lipschitz) map reducing to the complement of, and if on the other hand player II has a winning strategy then you have a reduction of to . For example, suppose that player II has a winning strategy. Map every sequence x to the sequence y that player II plays in if player I plays the sequence x, where player II follows his or her winning strategy. This defines a is a continuous map f with the property that x is in if and only if f(x) is in .

Wadge's lemma states that under the axiom of determinacy (AD), for any two subsets of Baire space, ≤_W or ≤_W ωω–. The assertion that the Wadge lemma holds for sets in Γ is the semilinear ordering principle for Γ or SLO(Γ). Any semilinear order defines a linear order on the equivalence classes modulo complements. Wadge's lemma can be applied locally to any pointclass Γ, for example the Borel sets, Δ1_n sets, Σ1_n sets, or Π1_n sets. It follows from determinacy of differences of sets in Γ. Since Borel determinacy is proved in ZFC, ZFC implies Wadge's lemma for Borel sets.