Defining \(\mathbb Z\) in \(\mathbb Q\). (English) Zbl 1390.03032

Koenigsmann, Jochen

Ann. Math. (2) 183, No. 1, 73-93 (2016).

By Matiyasevich’s theorem, a subset \(X\subseteq\mathbb N\) is Diophantine, i.e. expressable in the form \(\{y\in\mathbb N:\exists{\vec x}\in\mathbb N^np(y,\vec x)=0\}\) for some \(n\in\mathbb N\), \(p\in\mathbb Z[\vec x,y]\), if and only if \(X\) is recursively enumerable. Combined with the existence of recursively enumerable sets that are not recursive, this implies the unsolvability of Hilbert’s 10th problem, which asked for a general decision procedure for the solvability of Diophantine equations. On the other hand, it is well-known that the theory of \(\mathbb R\) in the language of ordered rings is decidable.
One of the main open questions suggested by these results is whether the solvability of polynomial equations with rational coefficients in \(\mathbb Q\) is decidable. One way to attack this problem would be to show that \(\mathbb Z\) has a Diophantine definition over \(\mathbb Q\), thus reducing the question to Matiyasevich’s theorem. A more relaxed question is then whether \(\mathbb Z\) is definable over \(\mathbb Q\) at all.
This was answered in the positive by a classical result of J. Robinson [J. Symb. Log. 14, 98–114 (1949; Zbl 0034.00801)], who showed that \(\mathbb Z\) has a \(\Pi_2\)-definition over \(\mathbb Q\). For a negative solution to Hilbert’s 10th problem over \(\mathbb Q\) along the lines sketched above, a \(\Sigma_1\)-definition would be needed.
The present paper brings the complexity considerably down by showing that \(\mathbb Z\) is \(\Pi_1\)-definable over \(\mathbb Q\) (Theorem \(1\)), thus showing that \(\mathbb Q\setminus\mathbb Z\) is Diophantine over \(\mathbb Q\) (Corollary 2) and that the \(\Pi_2\)-theory of \(\mathbb Q\) is undecidable (Corollary 3).
The proof proceeds in four steps: In step 1, a certain \(\Pi_2\)-definition of \(\mathbb Z\) in \(\mathbb Q\) is given by adapting a construction of B. Poonen [Am. J. Math. 131, No. 3, 675–682 (2009; Zbl 1179.11047); Math. Res. Lett. 16, No. 1, 165–170 (2009; Zbl 1183.14031)]. Step 2 consists in proving that the set of rational \(p\)-adic integers is Diophantine in \(\mathbb Q\). Step 3 gives \(\Sigma_1\)-definitions for some Jacobson radicals relevant in step 2. Finally, step 4 uses model-theoretical results to express certain existentially expressed formulas as universal formulas.
The author mentions that the Diophantine subsets of \(\mathbb Q\) obtained in step 2 may lead to a different proof strategy of the undecidability of Hilbert’s 10th problem over \(\mathbb Q\) than the one suggested above and suggests further ways to show that \(\mathbb Z\) is Diophantine in \(\mathbb Q\) in Section 4.
The paper requires a background in algebraic number theory. As its main result is a landmark in the theory of Diophantine equations, it should appeal to logicians, number theorists and recursion theorists.

Reviewer: Merlin Carl (Konstanz)

MSC:

03C40	Interpolation, preservation, definability
03D35	Undecidability and degrees of sets of sentences
11U09	Model theory (number-theoretic aspects)
11U05	Decidability (number-theoretic aspects)
11Dxx	Diophantine equations

Keywords:

Hilbert’s 10th problem; Diophantine equation; definablity; undecidability

Citations:

Zbl 0034.00801; Zbl 1179.11047; Zbl 1183.14031

References:

[1]	J. Colliot-Thélène, D. Coray, and J. Sansuc, ”Descente et principe de Hasse pour certaines variétés rationnelles,” J. reine angew. Math., vol. 320, pp. 150-191, 1980. · Zbl 0434.14019
[2]	J. Colliot-Thélène and J. Van Geel, Le complémentaire des puissances \(n\)-ièmes dans un corps de nombres est un ensemble diophantien, 2014.
[3]	G. Cornelissen and K. Zahidi, ”Elliptic divisibility sequences and undecidable problems about rational points,” J. reine angew. Math., vol. 613, pp. 1-33, 2007. · Zbl 1178.11076
[4]	J. Koenigsmann, ”From \(p\)-rigid elements to valuations (with a Galois-characterization of \(p\)-adic fields),” J. reine angew. Math., vol. 465, pp. 165-182, 1995. · Zbl 0824.12006
[5]	J. Park, ”A universal first-order formula defining the ring of integers in a number field,” Math. Res. Lett., vol. 20, iss. 5, pp. 961-980, 2013. · Zbl 1298.11113
[6]	B. Poonen, ”Characterizing integers among rational numbers with a universal-existential formula,” Amer. J. Math., vol. 131, iss. 3, pp. 675-682, 2009. · Zbl 1179.11047
[7]	B. Poonen, ”The set of nonsquares in a number field is Diophantine,” Math. Res. Lett., vol. 16, iss. 1, pp. 165-170, 2009. · Zbl 1183.14031
[8]	A. Prestel and C. N. Delzell, Mathematical Logic and Model Theory: A Brief Introduction, New York: Springer-Verlag, 2011. · Zbl 1241.03001
[9]	J. Robinson, ”Definability and decision problems in arithmetic,” J. Symbolic Logic, vol. 14, pp. 98-114, 1949. · Zbl 1241.03001
[10]	. J-P. Serre, A Course in Arithmetic, New York: Springer-Verlag, 1973, vol. 7. · Zbl 0256.12001