Les définitions de l'énumération récursivement sont-elles équivalentes?
-
05-11-2019 - |
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