Question

Il y a quelques définitions de Énumérable récursivement, par exemple en Juda: $ A sous-ensemble mathbb {n} $ est appelé re s'il existe un $ Sigma ^ 0_1 $ formule $ varphi (x) $ tel que

$$ a: = {n in mathbb {n}: mathbb {n} vdash varphi (n) } $$

À Shoenfield: Un prédicat $ P $ est re s'il y a un prédicat récursif $ Q $ tel que

$$ p ( bar {a}) leftrightarrow existe x q ( bar {a}, x) $$ pour tous $ bar {a} in p $. Et ici, il y en a un autre Une nouvelle définition de l'ensemble énumérable récursivement?.

Ma question est: les définitions de l'énumération récursive sont-elles équivalentes? Pourquoi?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top