# Are the definitions of recursively enumerate equivalent?

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?

• 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. – John L. Oct 4 '18 at 17:51
• I'm so sorry! I didn't know this protocol. – Tom Ryddle Oct 4 '18 at 18:08
• 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! – 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.
• In the first definition why is $Q$ computable (recursaive)? I only can be sure $Q$ is Bounded quantifier. – Tom Ryddle Oct 5 '18 at 4:33
• This is the definition of $\Sigma_1^0$. – Yuval Filmus Oct 5 '18 at 4:34