Wadge hierarchy

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
WikiProject Mathematics or the Mathematics Portal may be able to help recruit one.
If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

This article or section does not cite its references or sources.
Please help improve this article by introducing appropriate citations. (help, get involved!) This article has been tagged since June 2006.

This article or section may require cleanup to meet Wikipedia's quality standards.
Please help improve this article or replace this tag with a more specific message. This article has been tagged since June 2006. (help, talk)

[edit] Wadge reducibility

Take A a subset of X and B a subset of Y, where X and Y are Polish metric spaces (see Polish space). A is Wadge reducible to B (write A <= B) if and only if there is a continuous function f: X->Y such that if x is a member of A then f(x) is a member of B for all x in X.

[edit] Wadge degrees

Wadge reducibility can be used to order sets. Equivalence classes of sets under this order are called Wadge degrees.

Some properties of Wadge degrees include, its consistency with other absolute measures of complexity stated in terms of ease of definiability; for example, if A <= B and B is a countable intersection of open sets, then so is A.

Wadge also found a simple infinite game G(A,B) with the property that A <= B if and only if player II has a winning strategy for G(A,B). This game proves that the axiom of determinancy implies that we always have either A <= B or B <= - A; so that <= is (modulo complementation) a linear order. He also proved that on the Borel sets it's actually a well order, and calculated the order type.

Some papers have suggested Wadge degrees are relevant to algorithmic complexity.