There are a couple of definitions of recursively enumerable, for example in Judah: $A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0_1$ formula $\varphi(x)$ such that

$$A:=\{n \in \mathbb{N}: \mathbb{N} \vDash \varphi(n)\}$$

In Shoenfield: A predicate $P$ is r.e. if there is a recursive predicate $Q$ such that

$$P(\bar{a}) \leftrightarrow \exists x Q(\bar{a}, x)$$ for all $\bar{a} \in P$. And in here there is another one A new definition of recursively enumerable set?.

My question is: Are the definitions of recursively enumerate equivalent? Why?

  • $\begingroup$ It looks like you forgot to accept a good answer to the previous question of yours. It is, of course, entirely up to you whether to accept an answer or not. However, it is part of a basic protocol or etiquette to try to finish your previous questions by accepting an answer, especially when an answer that is very satisfying has appeared. Note that a question without an answer accepted by the questioner is tagged "unanswered" officially by this site even if it has multiple upvoted answers. That "unanswered" question will behave very differently from an "answered" question in various ways. $\endgroup$ – John L. Oct 4 '18 at 17:51
  • $\begingroup$ I'm so sorry! I didn't know this protocol. $\endgroup$ – Tom Ryddle Oct 4 '18 at 18:08
  • 2
    $\begingroup$ That is fine, Tom. Welcome to this site! It does take some time to learn how to take the most advantage of this site as well as how to be a good citizen of this site. Thank you for accepting that answer to your previous question on behalf of all users if I may! $\endgroup$ – John L. Oct 4 '18 at 19:33

Your two definitions are essentially the same: a $\Sigma_1^0$ formula is one of the form $$\exists x Q(n,x),$$ where $Q$ is computable and $n$ is the parameter.

Another difference between the two definitions is that the first only defines r.e. sets, i.e. unary relations, whereas the second defines r.e. relations of arbitrary arity. The two definitions coincide in the case of unary relations.

| cite | improve this answer | |
  • $\begingroup$ In the first definition why is $Q$ computable (recursaive)? I only can be sure $Q$ is Bounded quantifier. $\endgroup$ – Tom Ryddle Oct 5 '18 at 4:33
  • 2
    $\begingroup$ This is the definition of $\Sigma_1^0$. $\endgroup$ – Yuval Filmus Oct 5 '18 at 4:34
  • $\begingroup$ Thank you Yuval. Can you suggest me some basic books about recursively enumerable and recursive sets? $\endgroup$ – Tom Ryddle Oct 5 '18 at 4:51
  • 1
    $\begingroup$ It's a standard topic so there should be many textbooks out there. Sipser probably covers this topic in his Introduction to the Theory of Computation, for example. $\endgroup$ – Yuval Filmus Oct 5 '18 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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