# Why is every finite set Diophantine?

I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member against any input to determine set membership....

...However, it isn't clear to me how there is an analog to this method in the domain of Diophantine representation, even though Matiyasevich's theorem assures us that one does exist. (That is, a set is recursively enumerable iff it is Diophantine. Every finite set is recursively enumerable, thus also Diophantine.)

In your answer, please give the explicit method by which any finite set can be written in a Diophantine representation.

-
If what you're mystified about is how to write down a recursively enumerable set using a Diophantine equation, shouldn't you be asking a more general question about how to do that instead? –  Qiaochu Yuan Jan 22 '10 at 0:05
Forgive me - but that is precisely what I asked. Writing down such a method is both necessary and sufficient for showing that such a method exists. –  Xander Raymond Jan 22 '10 at 3:11
Yes, but the methods described in the answers don't require any knowledge of the work around Matiyasevich's theorem. (Also, to nitpick, it is not generally necessary to write something down to show it exists.) –  Qiaochu Yuan Jan 22 '10 at 11:52

Or, very simply stated, given the finite set $S = \{a_1, \dots , a_k\}$, consider the diophantine equation: $$(n-a_1)\dots(n-a_k)=0.$$ EDIT: Then we can write S as $\{ \ n \ | \ \exists x : (n-a_1)\dots(n-a_k)=0\ \}$. (Thanks David)

-
It might be easier to think about this if it were phrased as,"the set of x such that there exists a y such that (x-a_1)...(x-a_n)=0." That is to say, the variable x is being treated as a parameter, not as the variable of the Diophantine equation. –  David Speyer Jan 21 '10 at 23:00
Polynomial equations are special case of Diophantine equations, i.e. there is not need for the quantified x. –  Kaveh Apr 5 '13 at 2:24

If $k\geq0$ and $f$ is a polynomial in $k+1$ variables with integer coefficients, let $$X(f)=\{n\in\mathbb Z:\exists x_1,\dots,x_k\in\mathbb Z:f(n,x_1,\dots,x_k)=0\}.$$ This is the typical diophantine subset of $\mathbb Z$.

Clearly $X(f)\cup X(g)=X(h)$ with $h(n,x_1,\dots x_{k+l})=f(n,x_1,\dots,x_k)g(n,x_{k+1},\dots,x_{k+l})$. It follows that a finite union of diophantine subsets of $\mathbb Z$ is diophantine. It follows that to show that a finite set is diophantine, then, it suffices to check that for all $a\in\mathbb Z$ the set $\{a\}$ is diophantine.

Let then $a\in\mathbb Z$ and let $f(n)=n-a$. Then obviously $\{a\}=X(f)$.

-