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

Download Edit this record How to cite View on PhilPapers
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.
Categories
PhilPapers/Archive ID
PESOSR
Revision history
First archival date: 2019-04-15
Latest version: 16 (2019-09-11)
View upload history
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Added to PP index
2019-04-15

Total views
105 ( #29,834 of 46,438 )

Recent downloads (6 months)
67 ( #11,112 of 46,438 )

How can I increase my downloads?

Downloads since first upload
This graph includes both downloads from PhilArchive and clicks to external links.