În logica matematică , în special în teoria calculabilității , ierarhia aritmetică definită de Stephen Cole Kleene este o ierarhie a subseturilor din mulțimea N de numere întregi definibile în limbajul primului ordin al aritmeticii Peano . Un set de numere întregi este clasificat în funcție de alternanța cuantificatorilor unei formule într- o formă pre-anexată care permite definirea acesteia.
Primele niveluri ale ierarhiei corespund clasei de mulțimi recursiv enumerabile (Σ 1 0 ) și celei de mulțimi al căror complement este recursiv enumerabil (Π 1 0 ), intersecția lor fiind clasa de mulțimi recursive (Δ 1 0 ).
Pentru a defini ierarhia subseturilor definite de N , putem folosi o ierarhie de formule (în sensul calculării predicatelor ) de aritmetică. Acestea sunt formule de ordinul întâi , așa cum este indicat de exponentul 0, când vorbim de formula Σ n 0 sau Π n 0 . La fel, ierarhia analitică folosește formule de ordinul al doilea, care este notat de exponentul 1. În cele ce urmează, vom omite exponentul 0 deoarece nu există riscul confuziei.
La nivelul 0, clasele formulelor Σ 0 și Π 0 sunt identice. Acestea sunt formulele cu cuantificatori mărginite ale limbajului aritmeticii Peano, adică cele care sunt construite din egalități polinomiale (adunarea și multiplicarea sunt singurele simboluri ale funcțiilor utilizate), cu conectorii obișnuiți, și cuantificatorii universali și existențiali delimitați ∃ x ≤ t … și ∀ x ≤ t …. De exemplu, această formulă cu două variabile libere x și z este Σ 0 (sau Π 0 ):
(∃y≤z) 2z = (x + y) (x + y + 1) + 2yeste Σ 0 (sau Π 0 ).
Apoi definim inductiv clasele formulelor Σ n și Π n , pentru un număr natural n zero .
Astfel, o formulă Σ n sau Π n este o formulă cu cuantificatori delimitați precedată de un prefix de n alternanțe de cuantificatori începând cu un cuantificator existențial pentru Σ n , cu un cuantificator universal pentru Π n .
Noțiunea pe care am definit-o este pentru moment pur sintactică. Nu am clasificat toate formulele limbajului, dar orice formulă echivalentă cu o formă pre-anexată este echivalentă cu o formulă a ierarhiei, a cărei matrice nu conține nici măcar cuantificări delimitate. De asemenea, putem observa că negația unei formule Σ 0 fiind Π 0 (clasa este stabilă prin negație), negația unei formule Σ n este echivalentă cu o formulă Π n .
Se spune că un subset de N este Σ n , respectiv Π n , dacă poate fi definit printr-o formulă cu o variabilă liberă Σ n , respectiv Π n , și se spune că este Δ n dacă este atât Σ n, cât și Π n . Deducem direct din definiția formulelor Σ n și Π n că o mulțime este Π n dacă și numai dacă complementul său este Σ n și, prin urmare, mulțimile Δ n sunt și mulțimile Σ n al căror complement este și Σ n .
Poate fi convenabil să se extindă noțiunea la upluri de numere întregi naturale: un subset de N p , unde p este un număr natural diferit de zero, este Σ n , respectiv Π n , dacă este definit de o formulă Σ n , respectiv Π n , cu p variabile libere.
În mod echivalent, vorbim și despre un predicat sau o relație pe N Σ n sau Π n .
Astfel clasificăm toate subseturile definibile de ordinul întâi ale lui N ca Σ n sau Π n , aceasta se numește ierarhie aritmetică . Clasificarea unui set în ierarhie permite într-un mod să măsoare „gradul de calculabilitate” al setului datorită complexității logice a unei formule care îl definește. Cu cât un set este mai înalt în ierarhie, cu atât este mai puțin calculabil.
Într-adevăr, urmărind metodele utilizate de Gödel pentru a demonstra prima sa teoremă de incompletitudine , arătăm că clasa mulțimilor Σ 1 este exact clasa mulțimilor recursiv enumerabile . Astfel, Δ 1 desemnează clasa seturilor recursiv enumerabile și a seturilor complementare recursiv enumerabile, deci clasa seturilor recursive.
Dacă adăugăm un cuantificator „inutil” (adică referitor la o variabilă care nu apare în formulă), la cap sau la sfârșitul prefixului cuantificatoarelor unei formule Σ n sau Π n , obținem o formula echivalentă banal. Prin urmare, este imediat că:
Σ n ∪ Π n ⊂ Σ n +1 ∩ Π n +1 = Δ n +1 .
În plus, evident, prin definiția lui Δ n :
Δ n ⊂ Σ n și Δ n ⊂ Π n .Rețeaua de includere în ierarhia aritmetică este pe deplin descrisă de aceste relații de incluziune, în special aceste incluziuni sunt incluziuni stricte , ceea ce rezultă în esență din indecidabilitatea problemei stop , care spune direct că Δ 1 este o parte strictă a Σ 1 și, prin urmare, din Π 1 .
Fiecare clasă Σ n , Π n sau Δ n este stabilă prin intersecție și uniune; îl deducem construind în ordinea adecvată forma anexă a conjuncției sau disjuncția a două formule Σ n sau Π n . De asemenea, sunt stabile în funcție de produsul cartezian. Clasa mulțimilor Δ n este stabilă mergând la complementar și deci prin toate operațiile booleene.
Putem arăta că orice set al ierarhiei poate fi întotdeauna definit la același nivel printr-o formulă în care fiecare alternanță este redusă la un singur cuantificator și unde matricea este o formulă Σ 0 :
unde F este Σ 0 .
Se poate folosi pentru aceasta codificarea cuplurilor Cantor, care este gestionată de formulele Σ 0 .
Un set Σ n se scrie A = { n ∈ N / ∃ ( a 1 ,…, a k ) ∈ N k , P ( n , a 1 ,…, a k )} cu P o formulă Π n -1 la k +1 variabile gratuite. Putem apoi forma mulțimea B = {( n , a 1 ,…, a k ) ∈ N k +1 / P ( n , a 1 ,…, a k )}, care este Π n -1 în N k + 1 și rețineți că A este proiecția lui B conform primei coordonate.
O cuantificare existențială corespunde astfel unei proiecții. Putem deduce din aceasta o altă definiție a ierarhiei aritmetice care nu apelează direct la formule. Într-adevăr, clasa Σ n fiind definită (pentru subseturi de N p p > 0):
Aceasta definește ierarhia, clasa seturilor Σ 0 fiind definită.
Este totuși posibil să luăm o altă clasă de subseturi ale uniunii lui N p , p > 0, ca punct de plecare, păstrând aceeași ierarhie începând de la rangul 1. De exemplu, putem începe:
În al doilea caz, acest lucru echivalează, pentru definirea prin formule, la luarea în locul formulelor Σ 0 a formulelor fără cuantificatori (chiar delimitați).
Teorema Post este în mod specific legătura dintre ierarhia aritmetică și gradul de Turing .