In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals.
Sets are compared by continuous reductions.
These concepts are named after William W. Wadge.
The Wadge order is the preorder or quasiorder on the subsets of Baire space.
Properties of Wadge degrees include their consistency with measures of complexity stated in terms of definability.
is a countable intersection of open sets, then so is
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
It follows from determinacy of differences of sets in Γ.
Since Borel determinacy is proved in ZFC, ZFC implies Wadge's lemma for Borel sets.
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.
, 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.
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.
If player I has a winning strategy, then this defines a continuous (even Lipschitz) map reducing
, and if on the other hand player II has a winning strategy then you have a reduction of
For example, suppose that player II has a winning strategy.
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.
is the order type of the set of Wadge degrees modulo complements strictly below [
]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 ω).
As for the Wadge lemma, this holds for any pointclass Γ, assuming the axiom of determinacy.
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.
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.
in F. Any such class of functions again determines a preorder on the subsets of Baire space.