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:
“For the profit of travel: in the first place, you get rid of a few prejudices.... The prejudiced against color finds several hundred millions of people of all shades of color, and all degrees of intellect, rank, and social worth, generals, judges, priests, and kings, and learns to give up his foolish prejudice.”
—Herman Melville (1819–1891)