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:
“Complete courage and absolute cowardice are extremes that very few men fall into. The vast middle space contains all the intermediate kinds and degrees of courage; and these differ as much from one another as men’s faces or their humors do.”
—François, Duc De La Rochefoucauld (1613–1680)