Wadge Hierarchy - Wadge Degrees

Wadge Degrees

Suppose and are subsets of Baire space ωω. is Wadge reducible to or ≤_W if there is a continuous function on ωω with . 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 is denoted by _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 ≤_W and is a countable intersection of open sets, then so is . 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.