Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top