En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Kleene est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano. Un ensemble d'entiers est classé suivant les alternances de quantificateurs d'une formule sous forme prénexe qui permet de le définir. Les premiers niveaux de la hiérarchie correspondent à la classe des ensembles récursivement énumérables (Σ₁⁰) et à celle des ensembles dont le complémentaire est récursivement énumérable (Π₁⁰), leur intersection étant la classe des ensembles récursifs (Δ₁⁰).

[Dernier contributeur : Utilisateur Wikipedia non enregistré , Contenu soumis à la licence LGPL]