Wadge hierarchy

From Wikipedia, the free encyclopedia

In descriptive set theory, Wadge degrees are levels of complexity for sets of reals and more comprehensively, subsets of any given topological space. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees.

Contents 1 Wadge degrees 2 Wadge game 3 Wadge hierarchy 3.1 Structure of the Wadge hierarchy 4 Other notions of degree 5 See also 6 References 7 Further reading

[edit] Wadge degrees

Take A a subset of X and B a subset of Y, where X and Y are topological spaces. A is Wadge reducible to B, denoted by

if and only if there is a continuous function f from X to Y such that A = f ^{− 1}(B). The notion of reduction depends on the spaces X and Y.

For a given topological space X, Wadge reducibility determines a preorder or quasiorder on the subsets of X. This is the Wadge order for X. Equivalence classes of sets under this preorder are called Wadge degrees, the degree of a set A is denoted by [A]_W. The set of Wadge degrees ordered by the Wadge order is called the Wadge hierarchy. Wadge degrees are usually considered for Baire space ω^ω, Cantor space, and other Polish spaces. If the underlying space is not specified, the terms Wadge degree and Wadge hierarchy usually refer to Baire space.

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.

Wadge degrees for Baire space play 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.

[edit] Wadge game

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 G(A,B), 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.

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 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, where player II follows his or her winning strategy. This defines a is a continuous map f with the property that x is in A if and only if f(x) is in B.

Wadge's lemma states that under the axiom of determinacy (AD), for any two subsets A,B of Baire space

This works since one of the players has a winning strategy in the Wadge game G(A,B), and this strategy defines one of the continuous maps needed. The lemma can also be applied locally to pointclasses Γ, for example the Borel sets, Δ¹_n sets, Σ¹_n sets, or Π¹_n sets. Here the conclusion of Wadge's lemma for sets in Γ follows from determinacy of Boolean combinations of sets in Γ instead of full AD. Since Borel determinacy is proved in ZFC, ZFC implies Wadge's lemma for Borel sets.

The assertion that the Wadge lemma holds for sets in Γ is the semilinear ordering principle for Γ, SLO(Γ). Any semilinear order defines a linear order on the equivalence classes modulo complements. In this case the relation on the set of pairs {A,ω^ω − A} given by {A,ω^ω − A} ≤_W {B,ω^ω − B} if and only if A ≤_W B or A ≤_W ω^ω − B, is linear.

[edit] Wadge hierarchy

Martin and Monk proved in 1973 that AD implies the Wadge order for Baire space is well founded. As for the Wadge lemma, this holds for any pointclass Γ, assuming it is determined.

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 [A]_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 ω).

[edit] Structure of the Wadge hierarchy

Continuing to work under 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 set A_α = {B | B shows up before stage α} is a pointclass. Conversely, every pointclass (except for the trivial pointclass of all sets) is equal to some A_α. A pointclass is said to be self-dual if it is closed under complementation.

It can be shown that A_α is self-dual if and only if α is either 0, an even successor ordinal, or a limit ordinal of countable cofinality.

[edit] Other notions of degree

Similar notions of reduction and degree for subsets of a topological space X arise by replacing the continuous functions by any class of functions F which contains the identity function and is closed under composition. Write

if A = f ^{− 1}(B) for some function f in the class F. Any such class of functions again determines a preorder on the subsets of X. Degrees given by Lipschitz functions are called Lipschitz degrees, and degrees from Borel functions Borel-Wadge degrees.

[edit] See also

• Analytical hierarchy
• Arithmetical hierarchy
• Axiom of determinacy
• Borel hierarchy
• Determinacy
• Pointclass

[edit] References

• Andretta, Alessandro (2005), “The SLO principle and the Wadge hierarchy”, in Bold, Stefan; Löwe, Benedikt & Räsch, Thoralf et al., Infinite Games, Papers of the conference "Foundations of the Formal Sciences V" held in Bonn, Nov 26-29, 2004 , in preparation
• Kanamori, Akihiro (2000). The Higher Infinite, second edition. Springer. ISBN 3-540-00384-3. 
• Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Springer. ISBN 0-387-94374-9. 
• Wadge, William W. (1983). "Reducibility and determinateness on the Baire space". PhD thesis. . Univ. of California, Berkeley

[edit] Further reading

• Andretta, Alessandro and Martin, Donald (2003). "Borel-Wadge degrees". Fundamenta Mathematicae 177 (2): 175–192. 
• Cenzer, Douglas (1984). "Monotone Reducibility and the Family of Infinite Sets". The Journal of Symbolic Logic 49 (3): 774–782. doi:10.2307/2274130. 
• Selivanov, Victor L. (2006). "Towards a descriptive set theory for domain-like structures". Theoretical Computer Science Archive, Spatial representation: Discrete vs. continuous computational models 365 (3): 258–282. ISSN:0304-3975. 
• Semmes, Brian T. (2006). "A game for the Borel Functions". preprint. . Univ. of Amsterdam, ILLC Prepublications PP-2006-24 Retrieved on 2007-08-12.