Processing math: 100%

Logic Seminar

Russell MillerQueens College and CUNY Graduate Center
Hilbert's tenth problem for subrings of the rationals

Tuesday, August 22, 2017 - 2:55pm
Malott 206

For a ring R, Hilbert’s Tenth Problem is the set HTP(R) of polynomials fR[X1,X2,] for which f=0 has a solution in R. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that HTP(Z) is Turing-equivalent to the Halting Problem. The Turing degree of HTP(Q) remains unknown. Here we consider the problem for subrings of Q. One places a natural topology on the space of such subrings, which is homeomorphic to Cantor space. This allows consideration of measure theory and also Baire category theory. We prove, among other things, that HTP(Q) computes the Halting Problem if and only if HTP(R) computes it for a nonmeager set of subrings R. We also draw parallels and make distinctions between the jump operator and the operator HTP, which maps an element of Cantor space to the the HTP of the corresponding subring of Q.