Aritmetička hijerarhija

U matematičkoj logici, aritmetička hijerarhija, aritmetička hijerarhija ili Klin-Mostovskova hijerarhija klasifikuje određene skupove na osnovu složenosti formula koje ih definišu. Bilo koji skupi koji dobija klasifikaciju se zove aritmetički.

Računska hijerarhija je važna u teoriji rekurzije i efektivne teorije opisnog skupa, i studija formalnih teorija kao što je Peano aritmetika.

Tarski-Kuratovski algoritam pruža jednostavan način da dobijete gornju granicu klasifikacije određene za formulu i set koji ga definiše.

Hiperaritmetička hijerarhija i analitička hijerarhija produžuju aritmetičku hijerarhiju kako bi klasifikovali dodatne formule i skupove.

Aritmetička hijerarhija formula

Računska hijerarhija dodeljuje klasifikacije formulama u jeziku prvog reda aritmetike. Klasifikacije su označene kao $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$ za prirodne brojeve n (uključujući 0). Grčka pisma su ključni simboli, što ukazuje da formule ne sadrže postavljene parametre.

Ako  je formula $\phi$ logički ekvivalentna formuli sa samo ograničenim kvatifikatorima onda $\phi$ su dodeljene klasifikacije $\Sigma _{0}^{0}$ i $\Pi _{0}^{0}$.

Klasifikacije $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$ se induktivno definišu za svaki prirodan broj n koristeći sledeća pravila:

• Ako je $\phi$ logički ekvivalentna formuli forme$\exists n_{1}\exists n_{2}\cdots \exists n_{k}\psi$, gde $\psi$ je $\Pi _{n}^{0}$, onda $\phi$ je dodeljena klasifikacija $\Sigma _{n+1}^{0}$.
• Ako je $\phi$ logički ekvivalentna formuli forme $\forall n_{1}\forall n_{2}\cdots \forall n_{k}\psi$, gde $\psi$ je $\Sigma _{n}^{0}$, onda $\phi$ je dodeljena klasifikacija $\Pi _{n+1}^{0}$.

Takođe, $\Sigma _{n}^{0}$ formula je ekvivalentna formuli koja počinje sa nekim egzistencijalnim kvantifikatorima i alternativi $n-1$ puta između niza egzistencijalnih i univerzalnih kvantifikatora; dok $\Pi _{n}^{0}$ formula je ekvivalentna formuli koja počinje sa nekim univerzalnim kvantifikatorima i alternativama na sličan način.

Zato što je svaka formula ekvivalentna formuli u Preneks normalnom obliku, svakoj formuli bez postavljenih kvantifikatora je dodeljena najmanje jedna klasifikacija. Budući redudantni kvantifikatori se mogu dodati bilo kojoj formuli, jedanput kada je formula dodeljena klasifikacija $\Sigma _{n}^{0}$ ili $\Pi _{n}^{0}$ biće dodeljene klasifikacije $\Sigma _{m}^{0}$ i $\Pi _{m}^{0}$ za svako m veće od n. Najvažnija klasifikacija koja se dodeljuje formuli je ona sa najmanje n, jer je to dovoljno da se utvrde sve ostale klasifikacije.

Aritmetička hijerarhija skupova prirodnih brojeva

Skup prirodnih brojeva X je definisan formulom φ jezikom Peano aritmetike (jezik prvog reda sa simbolima "0" za nula, "S" za funkciju nasleđivanja, "+" za zbir, "×" za množenje i "=" za jednakost), ako su elementi X  tačno brojevi koji zadovoljavaju φ. To je, za sve prirodne brojeve n,

gde je ${\underline {n}}$ je cifra na jeziku aritmetike koja odgovara $n$. Skup je definisan u prvom redu aritmetike ako je to definisano na osnovu neke formule na jeziku Peano aritmetike.

Svakom skupu prirodnih brojeva X koji je definisan prvim redom aritmetike su dodeljene klasifikacije forme  $\Sigma _{n}^{0}$, $\Pi _{n}^{0}$, i $\Delta _{n}^{0}$, gde je $n$ prirodan broj, kako sledi. Ako je X definisan sa $\Sigma _{n}^{0}$ formulom onda je X dodeljena klasifikacija $\Sigma _{n}^{0}$. Ako je X definisan sa $\Pi _{n}^{0}$ formulom onda je X dodeljena klasifikacija $\Pi _{n}^{0}$. Ako je X i $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$ onda je $X$ dodeljena dodatna klasifikacija $\Delta _{n}^{0}$.

Imajte na umu da retko ima smisla govoriti o $\Delta _{n}^{0}$ formulama; prvi kvantifikator formule je bilo egzistencijalan ili univerzalan. Onda $\Delta _{n}^{0}$ skup nije definisan sa $\Delta _{n}^{0}$ formulom; pre nego, gde su i $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$  formule koje definišu skup.

Paralelna definicija se koristi za definisanje računske hijerarhije na konačan Dekartov proizvod prirodnih brojeva. Umesto formula sa jednom slobodnom promenljivom, formule sa k slobodnim brojem promenljivih se koriste za definisanje računske hijerarhije skupovima od k-torki prirodnih brojeva.

Relativizirane aritmetičke hijerarhije

Kao što možemo definisati šta to znači za skup X da bude rekurzivan u odnosu na drugi skup Y dozvoljavajući izračunavanja definisanjem X da se konsultuje sa Y i možemo da produžimo ovaj pojam na celu aritmetičku hijerarhiju i definisati šta to znači za X da bude $\Sigma _{n}^{0}$, $\Delta _{n}^{0}$ ili $\Pi _{n}^{0}$ u Y, označavaju redom $\Sigma _{n}^{0,Y}$ $\Delta _{n}^{0,Y}$ i $\Pi _{n}^{0,Y}$. Da bi se to uradilo, treba popraviti niz celih brojeva Y i da se doda predikat za članstvo u Y na jeziku Peano aritmetike. Tada smo rekli da je X u $\Sigma _{n}^{0,Y}$ ako je definisano sa $\Sigma _{n}^{0}$ formula u ovom proširenom jeziku. Drugim rečima X je $\Sigma _{n}^{0,Y}$ ako je definisan sa $\Sigma _{n}^{0}$ formulom kojoj je dozvoljeno da postavlja pitanja u vezi članstva u Y. Alternativno može se pogledati $\Sigma _{n}^{0,Y}$ skupova kao i one koji mogu da se grade počev od skupova rekurzivnih u Y i naizmenično uzimanje unija i preseka ovih skupova do n puta.

Ako je na primer Y skup celih brojeva. Neka X bude skup brojeva deljivih nekim elementom iz Y. Onda je X definisano formulom $\phi (n)=\exists m\exists t(Y(m)\land m\times t=n)$ tako da je X u $\Sigma _{1}^{0,Y}$ (u stvari je u $\Delta _{0}^{0,Y}$ kao i jer smo mogli da ograničimo obe strane kvantifikatora n).

Aritmetičko smanjenje i stepeni

Aritmetičko smanjenje je srednji pojam između Tjuringovog smanjenja i hiperaritmetičkog smanjenja.

Skup je aritmetički (takođe aritmetika i aritmetički definisan) ako je to definisano na osnovu neke formule na jeziku Peano aritmetike. Ekvivalentno X je aritmetički ako je X  $\Sigma _{n}^{0}$ ili $\Pi _{n}^{0}$ za neki ceo broj n. Skup X je aritmetički u skupu Y, koji je označen kao $X\leq _{A}Y$, ako je X definisano nekom formulom na jeziku Peano aritmetike druge strane predikata za članstvo u Y. Ekvivalentno, X je aritmetičko u Y ako je X u $\Sigma _{n}^{0,Y}$ ili $\Pi _{n}^{0,Y}$ za neki ceo broj n. Sinonim za $X\leq _{A}Y$ je: X je aritmetički smanjeno na Y.

Relacija $X\leq _{A}Y$ je refleksivna i prelazna, a time i odnos $\equiv _{A}$ definisan pravilom

je relacija ekvivalencije. Ekvivalentne klase ove relacije se nazivaju aritmetički stepeni; oni su delimično naređeni pod $\leq _{A}$.

Aritmetička hijerarhija podskupova Kantorovog i Berovog prostora

Kantorov prostor, označen $2^{\omega }$, je skup svih beskonačnih sekvenci 0s i 1s; Berov prostor, označen $\omega ^{\omega }$ ili ${\mathcal {N}}$, je skup svih beskonačnih sekvenci prirodnih brojeva. Imajte na umu da elementi Kantorovog prostora mogu da se identifikuju sa kompleta celih brojeva i elemenata Berovog prostora sa funkcijama prirodnih brojeva do celih brojeva.

Obična aksiomatizacija od drugog reda aritmetike koristi jezik seta sa sedištem u kojima su postavljeni kvantifikatori koji se prirodno mogu smatrati kvantifikovanjem preko Kantorovog prostora. Podskup Kantorovog prostora je dodeljen klasifikaciji $\Sigma _{n}^{0}$ ako je definisan sa $\Sigma _{n}^{0}$ formulom. Skupu je dodeljena klasifikacija $\Pi _{n}^{0}$ ako je definisan sa formulom $\Pi _{n}^{0}$. Ako je skup i $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$ onda mu se dodeljuje dodatna klasifikacija $\Delta _{n}^{0}$. Na primer ako je $O\subset 2^{\omega }$ skup svih beskonačnih binarnih nizova gde nisu svi 0 (ili ekvivalentno skup svih nepraznih skupova celih brojeva). Kao $O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}$ vidimo da je $O$ definisano formulom $\Sigma _{1}^{0}$ i stoga je $\Sigma _{1}^{0}$ skup.

Imajte na umu da, iako su oba elementa Kantorovog prostora (smatra se skupom celih brojeva) i podskupova u Kantorovom prostoru su klasifikovani u aritmetičke hijerarhije, to nisu iste hijerarhije. U stvari, odnos između dve hijerarhije je zanimljiv i netrivijalan. Na primer $\Pi _{n}^{0}$ elementi Kantorovog prostora nisu (generalno) isti kao elemnti iz $X$ Kantorovog prostora tako da je $\{X\}$  $\Pi _{n}^{0}$ podskup Kantorovog prostora. Međutim, mnogi zanimljivi rezultati se odnose na dve hijerarhije.

Postoje dva načina da se podskup Berovog prostora može svrstati u aritmetičke hijerarhije.

• Podskup Berovog prostora ima odgovarajući podskup Kantorovog prostora koja se odnosi na svaku funkciju iz $\omega$ u $\omega$ na karakteristiku funkcije njenog grafa. Podskup Berovog prostora ima klasifikaciju $\Sigma _{n}^{1}$, $\Pi _{n}^{1}$, ili $\Delta _{n}^{1}$ ako i samo ako odgovarajući podskup Kantorovog prostora ima istu klasifikaciju.
• Ekvivalentna definicija analitičke hijerarhije Berovog prostora daje definisanje analitičke hijerarhije formula pomoću funkcionalne verzije drugog reda aritmetike; onda analitička hijerarhija podgrupe Kantorovog prostora može biti definisana od hijerarhije na Berovom prostoru. Ova definicija alternativno daje upravo iste klasifikacije kao za prvu definiciju.

Paralelne definicije se koriste za definisanje računske hijerarhije na konačna kartezijanska ovlašćenja Berovog prostora ili Kantorovog prostora, koristeći formule sa nekoliko slobodnih promenljivih. Računska hijerarhija se može definisati na bilo koji efikasni poljski prostor; definicija je posebno jednostavna za Kantorov prostor i Berov prostor jer se uklapa sa jezikom običnog drugog reda aritmetike.

Imajte na umu da možemo definisati aritmetičku hijerarhiju podskupova Kantorovog i Berovog prostora u odnosu na neki skup prirodnih brojeva. U stvari podebljana $\mathbf {\Sigma } _{n}^{0}$ je samo unija $\Sigma _{n}^{0,Y}$ za sve skupove celih brojeva Y. Imajte na umu da je podebljana hijerarhija samo standardna hijerarhija Borelove hijerarhije.

Ekstenzije i varijacije

Moguće je definisati aritmetičku hijerarhiju formula korišćenjem jezika produženog sa simbolom za svaku primitivnu rekurzivnu funkciju. Ova varijacija malo menja klasifikaciju nekih skupova.

Mnoge semantičke varijacije hijerarhije mogu se definisati na svim finitarnim odnosima prirodnih brojeva; sledeća definicija se koristi. Svaki izračunljiv odnos se definiše kao $\Sigma _{0}^{0}$ i $\Pi _{0}^{0}$. Klasifikacije $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$ se induktivno definišu sa sledećim pravilima.

• Ako relacija $R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,$ je $\Sigma _{n}^{0}$ onda je relacija$S(n_{1},\ldots ,n_{l})=\forall m_{1}\cdots \forall m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})$ definisana da bude $\Pi _{n+1}^{0}$
• Ako relacija $R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,$ je $\Pi _{n}^{0}$ onda je relacija$S(n_{1},\ldots ,n_{l})=\exists m_{1}\cdots \exists m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})$ definisana da bude $\Sigma _{n+1}^{0}$

Ova varijacija malo menja klasifikaciju nekih skupova. To se može proširiti da pokrije finitarne odnose na prirodne brojeve, Berovog prostora, i Kantorovog prostora.

Značenje oznake

Sledeća značenja, se mogu priključiti notaciji za aritmetički redosled formula.

Oznaka $n$ u simbolima $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$ ukazuje na broj promena blokova univerzalnog i egzistencijalnog broja kvantifikatora koji se koriste u formuli. Štaviše, spoljni blok je egzistencijalan u $\Sigma _{n}^{0}$ formule i univerzalni u $\Pi _{n}^{0}$ formulama.

Oznaka $0$ u simbolima $\Sigma _{n}^{0}$, $\Pi _{n}^{0}$, i $\Delta _{n}^{0}$ označava tip predmeta koji se kvantifikuju gotovi. Tip 0 objekti su prirodni brojevi, i objekti tipa $i+1$ su funkcije koje mapiraju skup objekata tipa $i$ na prirodne brojeve. Kvantifikacija nad većim objektima tipa, kao što je funkcija prirodnih brojeva do prirodnih brojeva, opisana od strane superskriptu veća od 0, kao u analitičkoj hijerarhiji. Superskript 0 ukazuje na kvantifikatore preko brojeva, eksponent 1 ukazuje na kvantifikaciju nad funkcijama od brojeva do broja (tip 1 predmet), superskript 2 bi odgovarao kvantifikaciji preko funkcija koje uzimaju tip 1 objekat i vraćaju broj, i tako dalje.

Primeri

• $\Sigma _{1}^{0}$ skupovi brojeva su oni definisani po formuli forme $\exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)$ gde $\psi$ ima samo ograničene kvantifikatore. To su upravo rekurzivno brojivi skupovi.
• Skup prirodnih brojeva koji su indeksi za Tjuringove mašine koje računaju ukupan broj funkcija u $\Pi _{2}^{0}$. Intuitivno, indeks $e$ spada u ovom skupu ako i samo ako za svaki $m$ "postoji neko $s$ tako da se Tjuringova mašina sa indeksom $e$ zaustavlja na ulazu $m$ posle $s$ koraka”. Kompletan dokaz bi pokazao da je imovina prikazana u navodnicima u prethodnoj rečenici i definiše se na jeziku Peano aritmetike od strane $\Sigma _{1}^{0}$ formula.
• Svaki $\Sigma _{1}^{0}$ podskup Berovog prostora ili Kantorovog prostora je otvoren skup u uobičajenoj topologiji prostora. Osim toga, za svaki takav skup postoji izračunljivo nabrajanje Gedelovih brojeva osnovnih otvorenih skupova čija je unija originalan skup. Iz tog razloga, $\Sigma _{1}^{0}$ skupovi se ponekad nazivaju efikasno otvorenim. Slično tome, svaki $\Pi _{1}^{0}$ skup je zatvoren i $\Pi _{1}^{0}$ skupovi se ponekad nazivaju zatvorenim.
• Svaki aritmetička podskup Kantorovog prostora ili Berovog prostora je Borelov skup. Borelova hijerarhija proširuje aritmetičku hijerarhiju da uključi dodatni Borelov skup. Na primer, svaki $\Pi _{2}^{0}$ podskup Kantorovog ili Berovog prostora je $G_{\delta }$ skup (to jest, što je jednako skupu preseka brojivih otvorenih skupova). Osim toga, svaki od ovih otvorenih skupova je $\Sigma _{1}^{0}$ i lista Gedelovih brojeva otvorenih skupova ima izračunljivu vrednost. Ako $\phi (X,n,m)$ je $\Sigma _{0}^{0}$ formula sa slobodnim skupom promenljive X i slobodnim brojem promenljivih $n,m$ onda $\Pi _{2}^{0}$ skup $\{X\mid \forall n\exists m\phi (X,n,m)\}$ je presek $\Sigma _{1}^{0}$ skupova forme $\{X\mid \exists m\phi (X,n,m)\}$ kako n kreće preko skupa prirodnih brojeva.  

Svojstva

Sledeće osobine staju za aritmetičke hijerarhije skupova prirodnih brojeva i aritmetičke hijerarhije podgrupa Kantorovog ili Berovog prostora.

• Kolekcije $\Pi _{n}^{0}$ i $\Sigma _{n}^{0}$ su zatvorene pod konačnim unijama i konačnim presecima njihovih elemenata.
• Skup je $\Sigma _{n}^{0}$ ako i samo ako je njegova dopuna $\Pi _{n}^{0}$. Skup je$\Delta _{n}^{0}$ ako i samo ako je skup i $\Sigma _{n}^{0}$ i $\Pi _{n}^{0}$, u kom slučaju će njegov komplement takođe biti $\Delta _{n}^{0}$.
• Inkluzije $\Delta _{n}^{0}\subsetneq \Pi _{n}^{0}$ i $\Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}$ staju za $n\geq 1$.
• Inkluzije $\Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}$ i $\Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}$ staju za svako $n$ i inkluziju $\Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}$ staju za $n\geq 1$. Tako da hijerarhija ne propadne.

Relacija ka Tjuringovim mašinama

Tjuringovi izračunljivi skupovi prirodnih brojeva su upravo skupovi na nivou $\Delta _{1}^{0}$ aritmetičke hijerarhije. U rekursivno brojivim skupovima su upravo skupovi na nivou $\Sigma _{1}^{0}$.

Proročka mašina nije u stanju da reši svoj problem obustave (varijacija Tjuringa je dokaz primene). Ograničeni problem za $\Delta _{n}^{0,Y}$, u stvari, sedi u $\Sigma _{n+1}^{0,Y}$.

Postova teorema uspostavlja blisku vezu između aritmetičke hijerarhije skupova prirodnih brojeva i Tjuringovih stepeni. Konkretno, utvrđuje sledeće činjenice za sve n ≥ 1:

• Skup $\emptyset ^{(n)}$ (enti Tjuringov skok praznog skupa) se završi u jednom i svakom $\Sigma _{n}^{0}$.
• Skup $\mathbb {N} \setminus \emptyset ^{(n)}$ se završi u jednom i svakom  $\Pi _{n}^{0}$.
• Skup $\emptyset ^{(n-1)}$ se završi Tjuringom u $\Delta _{n}^{0}$.

Hijerarhija polinoma  je "izvodljiv resurs ograničene" verzije aritmetičke hijerarhije u kojoj se dužina polinoma granica stavlja na brojeve koji su uključeni (ili, ekvivalentno, vreme polinoma granica je postavljeno na Tjuringove mašine koje su uključene). To daje finiju klasifikaciju nekih skupova prirodnih brojeva koji su na nivou $\Delta _{1}^{0}$ aritmetičke hijerarhije.

Vidi još

• Interpreteabilna logika
• Hijerarhija (matematika)
• Hijerarhija polinoma

Literatura

• Dzhaparidze, Giorgie (1994). „The logic of arithmetical hierarchy”. Annals of Pure and Applied Logic. 66 (2): 89—112. doi:10.1016/0168-0072(94)90063-9. 
• Moschovakis, Yiannis N. (1980), Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics 100, North Holland. ISBN 978-0-444-70199-2., Zbl 0433.03025.
• Nies, André (2009). Computability and randomness. Oxford Logic Guides. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. 
• Rogers, H., jr (1967), Theory of recursive functions and effective computability, Maidenhead: McGraw-Hill, Zbl 0183.01401.