|
Solovay
Robert Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory. Biography Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on ''A Functorial Form of the Differentiable Riemann–Roch theorem''. Solovay has spent his career at the University of California at Berkeley, where his Ph.D. students include W. Hugh Woodin and Matthew Foreman. Work Solovay's theorems include: * Solovay's theorem showing that, if one assumes the existence of an inaccessible cardinal, then the statement "every set of real numbers is Lebesgue measurable" is consistent with Zermelo–Fraenkel set theory without the axiom of choice; * Isolating the notion of 0#; * Proving that the existence of a real-valued measurable cardinal is equiconsistent with the existence of a measurable cardinal; * Proving that if \lambda is a strong limit singular cardinal, greater than a strongly compac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solovay's Theorem
In the mathematical field of set theory, the Solovay model is a model constructed by in which all of the axioms of Zermelo–Fraenkel set theory (ZF) hold, exclusive of the axiom of choice, but in which all sets of real numbers are Lebesgue measurable. The construction relies on the existence of an inaccessible cardinal. In this way Solovay showed that the axiom of choice is essential to the proof of the existence of a non-measurable set, at least granted that the existence of an inaccessible cardinal is consistent with ZFC, the axioms of Zermelo–Fraenkel set theory including the axiom of choice. Statement ZF stands for Zermelo–Fraenkel set theory, and DC for the axiom of dependent choice. Solovay's theorem is as follows. Assuming the existence of an inaccessible cardinal, there is an inner model of ZF + DC of a suitable forcing extension ''V'' 'G''such that every set of reals is Lebesgue measurable, has the perfect set property, and has the Baire property. Construction ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solovay Model
In the mathematical field of set theory, the Solovay model is a model constructed by in which all of the axioms of Zermelo–Fraenkel set theory (ZF) hold, exclusive of the axiom of choice, but in which all sets of real numbers are Lebesgue measurable. The construction relies on the existence of an inaccessible cardinal. In this way Solovay showed that the axiom of choice is essential to the proof of the existence of a non-measurable set, at least granted that the existence of an inaccessible cardinal is consistent with ZFC, the axioms of Zermelo–Fraenkel set theory including the axiom of choice. Statement ZF stands for Zermelo–Fraenkel set theory, and DC for the axiom of dependent choice. Solovay's theorem is as follows. Assuming the existence of an inaccessible cardinal, there is an inner model of ZF + DC of a suitable forcing extension ''V'' 'G''such that every set of reals is Lebesgue measurable, has the perfect set property, and has the Baire property. Construction ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solovay–Strassen Primality Test
The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi pseudoprime test. Concepts Euler proved that for any odd prime number ''p'' and any integer ''a'', :a^ \equiv \left(\frac\right) \pmod p where \left(\tfrac\right) is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to \left(\tfrac\right), where ''n'' can be any odd integer. The Jacobi symbol can be computed in time O((log ''n'')²) using Jacobi's generalization of the law of quadratic reciprocity. G ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solovay–Kitaev Theorem
In quantum information and computation, the Solovay–Kitaev theorem says, roughly, that if a set of single-qubit quantum gates generates a dense subset of SU(2), then that set can be used to approximate any desired quantum gate with a relatively short sequence of gates. This theorem is considered one of the most significant results in the field of quantum computation and was first announced by Robert M. Solovay in 1995 and independently proven by Alexei Kitaev in 1997. Michael Nielsen and Christopher M. Dawson have noted its importance in the field. A consequence of this theorem is that a quantum circuit of m constant-qubit gates can be approximated to \varepsilon error (in operator norm) by a quantum circuit of O(m\log^c(m/\varepsilon)) gates from a desired finite universal gate set. By comparison, just knowing that a gate set is universal only implies that constant-qubit gates can be approximated by a finite circuit from the gate set, with no bound on its length. So, the Solova ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zero Sharp
In the mathematical discipline of set theory, 0# (zero sharp, also 0#) is the set of true formulae about indiscernibles and order-indiscernibles in the Gödel constructible universe. It is often encoded as a subset of the integers (using Gödel numbering), or as a subset of the hereditarily finite sets, or as a real number. Its existence is unprovable in ZFC, the standard form of axiomatic set theory, but follows from a suitable large cardinal axiom. It was first introduced as a set of formulae in Silver's 1966 thesis, later published as , where it was denoted by Σ, and rediscovered by , who considered it as a subset of the natural numbers and introduced the notation O# (with a capital letter O; this later changed to the numeral '0'). Roughly speaking, if 0# exists then the universe ''V'' of sets is much larger than the universe ''L'' of constructible sets, while if it does not exist then the universe of all sets is closely approximated by the constructible sets. Definition ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Martin's Axiom
In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consistent with ZFC and the negation of the continuum hypothesis. Informally, it says that all cardinals less than the cardinality of the continuum, \mathfrak c, behave roughly like \aleph_0. The intuition behind this can be understood by studying the proof of the Rasiowa–Sikorski lemma. It is a principle that is used to control certain forcing arguments. Statement For any cardinal 𝛋, we define a statement, denoted by MA(𝛋): For any partial order ''P'' satisfying the countable chain condition (hereafter ccc) and any family ''D'' of dense sets in ''P'' such that '', D, '' ≤ 𝛋, there is a filter ''F'' on ''P'' such that ''F'' ∩ ''d'' is non-empty for every ''d'' in ''D''. \operatorname(\aleph_0) is simply true — this is known ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zero Sharp
In the mathematical discipline of set theory, 0# (zero sharp, also 0#) is the set of true formulae about indiscernibles and order-indiscernibles in the Gödel constructible universe. It is often encoded as a subset of the integers (using Gödel numbering), or as a subset of the hereditarily finite sets, or as a real number. Its existence is unprovable in ZFC, the standard form of axiomatic set theory, but follows from a suitable large cardinal axiom. It was first introduced as a set of formulae in Silver's 1966 thesis, later published as , where it was denoted by Σ, and rediscovered by , who considered it as a subset of the natural numbers and introduced the notation O# (with a capital letter O; this later changed to the numeral '0'). Roughly speaking, if 0# exists then the universe ''V'' of sets is much larger than the universe ''L'' of constructible sets, while if it does not exist then the universe of all sets is closely approximated by the constructible sets. Definition ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Paris Kanellakis Award
The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It was instituted in 1996, in memory of Paris C. Kanellakis, a computer scientist who died with his immediate family in an airplane crash in South America in 1995 (American Airlines Flight 965). The award is accompanied by a prize of $10,000 and is endowed by contributions from Kanellakis's parents, with additional financial support provided by four ACM Special Interest Groups (SIGACT, SIGDA, SIGMOD, and SIGPLAN), the ACM SIG Projects Fund, and individual contributions. Winners See also * List of computer science awards This list of computer science awards is an index to articles on notable awards related to computer science. It includes lists of awards by the Association for Computing Machinery, the Institute of Electrical and Electronic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Measurable Cardinal
In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure on a cardinal , or more generally on any set. For a cardinal , it can be described as a subdivision of all of its subsets into large and small sets such that itself is large, and all singletons are small, complements of small sets are large and vice versa. The intersection of fewer than large sets is again large. It turns out that uncountable cardinals endowed with a two-valued measure are large cardinals whose existence cannot be proved from ZFC. The concept of a measurable cardinal was introduced by Stanislaw Ulam in 1930. Definition Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of ''κ''. (Here the term ''κ-additive'' means that, for any sequence ''A''''α'', α<λ of cardinality '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lebesgue Measurable
In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called ''n''-dimensional volume, ''n''-volume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set ''A'' is here denoted by ''λ''(''A''). Henri Lebesgue described this measure in the year 1901, followed the next year by his description of the Lebesgue integral. Both were published as part of his dissertation in 1902. Definition For any interval I = ,b/math>, or I = (a, b), in the set \mathbb of real numbers, let \ell(I)= b - a denote its length. For any subset E\subseteq\mathbb, the Lebesgue oute ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stationary Set
In mathematics, specifically set theory and model theory, a stationary set is a set that is not too small in the sense that it intersects all club sets, and is analogous to a set of non-zero measure in measure theory. There are at least three closely related notions of stationary set, depending on whether one is looking at subsets of an ordinal, or subsets of something of given cardinality, or a powerset. Classical notion If \kappa is a cardinal of uncountable cofinality, S \subseteq \kappa, and S intersects every club set in \kappa, then S is called a stationary set.Jech (2003) p.91 If a set is not stationary, then it is called a thin set. This notion should not be confused with the notion of a thin set in number theory. If S is a stationary set and C is a club set, then their intersection S \cap C is also stationary. This is because if D is any club set, then C \cap D is a club set, thus (S \cap C) \cap D = S \cap (C \cap D) is non empty. Therefore, (S \cap C) must be stati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Saunders Mac Lane
Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg. Early life and education Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftville.. He was christened "Leslie Saunders MacLane", but "Leslie" fell into disuse because his parents, Donald MacLane and Winifred Saunders, came to dislike it. He began inserting a space into his surname because his first wife found it difficult to type the name without a space. He was the oldest of three brothers; one of his brothers, Gerald MacLane, also became a mathematics professor at Rice University and Purdue University. Another sister died as a baby. His father and grandfather were both ministers; his grandfather had been a Presbyterian, but was kicked out of the church for believing in evolution, and his father was a Congregationalist. His mother, Winifred, studied at Mount Holyoke College and taught English, Latin, and mathematics. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
