From: weemba@sagi.wistar.upenn.edu (Matthew P Wiener)
Newsgroups: sci.math,sci.logic
Subject: Re: Undecidable Diophantine equation
Date: 2 Jun 1998 21:09:16 GMT
In article , tchow@lsa (Timothy Chow) writes:
>People have written down explicit Diophantine polynomial equations whose
>solubility is undecidable in ZFC (assuming ZFC is consistent). I wanted
>to show such an equation to a (non-mathematician) friend of mine, and I
>thought I had saved a copy somewhere but I can't find it. Could someone
>please email me an example (or a reference)? In view of the audience,
>the simpler the example the better.
J P Jones "Undecidable Diaphontine Equations" BULL AMS (NS), v3, pp
859-862, 1980.
J P Jones "Universal Diaphontine Equation" JOUR SYMB LOGIC v47, pp
549-571, 1982.
My memory is clear only regarding the explicit universal equation
being written out (in the BAMS announcement). It is an equation of
the form P(a,b,c,d,...,y,z)=0 such that by choosing a,b,c (to A,B,C,
say), one has the sets { z | (E d,e...y) P(A,B,C,d,e,...,y,z)=0 }
ranging over precisely the recursively enumerable sets.
Obviously, for certain choices of a,b,c, then, one has an undecidable
Diaphontine equation. I do not recall if Jones did this last step
explicitly or not.
--
-Matthew P Wiener (weemba@sagi.wistar.upenn.edu)