[FOM] My personal experience with LEM

[Martin Davis]

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