Diophantine sets 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.
 A: 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."
