Silver's dichotomy

Last updated May 18, 2023

In descriptive set theory, a branch of mathematics, Silver's dichotomy (also known as Silver's theorem)^[1] is a statement about equivalence relations, named after Jack Silver.^[2]^[3]

Statement and history

A relation is said to be coanalytic if its complement is an analytic set. Silver's dichotomy is a statement about the equivalence classes of a coanalytic equivalence relation, stating any coanalytic equivalence relation either has countably many equivalence classes, or else there is a perfect set of reals that are each incomparable to each other.^[4] In the latter case, there must be uncountably many equivalence classes of the relation.^[2]

The first published proof of Silver's dichotomy was by Jack Silver, appearing in 1980 in order to answer a question posed by Harvey Friedman.^[5] One application of Silver's dichotomy appearing in recursive set theory is since equality restricted to a set $X$ is coanalytic, there is no Borel equivalence relation $R$ such that $(=\upharpoonright \aleph _{0})\leq _{B}R\leq _{B}(=\upharpoonright 2^{\aleph _{0}})$ , where $\leq _{B}$ denotes Borel-reducibility. Some later results motivated by Silver's dichotomy founded a new field known as invariant descriptive set theory, which studies definable equivalence relations. Silver's dichotomy also admits several weaker recursive versions, which have been compared in strength with subsystems of second-order arithmetic from reverse mathematics,^[2] while Silver's dichotomy itself is provably equivalent to $\Pi _{1}^{1}{\mathsf {-CA}}_{0}$ over ${\mathsf {RCA}}_{0}$ .^[1]

Related Research Articles

In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set $contains 3 elements, and therefore has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers. The cardinality of a set is also called its size, when no confusion with other notions of size is possible.$

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 cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric preorder is an equivalence relation.

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.

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. Intuitively, forcing can be thought of as a technique to expand the set theoretical universe $to a larger universe by introducing a new "generic" object .$

In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets. In other words, the set itself is finite, and all of its elements are finite sets, recursively all the way down to the empty set.

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 computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.

In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers $, sometimes called the continuum. It is an infinite cardinal number and is denoted by or .$

In mathematics, a Borel equivalence relation on a Polish space X is an equivalence relation on X that is a Borel subset of X × X.

In mathematical logic, Heyting arithmetic $is an axiomatization of arithmetic in accordance with the philosophy of intuitionism. It is named after Arend Heyting, who first proposed it.$

In model theory, a branch of mathematical logic, the spectrum of a theory is given by the number of isomorphism classes of models in various cardinalities. More precisely, for any complete theory T in a language we write I(T, κ) for the number of models of T (up to isomorphism) of cardinality κ. The spectrum problem is to describe the possible behaviors of I(T, κ) as a function of κ. It has been almost completely solved for the case of a countable theory T.

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with " $" and " " of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.$

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.

In mathematics, ψ₀(Ω_ω), widely known as Buchholz's ordinal, is a large countable ordinal that is used to measure the proof-theoretic strength of some mathematical systems. In particular, it is the proof theoretic ordinal of the subsystem $-CA 0 of second-order arithmetic; this is one of the "big five" subsystems studied in reverse mathematics (Simpson 1999). It is also the proof-theoretic ordinal of, the theory of finitely iterated inductive definitions, and of, a fragment of Kripke-Platek set theory extended by an axiom stating every set is contained in an admissible set. Buchholz's ordinal is also the order type of the segment bounded by in Buchholz's ordinal notation . Lastly, it can be expressed as the limit of the sequence:,,, ...$

In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, x^y, together with induction for formulas with bounded quantifiers.

In mathematics, the effective topos $introduced by Martin Hyland (1982) captures the mathematical idea of effectivity within the category theoretical framework.$

In the mathematical discipline of set theory, a cardinal characteristic of the continuum is an infinite cardinal number that may consistently lie strictly between , and the cardinality of the continuum, that is, the cardinality of the set $of all real numbers. The latter cardinal is denoted or . A variety of such cardinal characteristics arise naturally, and much work has been done in determining what relations between them are provable, and constructing models of set theory for various consistent configurations of them.$

In descriptive set theory and related areas of mathematics, a hyperfinite equivalence relation on a standard Borel space X is a Borel equivalence relation E with countable classes, that can, in a certain sense, be approximated by Borel equivalence relations that have finite classes.

In descriptive set theory, specifically invariant descriptive set theory, countable Borel relations are a class of relations between standard Borel space which are particularly well behaved. This concept encapsulates various more specific concepts, such as that of a hyperfinite equivalence relation, but is of interest in and of itself.

References

1 2 S. G. Simpson, "Subsystems of Z₂ and Reverse Mathematics", p.442. Appearing in G. Takeuti, Proof Theory (1987), ISBN 0 444 87943 9.
1 2 3 L. Yanfang, On Silver's Dichotomy, Ph.D thesis. Accessed 30 August 2022.
↑ Sy D. Friedman, Consistency of the Silver dichotomy in generalized Baire space, Fundamenta Mathematicae (2014). Accessed 30 August 2022.
↑ A. Kechris, New Directions in Descriptive Set Theory (1999, p.165). Accessed 1 September 2022.
↑ J. Silver, Counting the number of equivalence classes of Borel and coanalytic equivalence relations (Annals of Mathematical Logic, 1980, received 1977). Accessed 31 August 2022.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Simpson87-1] 1 2 S. G. Simpson, "Subsystems of Z₂ and Reverse Mathematics", p.442. Appearing in G. Takeuti, Proof Theory (1987), ISBN 0 444 87943 9.

[YanfangThesis-2] 1 2 3 L. Yanfang, On Silver's Dichotomy, Ph.D thesis. Accessed 30 August 2022.

[FriedmanConsistency-3] Sy D. Friedman, Consistency of the Silver dichotomy in generalized Baire space, Fundamenta Mathematicae (2014). Accessed 30 August 2022.

[NewDirections-4] A. Kechris, New Directions in Descriptive Set Theory (1999, p.165). Accessed 1 September 2022.

[Silver80-5] J. Silver, Counting the number of equivalence classes of Borel and coanalytic equivalence relations (Annals of Mathematical Logic, 1980, received 1977). Accessed 31 August 2022.

[1]

[2]

[3]

[4]

[5]