2
$\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.

$\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$ 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$ 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$ Jan 22, 2010 at 11:52

2 Answers 2

9
$\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)

$\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$ 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
    Apr 5, 2013 at 2:24
6
$\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)$.

$\endgroup$

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