# Recursively enumerable sets

How can we show that any diophantine set is recursively enumerable?

To be r.e., we require that the characteristic function is recursive and thus we require set to be decidable.

Only thing hat may be helpful is the parametrization theorem, but not sure how.

-
Have you read the wiki article on Diophantine sets? –  JSchlather Feb 14 '13 at 23:31
This article proves the reverse of what I want. –  Buddy Holly Feb 14 '13 at 23:33
The decidable nature of candidate solutions to diophantine equations is pretty obvious. Do the arithmetic! –  hardmath Feb 14 '13 at 23:37
how is it obvious? If we alter the field then? –  Buddy Holly Feb 15 '13 at 9:12
My apologies if the tone of my remark did not come across with the light humor intended. The arithmetic "field" is always integer arithmetic with diophantine set definitions, so systematically evaluating an integer polynomial $P(\overline{x},\overline{y})$ for all candidate solutions will effectively enumerate the associated set. I was in the midst of writing an Answer when I saw Peter Smith had done a nice one. –  hardmath Feb 15 '13 at 16:13

A set $S \subset \mathbb{N}$ is Diophantine if there is an $k + 1$ polynomial $P$ such that $n \in S$ iff for some $k$-tuple $\vec{m}$, $P(n, \vec{m}) = 0$.

Suppose $S$ is Diophantine, generated by the $k+1$ polynomial $P$. Take $k+1$ tuples in turn (zig-zag through them so each is reached in a finite number of steps) and test to see whether of not they satisfy the given Diophantine condition: output the first element of the successful tuples. That's an algorithmic procedure. So, voilà, the Diophantine set can be effectively enumerated. So, by a labour-saving appeal to Church's Thesis, it is recursively enumerable. It is as unexciting as that.

-
Unexciting!?!?! Says you! –  Quinn Culver Feb 15 '13 at 19:12