Robert M. Solovay

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;

Solovay's theorem

Isolating the notion of ;

0^#

Proving that the existence of a is equiconsistent with the existence of a measurable cardinal;

real-valued measurable cardinal

Proving that if ${\displaystyle \lambda }$ is a strong limit , greater than a strongly compact cardinal then ${\displaystyle 2^{\lambda }=\lambda ^{+}}$ holds;

singular cardinal

Proving that if ${\displaystyle \kappa }$ is an uncountable regular cardinal, and ${\displaystyle S\subseteq \kappa }$ is a , then ${\displaystyle S}$ can be decomposed into the union of ${\displaystyle \kappa }$ disjoint stationary sets;

stationary set

With , developing the method of iterated forcing and showing the consistency of Suslin's hypothesis;

Stanley Tennenbaum

With , showed the consistency of Martin's axiom with arbitrarily large cardinality of the continuum;

Donald A. Martin

Outside of set theory, developing (with ) the Solovay–Strassen primality test, used to identify large natural numbers that are prime with high probability. This method has had implications for cryptography;

Volker Strassen

Regarding the , he proved with T. P. Baker and J. Gill that relativizing arguments cannot prove ${\displaystyle \mathrm {P} \neq \mathrm {NP} }$.^[3]

P versus NP problem

Proving that GL (the which has the instances of the schema ${\displaystyle \Box (\Box A\to A)\to \Box A}$ as additional axioms) completely axiomatizes the logic of the provability predicate of Peano arithmetic;

normal modal logic

With , proving that a finite set of quantum gates can efficiently approximate an arbitrary unitary operator on one qubit in what is now known as Solovay–Kitaev theorem.

Alexei Kitaev

Solovay, Robert M. (1970). "A model of set-theory in which every set of reals is Lebesgue measurable". Annals of Mathematics. Second Series. 92 (1): 1–56. :10.2307/1970696. JSTOR 1970696.

doi

Solovay, Robert M. (1967). "A nonconstructible Δ¹₃ set of integers". Transactions of the American Mathematical Society. 127 (1). American Mathematical Society: 50–75. :10.2307/1994631. JSTOR 1994631.

doi

Solovay, Robert M. and Volker Strassen (1977). "A fast Monte-Carlo test for primality". SIAM Journal on Computing. 6 (1): 84–85. :10.1137/0206006.

doi

Provability logic

at the Mathematics Genealogy Project

Robert M. Solovay

at DBLP Bibliography Server

Robert Solovay