Are the definitions of recursively enumerate equivalent?
-
05-11-2019 - |
Question
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange