Caractérisation des ensembles Récursivement Énumérables
Les assertions suivantes sont équivalentes:
1. $A$ est dans $\mathrm{RE}$,
2. $\exists B\subset \mathbb{N}^2$ primitif récursif tel que $A=\pi^2_2(B)$,
3. $A=\varnothing$ ou $A$ est l’image d’une fonction primitive récursive,
4. $A$ est l’image d’une fonction récursive.
| Qualité | Numéro | Titre |
|---|
Utilisateur : Volgaar
Cori-Lascar tome 2, p.41.'
Références :
Logique mathématique Tome 2 - René Cori, Daniel Lascar
131 Développements pour l’oral - D. Lesesvre, P. Montagnon, P. Le Barbenchon, T. Pierron