Wadge Hierarchy

In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. Wadge.

Wadge degrees

Suppose $A$ and $B$ are subsets of Baire space ω^ω. Then $A$ is Wadge reducible to $B$ or $A$ ≤_W $B$ if there is a continuous function $f$ on ω^ω with A = f^ /math>. The Wadge order is the preorder or quasiorder on the subsets of Baire space. Equivalence classes of sets under this preorder are called Wadge degrees, the degree of a set $A$ is denoted by math>Asub>W. The set of Wadge degrees ordered by the Wadge order is called the Wadge hierarchy.

Properties of Wadge degrees include their consistency with measures of complexity stated in terms of definability. For example, if $A$ ≤_W $B$ and $B$ is a countable intersection of open sets, then so is $A$. The same works for all levels of the Borel hierarchy and the difference hierarchy. The Wadge hierarchy plays an important role in models of the axiom of determinacy. Further interest in Wadge degrees comes from computer science, where some papers have suggested Wadge degrees are relevant to algorithmic complexity.

Wadge's lemma states that under the axiom of determinacy ( AD), for any two subsets $A,B$ of Baire space, $A$ ≤_W $B$ or $B$ ≤_W ω^ω\$A$.D. Martin, H. G. Dales, ''Truth in Mathematics'', ch. "Mathematical Evidence", p.224. Oxford Science Publications, 1998. The assertion that the Wadge lemma holds for sets in Γ is the ''semilinear ordering principle'' for Γ or SLO(Γ). Any 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, Δ¹_n sets, Σ¹_n sets, or Π¹_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.

Wadge's lemma is similar to the cone lemma from computability theory.

Wadge's lemma via Wadge and Lipschitz games

The Wadge game is a simple infinite game 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 $G(A,B)$, player I and player II each in turn play integers, and 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. $x$ is in $A$ if and only if $y$ is in $B$. 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 finitely many times is called the Wadge game.

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

Structure of the Wadge hierarchy

Martin and Monk proved in 1973 that AD implies the Wadge order for Baire space is well founded. Hence under AD, the Wadge classes modulo complements form a wellorder. The Wadge rank of a set $A$ is the order type of the set of Wadge degrees modulo complements strictly below math>Asub>W. The length of the Wadge hierarchy has been shown to be Θ. Wadge also proved that the length of the Wadge hierarchy restricted to the Borel sets is φ_ω1(1) (or φ_ω1(2) depending on the notation), where φ_''γ'' is the ''γ''^th Veblen function to the base ω₁ (instead of the usual ω).

As for the Wadge lemma, this holds for any pointclass Γ, assuming the axiom of determinacy. If we associate with each set $A$ the collection of all sets strictly below $A$ on the Wadge hierarchy, this forms a pointclass. Equivalently, for each ordinal ''α'' â‰¤ Î¸ the collection W_''α'' of sets that show up before stage ''α'' is a pointclass. Conversely, every pointclass is equal to some $W$_''α''. A pointclass is said to be ''self-dual'' if it is closed under complementation. It can be shown that W_''α'' is self-dual if and only if ''α'' is either 0, an even successor ordinal, or a limit ordinal of countable cofinality.

Other notions of degree

Similar notions of reduction and degree arise by replacing the continuous functions by any class of functions ''F'' that contains the identity function and is closed under composition. Write $A$ ≤_F $B$ if A = f^ /math> for some function $f$ in ''F''. Any such class of functions again determines a preorder on the subsets of Baire space. Degrees given by Lipschitz functions are called ''Lipschitz degrees'', and degrees from Borel functions ''Borel–Wadge degrees''.

See also

*
*
*
*
*
*
*
*

References

*
* .
*
*
*

Further reading

*
*
*
*
*
* {{cite report , author = Harry Bliss , title = The Tree Game for the Borel Functions , type = Preprint , publisher = Univ. of Amsterdam, ILLC Prepublications PP-2006-24 , date=2006 , url = http://dare.uva.nl/en/record/174524 , accessdate = 2007-08-12

Descriptive set theory
Mathematical logic hierarchies