Développement : Caractérisation des ensembles Récursivement Énumérables

Détails/Enoncé :

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.

Recasages pour l'année 2025 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Logique mathématique Tome 2, René Cori, Daniel Lascar (utilisée dans 7 versions au total)
131 Développements pour l’oral, D. Lesesvre, P. Montagnon, P. Le Barbenchon, T. Pierron (utilisée dans 75 versions au total)