I matematisk logikk , spesielt i teorien om beregbarhet , er det aritmetiske hierarkiet definert av Stephen Cole Kleene , et hierarki av delmengder av mengden N av heltall som kan defineres på språket i første orden av Peano-aritmetikken . Et sett med heltall er klassifisert i henhold til vekslingen av kvantifiserere av en formel i form av et vedlegg som gjør det mulig å definere det.
De første nivåene i hierarkiet tilsvarer klassen av rekursivt opptellbare sett (Σ 1 0 ) og den til sett hvis komplement er rekursivt opptellbar (Π 1 0 ), hvor skjæringspunktet er klassen av rekursive sett (Δ 1 0 ).
For å definere hierarkiet til definerbare delmengder av N , kan vi bruke et hierarki av formler (i betydningen beregning av predikater ) av aritmetikk. Dette er førsteordensformler , som er indikert av eksponenten 0, når vi snakker om formelen Σ n 0 eller Π n 0 . På samme måte bruker det analytiske hierarkiet andreordensformler, som er betegnet med eksponenten 1. I det følgende vil vi utelate eksponenten 0 fordi det ikke er noen risiko for forvirring.
På nivå 0 er klassene med formler Σ 0 og Π 0 identiske. Dette er formlene med avgrensede kvantifiserere av språket for Peano-aritmetikk, det vil si de som er konstruert fra polynomiske likheter (tillegg og multiplikasjon er de eneste symbolene på funksjoner som brukes), med de vanlige kontaktene, og de begrensede universelle og eksistensielle kvantifiserende ∃ x ≤ t … og ∀ x ≤ t …. For eksempel er denne formelen med to ledige variabler x og z Σ 0 (eller Π 0 ):
(∃y≤z) 2z = (x + y) (x + y + 1) + 2yer Σ 0 (eller Π 0 ).
Deretter definerer vi induktivt klassene til formlene Σ n og Π n , for et ikke-null naturlig tall n .
Dermed er en formel Σ n eller Π n en formel med avgrensede kvantifiserere foran et prefiks av n veksling av kvantifiserere som begynner med en eksistensiell kvantifier for the n , med en universell kvantifiser for Π n .
Forestillingen som vi har definert er for øyeblikket rent syntaktisk. Vi har ikke klassifisert alle formlene i språket, men en hvilken som helst formel som tilsvarer en forhåndsvedlagt form tilsvarer en formel i hierarkiet, hvis matrise ikke engang inneholder avgrensede kvantifiseringer. Vi kan også merke at negasjonen av en formel Σ 0 er Π 0 (klassen er stabil av negasjon), negasjonen av en formel Σ n tilsvarer en formel Π n .
En delmengde av N sies å være henholdsvis Σ n , n , hvis den kan defineres med en formel med en fri variabel Σ n , henholdsvis Π n , og det sies å være Δ n hvis den er både Σ n og n . Vi trekker direkte ut fra definisjonen av formlene Σ n og Π n at et sett er Π n hvis og bare hvis dets komplement er Σ n , og derfor er mengden Δ n også settene Σ n hvis komplement også er Σ n .
Det kan være hensiktsmessig å utvide definisjonen til uples av naturlige tall: en undergruppe av N p , hvor p er et ikke-null naturlig heltall, er Σ n , henholdsvis Π n , hvis den er definert ved en formel Σ n , henholdsvis Π n , med p gratis variabler.
På en ekvivalent måte snakker vi også om et predikat eller en relasjon på N Σ n eller Π n .
Vi klassifiserer altså alle de første ordens definerbare delmengder av N som Σ n eller Π n , dette kalles det aritmetiske hierarkiet . Klassifisering av et sett i hierarkiet gjør det mulig på en måte å måle "graden av beregbarhet" til settet takket være den logiske kompleksiteten til en formel som definerer det. Jo høyere et sett er i hierarkiet, desto mindre kan det beregnes.
Faktisk, ved å følge metodene som Gödel bruker for å bevise sin første ufullstendighetssetning , viser vi at klassen av sett Σ 1 er nøyaktig klassen av rekursivt utallige sett . Således Δ 1 er klassen av rekursivt nummererbare sett og av rekursivt nummererbare komplementære sett, og derfor den klasse av rekursive sett.
Hvis vi legger til en "ubrukelig" kvantifier (det vil si relatert til en variabel som ikke vises i formelen), på hodet eller på slutten av prefikset for kvantifiserere med en formel Σ n eller Π n , får vi en trivielt ekvivalent formel. Det er derfor umiddelbart at:
Σ n ∪ Π n ⊂ Σ n +1 ∩ Π n +1 = Δ n +1 .
I tillegg har vi, åpenbart per definisjon av Δ n :
Δ n ⊂ Σ n og Δ n ⊂ Π n .Gitter av inkludering på den aritmetiske hierarkiet er fullt ut beskrevet ved hjelp av disse inklusjonsforbindelser, spesielt slike inneslutninger er strenge inneslutninger , som i det vesentlige resulterer fra undecidability av stopp problem , som direkte står at Δ 1 er en streng del av Σ 1 og dermed av Π 1 .
Hver klasse Σ n , Π n eller Δ n er stabil ved kryss og forening; vi utleder det ved å konstruere i riktig rekkefølge pre-annex-formen av sammenhengen eller skillet mellom to formler Σ n eller Π n . De er også stabile av kartesisk produkt. Klassen av mengder Δ n er stabil ved å gå til den komplementære og derfor av alle de boolske operasjonene.
Vi kan vise at ethvert sett i hierarkiet alltid kan defineres på samme nivå ved hjelp av en formel der hver veksling reduseres til en enkelt kvantifiserende og hvor matrisen er en formel Σ 0 :
hvor F er Σ 0 .
Man kan bruke til dette kodingen av Cantor-parene, som håndteres av formler Σ 0 .
Et sett Σ n skrives A = { n ∈ N / ∃ ( a 1 ,…, a k ) ∈ N k , P ( n , a 1 ,…, a k )} med P en formel Π n -1 ved k +1 gratis variabler. Vi kan da danne mengden B = {( n , a 1 ,…, a k ) ∈ N k +1 / P ( n , a 1 ,…, a k )}, som er Π n -1 i N k + 1 , og merk at A er projeksjonen av B i henhold til den første koordinaten.
En eksistensiell kvantifisering tilsvarer altså en projeksjon. Vi kan utlede fra en annen definisjon av det aritmetiske hierarkiet som ikke beretter formlene direkte. Faktisk er klassen Σ n definert (for undergrupper av N p p > 0):
Dette definerer hierarkiet, klassen av sett Σ 0 defineres.
Det er imidlertid mulig å ta en annen klasse av delmengder av foreningen av N p , p > 0, som utgangspunkt, mens man holder det samme hierarkiet fra rang 1. For eksempel kan vi starte:
I det andre tilfellet tilsvarer dette, for definisjonen av formlene, å ta i stedet for formlene Σ 0 formlene uten kvantifiserere (til og med avgrenset).
The Post teorem er spesielt koblingen mellom aritmetisk hierarki og graden av Turing .