HOME

TheInfoList



OR:

Robert Martin Solovay (born December 15, 1938) is an American
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History O ...
specializing in
set theory 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 concer ...
.


Biography

Solovay earned his
Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...
from the
University of Chicago The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park neighborhood. The University of Chicago is consistently ranked among the be ...
in 1964 under the direction of
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 ...
, with a dissertation on ''A Functorial Form of the Differentiable
Riemann–Roch theorem The Riemann–Roch theorem is an important theorem in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeros and allowed poles. It re ...
''. Solovay has spent his career at the
University of California at Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant univ ...
, 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 In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum of ...
, then the statement "every set of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every r ...
s is
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 w ...
" is consistent with
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such a ...
without the
axiom of choice In mathematics, the axiom of choice, or AC, 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 ...
; * Isolating the notion of 0#; * Proving that the existence of a real-valued measurable cardinal is
equiconsistent In mathematical logic, two theories are equiconsistent if the consistency of one theory implies the consistency of the other theory, and vice versa. In this case, they are, roughly speaking, "as consistent as each other". In general, it is not p ...
with the existence of a measurable cardinal; * Proving that if \lambda is a strong limit
singular cardinal Singular may refer to: * Singular, the grammatical number that denotes a unit quantity, as opposed to the plural and other forms * Singular homology * SINGULAR, an open source Computer Algebra System (CAS) * Singular or sounder, a group of boar, s ...
, greater than a
strongly compact cardinal In set theory, a branch of mathematics, a strongly compact cardinal is a certain kind of large cardinal. A cardinal κ is strongly compact if and only if every κ-complete filter can be extended to a κ-complete ultrafilter. Strongly compact cardi ...
then 2^\lambda=\lambda^+ holds; * Proving that if \kappa is an uncountable regular cardinal, and S\subseteq\kappa is a
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 close ...
, then S can be decomposed into the union of \kappa disjoint stationary sets; * With
Stanley Tennenbaum Stanley Tennenbaum (April 11, 1927 – May 4, 2005) was an American mathematician who contributed to the field of logic. In 1959, he published Tennenbaum's theorem, which states that no countable nonstandard model of Peano arithmetic (PA) can be r ...
, developing the method of iterated forcing and showing the consistency of Suslin's hypothesis; * With Donald A. Martin, showed the consistency of
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 consi ...
with arbitrarily large
cardinality of the continuum In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \mathb ...
; * Outside of set theory, developing (with
Volker Strassen Volker Strassen (born April 29, 1936) is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of Konstanz. For important contributions to the analysis of algorithms he has received many aw ...
) the
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 ...
, used to identify large
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
s that are
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
with high
probability Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
. This method has had implications for
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
; *Regarding the
P versus NP problem The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...
, he proved with T. P. Baker and J. Gill that relativizing arguments cannot prove \mathrm \neq \mathrm. * Proving that GL (the
normal modal logic In logic, a normal modal logic is a set ''L'' of modal formulas such that ''L'' contains: * All propositional tautologies; * All instances of the Kripke schema: \Box(A\to B)\to(\Box A\to\Box B) and it is closed under: * Detachment rule (''modus po ...
which has the instances of the schema \Box(\Box A\to A)\to\Box A as additional axioms) completely axiomatizes the logic of the provability predicate of
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
; * With Alexei Kitaev, proving that a finite set of
quantum gate In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, lik ...
s can efficiently approximate an arbitrary
unitary operator In functional analysis, a unitary operator is a surjective bounded operator on a Hilbert space that preserves the inner product. Unitary operators are usually taken as operating ''on'' a Hilbert space, but the same notion serves to define the co ...
on one
qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
in what is now known as Solovay–Kitaev theorem.


Selected publications

* * *


See also

*
Provability logic Provability logic is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'. The point is to capture the notion of a proof predicate of a reasonably rich formal theory, such as Peano arithmetic. Examples ...


References


External links

* * {{DEFAULTSORT:Solovay, Robert M. American logicians Members of the United States National Academy of Sciences 20th-century American mathematicians Set theorists 1938 births Living people