Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question
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

2 Answers 2

up vote 9 down vote accepted

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)

share|cite|improve this answer
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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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