Wadge hierarchy

Last updated February 16, 2024

In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. Wadge.

Wadge degrees

Suppose $A$ and $B$ are subsets of Baire space ω^ω. Then $A$ is Wadge reducible to $B$ or $A$ ≤_W $B$ if there is a continuous function $f$ on ω^ω with $A=f^{-1}[B]$ . 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 $A$ is denoted by [ $A$ ]_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 intersection of open sets, then so is $A$ . 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.

Wadge's lemma states that under the axiom of determinacy (AD), for any two subsets $A,B$ of Baire space, $A$ ≤_W $B$ or $B$ ≤_W ω^ω\ $A$ .^[1] The assertion that the Wadge lemma holds for sets in Γ is the semilinear ordering principle for Γ or SLO(Γ). Any semilinear order defines a linear order on the equivalence classes modulo complements. Wadge's lemma can be applied locally to any pointclass Γ, for example the Borel sets, Δ¹_n sets, Σ¹_n sets, or Π¹_n sets. It follows from determinacy of differences of sets in Γ. Since Borel determinacy 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 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 and Monk proved in 1973 that AD implies the Wadge order for Baire space is well founded. 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$ ]_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) (or φ_ω₁(2) depending on the notation), where φ_γ is the γ^th Veblen function to the base ω₁ (instead of the usual ω).

As for the Wadge lemma, this holds for any pointclass Γ, assuming the axiom of determinacy. 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. 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 successor ordinal, or a limit ordinal of countable cofinality.

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 and is closed under composition. Write $A$ ≤_F $B$ if $A=f^{-1}[B]$ for some function $f$ in F. Any such class of functions again determines a preorder on the subsets of Baire space. Degrees given by Lipschitz functions are called Lipschitz degrees, and degrees from Borel functions Borel–Wadge degrees.

Related Research Articles

In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family $of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.$

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory — as a branch of mathematics — is mostly concerned with those that are relevant to mathematics as a whole.

In mathematics, a Borel set is any set in a topological space that can be formed from open sets through the operations of countable union, countable intersection, and relative complement. Borel sets are named after Émile Borel.

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.

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 other areas of mathematics such as functional analysis, ergodic theory, the study of operator algebras and group actions, and mathematical logic.

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 over both the set of natural numbers, $, and over functions from to . The analytical hierarchy of sets classifies sets by the formulas that can be used to define them; it is the lightface version of the projective hierarchy.$

In the mathematical field of descriptive set theory, a subset of a Polish space $is an analytic set if it is a continuous image of a Polish space. These sets were first defined by Luzin (1917) and his student Souslin (1917) .$

In mathematics, the axiom of determinacy 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 a certain type is determined; that is, one of the two players has a winning strategy.

In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology. This space is commonly used in descriptive set theory, to the extent that its elements are often called "reals". It is denoted N^N, ^ωω, by the symbol $or also ω ω, not to be confused with the countable ordinal obtained by ordinal exponentiation.$

A subset $of a topological space has the property of Baire, or is called an almost open set, if it differs from an open set by a meager set; that is, if there is an open set such that is meager.$

In set theory, a subset of a Polish space $is \infty-Borel if it can be obtained by starting with the open subsets of, and transfinitely iterating the operations of complementation and well-ordered union. This concept is usually considered without the assumption of the axiom of choice, which means that the \infty-Borel sets may fail to be closed under well-ordered union; see below.$

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 similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

In set theory, AD⁺ is an extension, proposed by W. Hugh Woodin, to the axiom of determinacy. The axiom, which is to be understood in the context of ZF plus DC (the axiom of dependent choice for real numbers), states two things:

Every set of reals is ∞-Borel.
For any ordinal λ less than Θ, any subset A of ω^ω, and any continuous function π:λ^ω→ω^ω, the preimage π⁻¹[A] is determined. (Here λ^ω is to be given the product topology, starting with the discrete topology on λ.)

In set theory, a branch of mathematics, the difference hierarchy over a pointclass is a hierarchy of larger pointclasses generated by taking differences of sets. If Γ is a pointclass, then the set of differences in Γ is $. In usual notation, this set is denoted by 2-Γ. The next level of the hierarchy is denoted by 3-Γ and consists of differences of three sets: . This definition can be extended recursively into the transfinite to α -Γ for some ordinal α .$

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 some sort of definability property; for example, the collection of all open sets in some fixed collection of Polish spaces is a pointclass.

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 possibly infinite two-player game, where both players have perfect information and no randomness is involved.

This is a glossary of set theory.

The Moschovakis coding lemma is a lemma from descriptive set theory involving sets of real numbers under the axiom of determinacy. The lemma was developed and named after the mathematician Yiannis N. Moschovakis.

References

↑ D. Martin, H. G. Dales, Truth in Mathematics, ch. "Mathematical Evidence", p.224. Oxford Science Publications, 1998.

Alexander S. Kechris; Benedikt Löwe; John R. Steel, eds. (December 2011). Wadge Degrees and Projective Ordinals: The Cabal Seminar Volume II. Lecture Notes in Logic. Cambridge University Press. ISBN 9781139504249.
Andretta, Alessandro (2007). "The SLO principle and the Wadge hierarchy". In Bold, Stefan; Benedikt Löwe; Räsch, Thoralf; et al. (eds.). Infinite Games, Papers of the conference "Foundations of the Formal Sciences V" held in Bonn, Nov 26-29, 2004. Studies in Logic. Vol. 11. College Publications. pp. 1–38. ISBN 9781904987758..
Kanamori, Akihiro (2000). The Higher Infinite (second ed.). Springer. ISBN 3-540-00384-3.
Kechris, Alexander S. (1995). Classical Descriptive Set Theory . Springer. ISBN 0-387-94374-9.
Wadge, William W. (1983). "Reducibility and determinateness on the Baire space" (PDF). PhD thesis. Univ. of California, Berkeley.{{cite journal}}: Cite journal requires |journal= (help)