Diophantine vs. existential definability

Question

We consider the language $\{+,\cdot,0,1\}$ of rings.

I want to understand how terminology is used in the work by J. Koenigsmann, Defining $\mathbb Z$ in $\mathbb Q$, Annals of Mathematics 183 (2016), 73-93.

Koenigsmann uses the words diophantine and existential. Following Wikipedia for diophantine and the text book on Model Theory by Chang and Keisler for existential sentence, I hope that the definitions below are correct. Let $R$ be a ring and $S \subseteq R$ be a subset.

• $S$ is called diophantine in $R$, if there exists a polynomial $f(T,Z_1,\ldots,Z_n)$ with integer coefficients such that $t \in S$ if and only if $\exists z_1,\ldots, z_n \ f(t,z_1,\ldots,z_n) = 0$ for all $t \in R$.

• $S$ is called existential (or existentially definable) in $R$ if there exists a quantifier-free formula $\varphi(T,Z_1,\ldots,Z_n)$ such that $t \in S$ if and only if $\exists z_1,\ldots, z_n \ \varphi(t,z_1,\ldots,z_n) $ for all $t \in R$.

Now I have several questions:

1. Is my definition of existential standard or does one rather use positive sentences $\varphi$?

2. Concerning 1.: Why could it possibly be more sensible to use positive sentences?

3. It seems to me (in particular in view of the first page of the paper and the two paragraphs before Proposition 23) that Koenigsmann is using the terminologies existentially definable and diophantine as synonyms. Is this the case?

4. Concerning 3.: Why would one do this?

5. Are the two definitions equivalent if $R = \mathbb Q$?

6. I think, Hilbert's tenth problem over $\mathbb Q$ could only be solved by showing that $\mathbb Z$ is diophantine in $\mathbb Q$. An existential definition in the sense above would not suffice. Is this true?

Thank you very much in advance!

Answer 1

Your definitions are correct (though your definition of existentially definable has an extraneous "$=0$" at the end of the formula, which I assume is a typo). I think this answers your questions 1 and 2.

In fact, over $\mathbb{Q}$, the two definitions are equivalent. I think this answers your questions 3 through 6.

Claim: A set $S\subseteq \mathbb{Q}$ is diophantine in $\mathbb{Q}$ if and only if it is existentially definable in $\mathbb{Q}$.

Proof: In any ring, a diophantine set is existentially definable. Conversely, let's prove that for every quantifier-free formula $\varphi(T,Z_1,\dots,Z_n)$, there is a polynomial $f_\varphi(T,Z_1,\dots,Z_n,W_1,\dots,W_m)$ with integer coefficients such that $$R\models \varphi(t,z_1,\dots,z_n)\text{ if and only if }R\models \exists w_1\dots w_m (f_\varphi(t,z_1,\dots,z_n,w_1,\dots,w_m) = 0).$$ It follows that $$R\models \exists z_1\dots z_n\,\varphi(t,z_1,\dots,z_n)\text{ if and only if }R\models \exists z_1\dots z_n w_1\dots w_m (f_\varphi(t,z_1,\dots,z_n,w_1,\dots,w_m) = 0).$$

In the statement we're trying to prove, there is no special distinction between the variable $T$ and the variables $Z_i$: $\varphi$ is just a formula in $(n+1)$ free variables, which also appear in the polynomial $f_\varphi$. So let's agree to supress mention of these variables, to ease notation.

We may assume $\varphi$ is written in conjunctive normal form, as a conjunction of disjunctions of atomic and negated atomic formulas. So we will prove the claim in steps, for (1) atomic formulas, (2) negated atomic formulas, (3) disjunctions of atomic and negated atomic formulas, and (4) conjunctions of disjunctions of atomic and negated formulas.

1. If $\varphi$ is an atomic formula, it is an equality between terms $p_1 = p_2$. Then $\varphi$ is equivalent to $p_1 - p_2 = 0$. We conclude by observing that every term in the language of rings is equivalent to a polynomial with integer coefficients (in the same variables).
2. If $\varphi$ is a negated atomic formula, say $\lnot \psi$, then by step 1, $\varphi$ is equivalent to $f_\psi \neq 0$. Since $\mathbb{Q}$ is a field, this is equivalent to the existence of $w$ such that $wf_\psi = 1$. So $\varphi$ is equivalent to $\exists w\,(wf_\psi - 1 = 0)$. This method of turning an inequation into an equation at the expense of adding an extra variable is sometimes called the Rabinowitsch trick.
3. Suppose $\varphi$ is a disjunction $\bigvee_{i=1}^k \psi_i$, where each $\psi_i$ is atomic or negated atomic. By steps 1 and 2, each $\psi_i$ is equivalent to $\exists w\,f_{\psi_i} = 0$ (where $f_{\psi_i}$ does not contain the variable $w$ if $\psi_i$ is atomic). Now the existential quantifier distributes over disjunctions, so we can pull the $\exists w$ to the front. And since $\mathbb{Q}$ is an integral domain, some $f_{\psi_i}$ is $0$ if and only if $\prod_{i=1}^k f_{\psi_i}$ is $0$. So $\varphi$ is equivalent to $\exists w (\prod_{i=1}^k f_{\psi_i} = 0).$
4. Suppose $\varphi$ is a conjunction $\bigwedge_{i=1}^k \psi_i$, where each $\psi_i$ is equivalent to $\exists w_i( f_{\psi_i} = 0)$. Note that here we have used distinct variables $w_i$ for each conjunct, so that we can pull the existential quantifiers out of the conjunction: $\bigwedge_{i=1}^k \exists w_i (f_{\psi_i} = 0)$ is equivalent to $\exists w_1\dots w_k( \bigwedge_{i=1}^k f_{\psi_i} = 0)$. And since a sum of squares $a_1^2+\dots+a_k^2 = 0$ in $\mathbb{Q}$ is $0$ if and only if each $a_i=0$, all $f_{\psi_i}$ are $0$ if and only if $\sum_{i=1}^k (f_{\psi_i})^2$ is $0$. So $\varphi$ is equivalent to $\exists w_1\dots w_k \sum_{i=1}^k (f_{\psi_i})^2 = 0.$

This completes the proof.

Note that step 1 works in any ring, step 2 works in any field, step 3 works in any integral domain, and step 4 works in any formally real field. Thus the full result is true in any formally real field (e.g. any subfield of $\mathbb{R}$). In a general field, an existentially definable set is definable by a system of diophantine equations.

Finally, note that all of the above applies just as well to diophantine / existentially definable sets in $R^n$, not just $R$: in the definitions and the proof, just replace the variable $t$ with a tuple of $n$ variables.