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.
Read more about this topic: Wadge Hierarchy
Famous quotes containing the word degrees:
“The most durable thing in writing is style, and style is the most valuable investment a writer can make with his time. It pays off slowly, your agent will sneer at it, your publisher will misunderstand it, and it will take people you have never heard of to convince them by slow degrees that the writer who puts his individual mark on the way he writes will always pay off.”
—Raymond Chandler (1888–1959)