From Wikipedia, the free encyclopedia
American mathematician (born 1938)
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 .
[1] Solovay has spent his career at the
University of California at Berkeley , where his Ph.D. students include
W. Hugh Woodin and
Matthew Foreman .
[2]
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
λ
{\displaystyle \lambda }
is a strong limit
singular cardinal , greater than a
strongly compact cardinal then
2
λ
=
λ
+
{\displaystyle 2^{\lambda }=\lambda ^{+}}
holds;
Proving that if
κ
{\displaystyle \kappa }
is an uncountable regular cardinal, and
S
⊆
κ
{\displaystyle S\subseteq \kappa }
is a
stationary set , then
S
{\displaystyle S}
can be decomposed into the union of
κ
{\displaystyle \kappa }
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
P
≠
N
P
{\displaystyle \mathrm {P} \neq \mathrm {NP} }
.
[3]
Proving that GL (the
normal modal logic which has the instances of the schema
◻
(
◻
A
→
A
)
→
◻
A
{\displaystyle \Box (\Box A\to A)\to \Box A}
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
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.
doi :
10.2307/1970696 .
JSTOR
1970696 .
Solovay, Robert M. (1967). "A nonconstructible Δ1 3 set of integers". Transactions of the American Mathematical Society . 127 (1). American Mathematical Society: 50–75.
doi :
10.2307/1994631 .
JSTOR
1994631 .
Solovay, Robert M. and Volker Strassen (1977). "A fast Monte-Carlo test for primality". SIAM Journal on Computing . 6 (1): 84–85.
doi :
10.1137/0206006 .
See also
References
External links
Adleman ,
Diffie ,
Hellman ,
Merkle ,
Rivest ,
Shamir (1996)
Lempel ,
Ziv (1997)
Bryant ,
Clarke ,
Emerson ,
McMillan (1998)
Sleator ,
Tarjan (1999)
Karmarkar (2000)
Myers (2001)
Franaszek (2002)
Miller ,
Rabin ,
Solovay ,
Strassen (2003)
Freund ,
Schapire (2004)
Holzmann ,
Kurshan ,
Vardi ,
Wolper (2005)
Brayton (2006)
Buchberger (2007)
Cortes ,
Vapnik (2008)
Bellare ,
Rogaway (2009)
Mehlhorn (2010)
Samet (2011)
Broder ,
Charikar ,
Indyk (2012)
Blumofe ,
Leiserson (2013)
Demmel (2014)
Luby (2015)
Fiat ,
Naor (2016)
Shenker (2017)
Pevzner (2018)
Alon ,
Gibbons ,
Matias ,
Szegedy (2019)
Azar ,
Broder ,
Karlin ,
Mitzenmacher ,
Upfal (2020)
Blum ,
Dinur ,
Dwork ,
McSherry ,
Nissim ,
Smith (2021)
Burrows ,
Ferragina ,
Manzini (2022)
International National Academics