Are the definitions of recursively enumerate equivalent?
-
05-11-2019 - |
Frage
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?
Keine korrekte Lösung
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange