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

closed as off-topic by quid, Stefan Kohl, Felipe Voloch, Christian Remling, Ilya Bogdanov Oct 25 at 12:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – quid, Stefan Kohl, Felipe Voloch, Christian Remling, Ilya Bogdanov
If this question can be reworded to fit the rules in the help center, please edit the 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

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