1
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – BigSocks
    Feb 10 at 20:04
  • $\begingroup$ @BigSocks Yes, basically. $\endgroup$ Feb 10 at 20:04
  • $\begingroup$ Awesome, thank you very much for your input and careful analysis of my mistake! $\endgroup$
    – BigSocks
    Feb 10 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.