{{Short description|American mathematician (born 1938)}} {{redirect|Solovay|alleged internet "Spam King"|Robert Soloway||Soloway (disambiguation)}}

{{Infobox scientist | name = Robert M. Solovay | image = Robert solovay.jpg | image_size = 200px | caption = Robert Solovay in 1993 (photo by George Bergman) | birth_date = {{Birth date and age|1938|12|15|mf=y}} | birth_place = Brooklyn, New York, U.S. | death_date = | death_place = | fields = Mathematics | workplaces = University of California, Berkeley | alma_mater = University of Chicago | doctoral_advisor = Saunders Mac Lane | doctoral_students = Ken McAloon<br>Matthew Foreman<br>Judith Roitman<br>Betül Tanbay<br>W. Hugh Woodin | known_for = Solovay model<br>Solovay–Strassen primality test<br>Zero sharp<br>Martin's axiom<br>Solovay–Kitaev theorem | awards = Paris Kanellakis Award {{small|(2003)}} }} '''Robert Martin Solovay''' (born December 15, 1938) is an American mathematician working 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''.<ref>{{MathGenealogy|id=6522}}</ref> Solovay has spent his career at the University of California at Berkeley, where his Ph.D. students include W. Hugh Woodin and Matthew Foreman.<ref>{{Cite web|url=https://math.berkeley.edu/people/faculty/robert-m-solovay|title=Robert M. Solovay &#124; Department of Mathematics at University of California Berkeley}}</ref>

==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<sup>#</sup>; * Proving that the existence of a real-valued measurable cardinal is equiconsistent with the existence of a measurable cardinal; * Proving that if <math>\lambda</math> is a strong limit singular cardinal, greater than a strongly compact cardinal then <math>2^\lambda=\lambda^+</math> holds; * Proving that if <math>\kappa</math> is an uncountable regular cardinal, and <math>S\subseteq\kappa</math> is a stationary set, then <math>S</math> can be decomposed into the union of <math>\kappa</math> disjoint stationary sets; * With Stanley Tennenbaum, 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 with arbitrarily large cardinality of the continuum; * Outside of set theory, developing (with Volker Strassen) the Solovay–Strassen primality test, used to identify large natural numbers that are prime with high probability. This method has had implications for cryptography; *Regarding the P versus NP problem, he proved with T. P. Baker and J. Gill that relativizing arguments cannot prove <math>\mathrm{P} \neq \mathrm{NP}</math>.<ref>{{Cite journal|date=1994-10-10|title=Relativizations of the P=?NP question over the reals (and other ordered rings)|journal=Theoretical Computer Science|language=en|volume=133|issue=1|pages=15–22|doi=10.1016/0304-3975(94)00068-9|issn=0304-3975|last1 = Emerson|first1 = T.|doi-access=free}}</ref> * Proving that GL (the normal modal logic which has the instances of the schema <math>\Box(\Box A\to A)\to\Box A</math> as additional axioms) completely axiomatizes the logic of the provability predicate of Peano arithmetic; * With Alexei Kitaev, 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.

== Selected publications == * {{cite journal|doi=10.2307/1970696|author=Solovay, Robert M.|title=A model of set-theory in which every set of reals is Lebesgue measurable|journal=Annals of Mathematics |series=Second Series|volume=92|issue=1|year=1970|pages=1–56|jstor=1970696}} * {{cite journal|author=Solovay, Robert M.|title=A nonconstructible ''Δ<sup>1</sup><sub>3</sub>'' set of integers|journal=Transactions of the American Mathematical Society|volume=127|year=1967|pages=50–75|doi=10.2307/1994631|issue=1|publisher=American Mathematical Society|jstor=1994631}} * {{cite journal|author=Solovay, Robert M. and Volker Strassen|journal=SIAM Journal on Computing|title=A fast Monte-Carlo test for primality|volume=6|year=1977|issue=1|pages=84–85|doi=10.1137/0206006}}

== See also == * Provability logic

== References == {{reflist}}

== External links == * {{MathGenealogy|id=6522}} * {{DBLP|name=Robert Solovay}}

{{Kanellakis Award laureates}}

{{Authority control}}

{{DEFAULTSORT:Solovay, Robert M.}} Category:American logicians Category:Members of the United States National Academy of Sciences Category:20th-century American mathematicians Category:Set theorists Category:1938 births Category:Living people Category:University of Chicago alumni Category:University of California, Berkeley faculty