[FOM] My personal experience with LEM
Martin Davis
martin at eipye.com
Fri Oct 14 17:26:48 EDT 2005
In my dissertation of 1950 I proved the following:
There exists a Diophantine set of natural numbers whose complement is not
Diophantine.
[A set of natural numbers is Diophantine if it is the set of values of the
parameter r for which some polynomial equation p(r,x1,...,xm)=0 has
solutions in natural numbers.]
It's easy to see that the existence of such a set follows from the
existence of a Diophantine set of n-tuples with this same property. To
prove that this last is true I noted that, otherwise, the class of such
sets being closed under existential quantification (=projection) would
therefore also be closed under universal quantification and hence include
all arithmetic relations. Since Diophantine sets are all r.e., this is
impossible because there are arithmetic relations (e.g. complements of r.e.
relations) not r.e.
Noting that this property of not being closed under taking complements was
shared by the two classes of r.e. and of Diophantine sets, I was encouraged
by this blatantly non-constructive proof to conjecture that the two classes
were one and the same. A proof of this conjecture, and hence a constructive
proof of my theorem as an immediate corollary, had to wait 20 years for
Yuri Matiyasevich to produce the crucial final step culminating an effort
by Hilary Putnam, Julia Robinson, and myself.
Martin
More information about the FOM
mailing list