- Wadge hierarchy
In

descriptive set theory ,**Wadge degrees**are levels of complexity for sets of reals and more comprehensively, subsets of any giventopological space . Sets are compared bycontinuous reductions. The**Wadge hierarchy**is the structure of Wadge degrees.**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 : $Ale\_W\; B$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 orquasiorder on the subsets of $X$. This is the**Wadge order**for $X$.Equivalence class es 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 otherPolish space s. 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 ofopen set s, then so is $A$. The same works for all levels of theBorel hierarchy and thedifference 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 .**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.: $xin\; ALeftrightarrow\; yin\; 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 (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 theaxiom of determinacy (AD), for any two subsets $A,B$ of Baire space: $Ale\_W\; Bor\; Ble\_W\; omega^omega\; -\; A$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 topointclass es Γ, for example the Borel sets,**Δ**^{1}_{n}sets,**Σ**^{1}_{n}sets, or**Π**^{1}_{n}sets. Here the conclusion of Wadge's lemma for sets in Γ follows from determinacy ofBoolean combinations of sets in Γ instead of full AD. Since Borel determinacy is proved inZFC , 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.**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 ω_{1}(instead of the usual ω).**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 $alphamath>\; the\; set$ A\_alpha=\{\; B|B$shows\; up\; before\; stage$ alpha\}$is\; a\; pointclass.\; Conversely,\; every\; pointclass\; (except\; for\; the\; trivial\; pointclass\; of\; all\; sets)\; is\; equal\; to\; some$ A\_alpha$.\; A\; pointclass\; is\; said\; to\; be\; "self-dual"\; if\; it\; isclosedunder\; complementation.$

It can be shown that $A\_alpha$ is self-dual if and only if $alpha$ is either 0, an even

successor ordinal , or alimit ordinal ofcountable cofinality .**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: $Ale\_\; emph\; exttt\{F\}\; B$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".

**See also***

Analytical hierarchy

*Arithmetical hierarchy

*Axiom of determinacy

*Borel hierarchy

*Determinacy

*Pointclass **References***, in preparation

*

*

***Further reading***

*

*

*

*

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Hierarchy (mathematics)**— In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of… … Wikipedia**Borel hierarchy**— In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number… … Wikipedia**Determinacy**— Determined redirects here. For the 2005 heavy metal song, see Determined (song). For other uses, see Indeterminacy (disambiguation). In set theory, a branch of mathematics, determinacy is the study of under what circumstances one or the other… … Wikipedia**Descriptive set theory**— In mathematical logic, descriptive set theory is the study of certain classes of well behaved subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other… … Wikipedia**Set theory**— This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects … Wikipedia**Hiérarchie de Borel**— La hiérarchie de Borel désigne une description de la tribu des boréliens d un espace topologique X comme une réunion croissante d ensembles de parties de X, indexée par le premier ordinal non dénombrable. Sommaire 1 Notations préliminaires 2… … Wikipédia en Français**List of mathematics articles (W)**— NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… … Wikipedia**Inductive set**— This article relates to the notion of inductive sets from descriptive set theory. For the notion in the context of the axiom of infinity, see Inductive set (axiom of infinity). In descriptive set theory, an inductive set of real numbers (or more… … Wikipedia**Pointclass**— In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a point is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by some… … Wikipedia