In
descriptive set theory
In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to ot ...
, within
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Wadge degrees are levels of complexity for sets of
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010)
...
s. Sets are compared by
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. Wadge.
Wadge degrees
Suppose
and
are subsets of
Baire space
In mathematics, a topological space X is said to be a Baire space if countable unions of closed sets with empty interior also have empty interior.
According to the Baire category theorem, compact Hausdorff spaces and complete metric spaces are ...
ω
ω. Then
is Wadge reducible to
or
≤
W if there is a continuous function
on ω
ω with
">math>Asub>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
A ≤
W B and
B is a
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
of
open set
In mathematics, open sets are a generalization of open intervals in the real line.
In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are suf ...
s, then so is
A. The same works for all levels of the
Borel hierarchy In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number called ...
and the
difference hierarchy. The Wadge hierarchy plays an important role in models of the
axiom of determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...
. Further interest in Wadge degrees comes from
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, where some papers have suggested Wadge degrees are relevant to
algorithmic complexity
Algorithmic may refer to:
*Algorithm, step-by-step instructions for a calculation
**Algorithmic art, art made by an algorithm
**Algorithmic composition, music made by an algorithm
** Algorithmic trading, trading decisions made by an algorithm
**Alg ...
.
Wadge's lemma states that under the
axiom of determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...
(
AD), for any two subsets
A,B of Baire space,
A ≤
W B or
B ≤
W ω
ω\
A.
[D. Martin, H. G. Dales, ''Truth in Mathematics'', ch. "Mathematical Evidence", p.224. Oxford Science Publications, 1998.] The assertion that the Wadge lemma holds for sets in Γ is the ''semilinear ordering principle'' for Γ or SLO(Γ). Any defines a linear order on the equivalence classes modulo complements. Wadge's lemma can be applied locally to any
pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
Γ, for example the
Borel set
In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are named ...
s, Δ
1n sets, Σ
1n sets, or Π
1n sets. It follows from determinacy of differences of sets in Γ. Since
Borel determinacy In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game. A Gale-Stewart game is a poss ...
is proved in
ZFC, ZFC implies Wadge's lemma for Borel sets.
Wadge's lemma is similar to the
cone lemma from computability theory.
Wadge's lemma via Wadge and Lipschitz games
The Wadge game is a simple infinite
game
A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...
discovered by William Wadge (pronounced "wage"). It is used to investigate the notion of continuous reduction for subsets of Baire space. Wadge had analyzed the structure of the Wadge hierarchy for Baire space with games by 1972, but published these results only much later in his PhD thesis. In the Wadge game
G(A,B), player I and player II each in turn play integers, and the outcome of the game is determined by checking whether the sequences ''x'' and ''y'' generated by players I and II are contained in the sets ''A'' and ''B'', respectively. Player II wins if the outcome is the same for both players, i.e.
x is in
A if and only if
y is in
B. Player I wins if the outcome is different. Sometimes this is also called the ''Lipschitz game'', and the variant where player II has the option to pass finitely many times is called the Wadge game.
Suppose that the game is
determined. If player I has a winning strategy, then this defines a continuous (even
Lipschitz) map reducing
B to the complement of
A, and if on the other hand player II has a winning strategy then you have a reduction of
A to
B. For example, suppose that player II has a winning strategy. Map every sequence ''x'' to the sequence ''y'' that player II plays in
G(A,B) if player I plays the sequence ''x'', and player II follows his or her winning strategy. This defines a continuous map ''f'' with the property that ''x'' is in
A if and only if ''f''(''x'') is in
B.
Structure of the Wadge hierarchy
Martin Martin may refer to:
Places
* Martin City (disambiguation)
* Martin County (disambiguation)
* Martin Township (disambiguation)
Antarctica
* Martin Peninsula, Marie Byrd Land
* Port Martin, Adelie Land
* Point Martin, South Orkney Islands
Austral ...
and Monk proved in 1973 that
AD implies the Wadge order for Baire space is
well founded
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s&n ...
. Hence under AD, the Wadge classes modulo complements form a wellorder. The Wadge rank of a set
A is the order type of the set of Wadge degrees modulo complements strictly below
A">math>Asub>W. The length of the Wadge hierarchy has been shown to be
Θ. Wadge also proved that the length of the Wadge hierarchy restricted to the Borel sets is φ
ω1(1) (or φ
ω1(2) depending on the notation), where φ
''γ'' is the ''γ''
th Veblen function
In mathematics, the Veblen functions are a hierarchy of normal functions ( continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If φ0 is any normal function, then for any non-zero ordinal α, φ ...
to the base ω
1 (instead of the usual ω).
As for the Wadge lemma, this holds for any pointclass Γ, assuming the
axiom of determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...
. If we associate with each set
A the collection of all sets strictly below
A on the Wadge hierarchy, this forms a pointclass. Equivalently, for each ordinal ''α'' ≤ θ the collection W
''α'' of sets that show up before stage ''α'' is a
pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
. Conversely, every pointclass is equal to some
W''α''. A pointclass is said to be ''self-dual'' if it is
closed under complementation. It can be shown that W
''α'' is self-dual if and only if ''α'' is either 0, an
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
successor ordinal In set theory, the successor of an ordinal number ''α'' is the smallest ordinal number greater than ''α''. An ordinal number that is a successor is called a successor ordinal. Properties
Every ordinal other than 0 is either a successor ordin ...
, or a
limit ordinal
In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists an ...
of
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
cofinality
In mathematics, especially in order theory, the cofinality cf(''A'') of a partially ordered set ''A'' is the least of the cardinalities of the cofinal subsets of ''A''.
This definition of cofinality relies on the axiom of choice, as it uses the ...
.
Other notions of degree
Similar notions of reduction and degree arise by replacing the continuous functions by any class of functions ''F'' that contains the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
and is closed under
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
. Write
A ≤
F B if
A = f^ /math> for some function f in ''F''. Any such class of functions again determines a preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
on the subsets of Baire space. Degrees given by Lipschitz function
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there exi ...
s are called ''Lipschitz degrees'', and degrees from Borel function
In mathematics and in particular measure theory, a measurable function is a function between the underlying sets of two measurable spaces that preserves the structure of the spaces: the preimage of any measurable set is measurable. This is in d ...
s ''Borel–Wadge degrees''.
See also
* Analytical hierarchy
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
* Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
* Axiom of determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...
* Borel hierarchy In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number called ...
* Determinacy
Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and sim ...
* Pointclass
In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...
* Weihrauch reducibility
References
*
* .
*
*
*
Further reading
*
*
*
*
*
* {{cite journal , author = Semmes, Brian T., title = A game for the Borel Functions , version = preprint , publisher = Univ. of Amsterdam, ILLC Prepublications PP-2006-24 , date=2006 , url = http://dare.uva.nl/en/record/174524 , accessdate = 2007-08-12
Descriptive set theory
Mathematical logic hierarchies