Hilbert's 10th Problem for solutions in a subring of Q


Authors
Abstract
Yuri Matiyasevich's theorem states that the set of all Diophantine equations which have a solution in non-negative integers is not recursive. Craig Smoryński's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. Let R be a subring of Q with or without 1. By H_{10}(R), we denote the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide whether or not the equation has a solution in R. We prove that a positive solution to H_{10}(R) implies that the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable. We show the converse implication for every infinite set R \subseteq Q such that there exist computable functions \tau_1,\tau_2:N \to Z which satisfy (\forall n \in N \tau_2(n) \neq 0) \wedge ({\frac{\tau_1(n)}{\tau_2(n)}: n \in N}=R). This implication for R=N guarantees that Smoryński's theorem follows from Matiyasevich's theorem. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have a rational solution is not recursive. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have only finitely many rational solutions is not recursively enumerable. These conjectures are equivalent by our results for R=Q.
Keywords Craig Smorynski's theorem  Diophantine equation which has at most finitely many solutions  Hilbert's 10th Problem for solutions in a subring of Q  Martin Davis' theorem  recursive set  recursively enumerable set  Yuri Matiyasevich's theorem
Categories No categories specified
(categorize this paper)
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Recursive Enumerability with Finite Repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
On Recursive Enumerability with Finite Repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
A Non-Splitting Theorem for D.R.E. Sets.Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (1):17-96.
Hilbert's Tenth Problem for Rings of Rational Functions.Karim Zahidi - 2002 - Notre Dame Journal of Formal Logic 43 (3):181-192.
Existential Arithmetization of Diophantine Equations.Yuri Matiyasevich - 2009 - Annals of Pure and Applied Logic 157 (2-3):225-233.
The Translation Theorem.Peter Cholak - 1994 - Archive for Mathematical Logic 33 (2):87-108.
Effective Nonrecursiveness.Takeshi Yamaguchi - 1997 - Mathematical Logic Quarterly 43 (1):45-48.
A Note on a Theorem of Ax.Piotr Kowalski - 2008 - Annals of Pure and Applied Logic 156 (1):96-109.

Analytics

Added to PP index
2019-04-15

Total views
107 ( #81,194 of 2,289,446 )

Recent downloads (6 months)
53 ( #15,799 of 2,289,446 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature