3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – Qiaochu Yuan
    Commented Jan 22, 2010 at 0:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Xander Raymond
    Commented Jan 22, 2010 at 3:11
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Qiaochu Yuan
    Commented Jan 22, 2010 at 11:52

2 Answers 2

Reset to default
10
$\begingroup$

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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Jan 21, 2010 at 23:00
  • $\begingroup$ Polynomial equations are special case of Diophantine equations, i.e. there is not need for the quantified x. $\endgroup$
    – Kaveh
    Commented Apr 5, 2013 at 2:24
7
$\begingroup$

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)$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .