Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
Unexciting!?!?! Says you! – Quinn Culver Feb 15 '13 at 19:12

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.