Submission date: 28 December 2020

Abstract:

The celebrated DPRM theorem by M. Davis, H. Putnam, J. Robinson, and Y. Matiyasevich shows that a set of integers is listable (also called recursively enumerable, or computably enumerable) if and only if it is Diophantine, i.e., positive existentially definable over the language of arithmetic. We present some foundational material to investigate analogues of the DPRM theorem over other structures. This allows us to give rigorous proofs of various folklore results in the literature. In addition, we investigate different conjectures that point in the direction that the analogue of the DPRM theorem for global fields does not hold.

Mathematics Subject Classification: Primary: 11U09, Secondary: 03D45, 11G35, 11J68

Keywords and phrases:

Full text arXiv 2012.14054: pdf, ps.