# What specifically is wrong with this naive approach to solve Hilbert's 10th problem over the rationals?

By MDPR, c.e. sets are the same as Diophantine sets. An existential definition of $$\Bbb Z$$ in $$\Bbb Q$$ would solve Hilbert's 10th problem over $$\Bbb Q$$.

The idea is not so crazy, you just input a pair $$(a,b)$$ of integers (I guess a pair of pairs of naturals, but that's a detail) and if $$b \vert a$$ you halt and if it doesn't you run forever. So the pairs $$(a,b)$$ for which the algorithm halts are rational numbers that are actually integers and if it doesn't they're rational numbers that are not integers.

N.B. This is so simple I know I cannot be correct. Many people much more experienced than me have tried and failed with many more complicated methods. This is more of a request to explain why this is wrong.

What I am guessing could be my incorrect assumption:

1. You can just give an algorithm that distinguishes between integers and rationals and by MDPR the c.e. set this algorithm produces is a Diophantine set and hence a Diophantine definition of $$\Bbb Z$$ in $$\Bbb Q$$.
2. You can sneak the integers into my algorithm by defining rationals as pairs of integers and not worry about circularity.

If I understand your idea correctly, you're not actually defining $$\mathbb{Z}$$ in $$\mathbb{Q}$$. You're defining $$\mathbb{Z}$$ in a structure $$\tilde{\mathbb{Q}}$$, which intuitively consists of $$\mathbb{Q}$$ together with the details of its construction via ordered pairs of integers. This is unavoidable when you try to check whether $$a\vert b$$ in a rational $$q=(a,b)$$: you need to be able to first "unpack" the rational into an ordered pair, and second check whether there is an integer (not a rational) which when multiplied by the left coordinate yields the right coordinate.

Now this absolutely works, but it doesn't help define $$\mathbb{Z}$$ in $$\mathbb{Q}$$ at all, let alone in a $$\Sigma_1$$ way. The structure $$\tilde{\mathbb{Q}}$$ is, when we dive into the details, $$\mathbb{Z}$$ itself (or perhaps more accurately, $$\mathbb{Z}$$ together with some inessentialy "syntactic sugar")! And an existential definition of $$\mathbb{Z}$$ in $$\mathbb{Z}$$ isn't very surprising.

It may help at this point to look at a context where we know such an idea must fail - for example, the field $$\overline{\mathbb{Q}}\cap\mathbb{R}$$ of algebraic real numbers. As a real closed field this is decidable, and so cannot define $$\mathbb{Z}$$ at all, but it can be implemented in $$\mathbb{Z}$$ in a manner similar to the implementation of rationals as (equivalence classes of) ordered pairs of integers.

I think the source of this confusion is a reflexive identification of computations with $$\Sigma_1$$-definitions. The fact that we can do this over $$\mathbb{Z}$$ (or similar) is a highly nontrivial property of $$\mathbb{Z}$$, and we're not guaranteed anything similar about $$\mathbb{Q}$$; in fact, this is essentially what you're trying to prove in the first place!

For this reason it's important to grapple with $$\Sigma_1$$ definitions themselves, not intuitive analogues. A $$\Sigma_1$$ definition of $$\mathbb{Z}$$ in $$\mathbb{Q}$$ can't "unpack" an element of $$\mathbb{Q}$$ into some explicit implementation in a different context, nor can it in any way "search" over natural numbers or similar objects.

• So, is it reasonable to say that the method is flawed because of both of my guesses? Both that, by "packing" the rational into the ordered pair $(a,b)$, I am already sneaking $\Bbb Z$ into $\tilde{\Bbb Q}$, and that I am conflating computation with $\Sigma_1$ definition? On the second point, should I then believe that there is no sense in trying to go in this direction, [computation] $\to$ [$\Sigma_1$ definition], unless somehow I truly quantify over "sugar-free" rationals? Feb 10 at 20:04
• @BigSocks Yes, basically. Feb 10 at 20:04
• Awesome, thank you very much for your input and careful analysis of my mistake! Feb 10 at 20:06