I'm trying to show that the following sets are Diophantine:
- $\{(x,y)\mid x \leq y\}$
- $\{(x,y)\mid x < y\}$
- $\{(x,y)\mid x\text{ divides }y\}$
- $\{(x,y,z)\mid x\equiv y \pmod z\}$
- $\{(x,y,z)\mid x = \gcd(y,z)\}$
So, the definition I am using is that a Set $S$ is diophantine if i) it is a subset of $n$ , the set of all $n$-tuples of positive integers, and ii) there is a polynomial $p$ over in $n+k$ variables, $k0$ , such that $x$ is an element of the set $S$ iff there is some y an element of Naturals^k , such that $p(x,y)=0$
So, my answer is that set 1 isn't diophantine since it is not a subset of n, since if we let $y = -2$ for example.
For set 2), it also isn't diophantine by the same reason as in #1
For set 3), it is since we let $k*x = y$, where $k$ is a positive number, but how to take care of the polynomial $p$ over $n+k$ variables?
For set 4, condition 1 is met, but I need some justification
and for set 5, it is also diophantine by the same reason as set 4.
Thanks.
As is traditional in the field, we let variables range over the non-negative integers. The definitions should not be hard to modify if we are restricted to quantification over the positive integers. Note that the answers use polynomial equations $P=0$, where some of the coefficients of $P$ may be negative. If we want to avoid negative coefficients, we can, by bringing all the negative stuff to one side, use $P^+=P^-$.
$1.$ For $x\le y$, use the formula $\exists u(x+u-y=0$. If you really insist on quantifying over positive integers only, say that $x=y$ or there exists a $u$ such that $x+u-y=0$. This can be expressed as $\exists u((x-y)(x+u-y)=0)$.
From here on we don't type the existential quantifiers.
$2.$ For $x\lt y$ use $x+1+u-y=0$. Here if we want $u$ to range over the positive integers, we can use the simpler $x+u-y=0$.
$3.$ For $x$ divides $y$, use $ux=y$.
$4.$ For congruence, there is the annoyance that $x-y$ may be positive, negative, or $0$. We can say that there exists $u$ such that $uz=x-y$ or $uz=y-x$. This can be written as there exists a $u$ such that $(uz-x+y)(uz+x-y)=0$.
$5.$ For gcd, say that $x$ divides $y$ and $x$ divides $z$ (we already know how to do these) and $x$ can be written as a linear combination of $y$ and $z$ (Bezout's Theorem).
To say linear combination, we can't quite say that there are $s$ and $t$ such that $sy+tz=x$, because almost always one of $s$ or $t$ will be negative. But we can sneak around that by saying there exist $s$ and $t$ such that $(sy-tz-x)(sy-tz-x)=0$.
Note that we have three conditions whose conjunction we want to assert. Use the fact that the polynomials $P$, $Q$, and $R$ are all $0$ at a certain place iff $P^2+Q^2+R^2=0$ at that place.
Remark: Your $x$, $y$ and so on implicitly range over the non-negative integers or the positive integers, according to local definition. So your choice of $y=-2$ is not allowed. It turns out that all recursively enumerable sunsets of $\mathbb{N}^n$ are Diophantine, so in particular all of the sets in your list will be. But what is asked for is an explicit construction for each.
Added: For the $\gcd$ predicate, putting the pieces together, a formula that one can use is $$\exists u\exists v\exists s\exists t\left((ux-y)^2 +(vx-z)^2 +((sy-tz-x)(sy-tz-x))^2=0\right).$$ Note again the use of product to say "or" and of sum of squares to say "and."