Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure${\cal S}$, there exists a countable field${\cal F}$of arbitrary characteristic with the same essential computable-model-theoretic properties as${\cal S}$. Along the way, we develop a new “computable category theory”, and prove that our functor and (...) its partially defined inverse are computable functors. (shrink)

This paper surveys the recent developments in the area that grew out of attempts to solve an analog of Hilbert's Tenth Problem for the field of rational numbers and the rings of integers of number fields. It is based on a plenary talk the author gave at the annual North American meeting of ASL at the University of Notre Dame in May of 2009.

It is shown that for any computable field K and any r.e. degree a there is an r.e. set A of degree a and a field F ≅ K with underlying set A such that the field operations of F (including subtraction and division) are extendible to (total) recursive functions. Further, it is shown that if a and b are r.e. degrees with b ≤ a, there is a 1-1 recursive function $f: \mathbb{Q} \rightarrow \omega$ such that f(Q) ∈ a, (...) f(Z) ∈ b, and the images of the field operations of Q under f can be extended to recursive functions. (shrink)

This paper provides the first examples of rings of algebraic numbers containing the rings of algebraic integers of the infinite algebraic extensions of where Hilbert's Tenth Problem is undecidable.

We show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same "expressive power" and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomophy rings of Q.

We show that elliptic curves whose Mordell–Weil groups are finitely generated over some infinite extensions of ${\mathbb {Q}}$ , can be used to show the Diophantine undecidability of the rings of integers and bigger rings contained in some infinite extensions of rational numbers.

Let F be a finitely generated field and let j : F → N be a weak presentation of F, i.e. an isomorphism from F onto a field whose universe is a subset of N and such that all the field operations are extendible to total recursive functions. Then if R1 and R2 are recursive subrings of F, for all weak presentations j of F, j is Turing reducible to j if and only if there exists a finite collection of (...) non-constant rational functions {Gi} over F such that for every x ε R1 for some i, Gi ε R2. We investigate under what circumstances such a collection of rational functions exists and conclude that in the case when R1 R2 are both holomorphy rings and F is of characteristic 0 or is an algebraic function field over a perfect field of constants, the existence of the above-described collection of rational functions is equivalent to the requirement that the non-archimedean primes which do not appear as poles of elements of R2 do not have factors of relative degree 1 in some simple extension of K. (shrink)

Let K be a computable field. Let F be a collection of recursive functions over K, possibly including field operations. We investigate the following question. Given an r.e. degree a, is there an injective map j: K $\longrightarrow \mathbb{N}$ such that j(K) is of degree a and all the functions in F are translated by restrictions of total recursive functions.

We show that a solution to Hilbert’s Tenth Problem in the rings of algebraic integers and bigger subrings of number fields where it is currently not known, is equivalent to a problem of bounding archimedean valuations over non-real number fields.

We investigate the issues of Diophantine definability over the non-finitely generated version of non-degenerate modules contained in the infinite algebraic extensions of the rational numbers. In particular, we show the following. Let k be a number field and let K inf be a normal algebraic, possibly infinite, extension of k such that k has a normal extension L linearly disjoint from K inf over k. Assume L is totally real and K inf is totally complex. Let M inf be a (...) non-degenerate O k -module, possibly non-finitely generated and contained in O Kinf . Then M inf contains a submodule M¯ inf such that M inf /M¯ inf is torsion and O k has a Diophantine definition over M¯ inf. (shrink)

We consider the problem of constructing first-order definitions in the language of rings of holomorphy rings of one-variable function fields of characteristic 0 in their integral closures in finite extensions of their fraction fields and in bigger holomorphy subrings of their fraction fields. This line of questions is motivated by similar existential definability results over global fields and related questions of Diophantine decidability.

One of the main theorems of the paper states the following. Let R-K-M be finite extensions of a rational one variable function field R over a finite field of constants. Let S be a finite set of valuations of K. Then the ring of elements of K having no poles outside S has a Diophantine definition over its integral closure in M.

Let K be a function field of one variable over a constant field C of finite transcendence degree over C. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K. Then there exists a set W' of K-primes such that Hilbert's Tenth Problem is not decidable over $O_{K,W'} = \{x \in K\mid ord_\mathfrak{p} x \geq 0, \forall\mathfrak{p} \notin W'\}$ (...) , and the set (W' $\backslash$ W) ∪ (W $\backslash$ W') is finite. Let K be a function field of one variable over a constant field C finitely generated over Q. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K and the degree of all the primes in W is bounded by b ∈ N. Then there exists a set W' of K-primes such that Z has a Diophantine definition over O K ,W', and the set (W' $\backslash$ W) ∪ (W $\backslash$ W') is finite. (shrink)

Let K be a countable field. Then a weak presentation of K is an isomorphism of K onto a field whose elements are natural numbers, such that all the field operations are extendible to total recursive functions. Given a pair of two non-finitely generated countable fields contained in some overfield, we investigate under what circumstances the overfield has a weak presentation under which the given fields have images of arbitrary Turing degrees or, in other words, we investigate Turing separability of (...) various pairs of non-finitely generated fields. (shrink)