Aritmetika hierarkio

En matematika logiko, la **aritmetika hierarkio** aŭ **kleene-a hierarkio** klasifikas la arojn de aritmetikaj formuloj (aŭ aritmetikaj aroj) laŭ ilia grado de solvebleco. Markotoj en la hierarkio estas difinita tiujn formulojn, kiuj kontentigas propozicion (priskribon) de certa komplekseco.

La algoritmo de Tarski-Kuratowski provizas supera baron por la grado de solvebleco de aritmetika formulo.

## Difino 
La **aritmetika hierarkio** estas tri familioj de kolektoj de aroj (aŭ formuloj) nomitaj kiel \Pi^0_n, \Sigma^0_n, kaj \Delta^0_n, por naturaj nombroj *n*. La kolektoj estas rikure difinita jene:
:\Sigma^0_0 estas la kolekto de rikuraj aroj
:\Sigma^0_{n+1} estas la kolekto de A-rikure numereblaj aroj por A \in \Sigma^0_n
:\Pi^0_n la kolekto de komplementoj de A-rikure numereblaj aroj
:\Delta^0_n := \Sigma^0_n \cap \Pi^0_n estas kolekto de A-rikure numereblaj aroj por A \in \Sigma^0_{n-1}.

Bonvolu noti ke oni devas uzi tiel-nomata \Sigma^0_n-plena aro A por la difino de \Sigma^0_{n+1}-aroj en la kazo ke oni volas uzi nur unu aron A por ĉiu nivelo. Alternative, oni povas ankaŭ diri ke aro B estas \Sigma^0_{n+1}, se ekzistas \Sigma^0_n-aro A tia, ke B estas A-rikure numerebla.

Alternative, ili povas esti difinitaj kiel la kolekto de aritmetikaj formuloj kun iu nombro de kvantizantoj. Formulo estas en la nivelo \Sigma^0_n se ĝi kontentigas propozicion kvantizitan unue per \exists, kaj entute per *n* alternaj ekzistecaj (\exists) kaj universalaj (\forall) natur-nombraj kvantizantoj; formuloj estas klasifikita kiel \Pi^0_n en ekvivalenta maniero, krom se la vico de kvantizantoj komenciĝas per \forall. Aro estas \Sigma^0_n (respektive \Pi^0_n) se kaj nur se ĝi estas difinebla per formulo de tiu komplekseco.

Notu ke malofte senceble estas paroli pri \Delta^0_n-aj formuloj; la unua kvantizanto de la formulo estas aŭ ekzisteca aŭ universala. Do, \Delta^0_n-a aro ne estas difinita per \Delta^0_n-a formulo; male, \Sigma^0_n-formulo kaj \Pi^0_n-formulo *ambaŭ* difinas la aron.

La supra indico indikas la rangon de tiuj objektoj, kiuj estas kvantizitaj; 0 estas por la naturaj nombroj. Kvanigilo de pli alta rango, kiel aroj de naturaj nombroj, estas priskribita per supra indico pli granda ol 0, kiel en la analitika hierarkio. Alivorte, la supra indico 0 indikas logikon de la unua ordo, 1 — logikon de la dua ordo, kaj tiel plu.

## Ekzemploj 
* \Sigma^0_0 = \Pi^0_0 = \Sigma^0_1 \cap \Pi^0_1, la kolekto de rikuraj aroj
* \Sigma^0_1 estas tiuj propozicioj kun unu ekzisteca kvantumilo, \exists x_1 :  propozicio tenas. Ĉi tiuj estas precize la rikure numereblaj aroj.
* Se estas donita gödel-a numerado \varphi_i tiam \{i | \varphi_i \in \mathbf{R}^{(1)}\} \in \Pi^0_2 (la aro de gödel-aj nombroj de la tute komputeblaj funkcioj kun unu parametro)

## Propraĵoj 
* Kolektoj \Pi^0_n kaj \Sigma^0_n estas fermitaj sub finiaj kunaĵoj kaj finiaj komunaĵoj de iliaj respektivaj eroj
* \Delta^0_n \subsetneq \Pi^0_n kaj \Delta^0_n \subsetneq \Sigma^0_n
* \Pi^0_n \subsetneq \Pi^0_{n+1} kaj \Sigma^0_n \subsetneq \Sigma^0_{n+1} (kiu signifas ke la hierarkio ne kolapsas)
* \Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_{n+1}
* \emptyset^{(n)} (la *n*-a salto de Turing de la malplena aro) estas m-plena en \Sigma^0_n
* \mathbb{N} \setminus \emptyset^{(n)} estas m-plena en \Pi^0_n
* \emptyset^{(n-1)} estas turing-a plena aro en \Delta^0_n

## Rilato al turing-aj aŭtomatoj 
Supozu ke estas orakolaj maŝinoj, kiuj povas komputi ĉiujn funkciojn en nivelo \Delta^0_n. Ĉi tiu maŝino estas nekapabla solvi sian propran problemon de haltado (Turing-a pruvo ankoraŭ aplikas). La problemo de haltado por \Delta^0_n fakte estas en \Delta^0_{n+1}.

La teoremo de Post priskribas ligon inter la aritmetika hierarkio kaj la Turing-aj gradoj.

La polinoma hierarkio estas "fareble rimede-barita" versio de la aritmetika hierarkio, en kiu polinom-longaj baroj estas je la propozicioj, aŭ ekvivalente, polinom-tempaj baroj estas je komplikeco la turing-aj aŭtomatoj.

Kategorio:Teorio de efikaj priskribaj aroj
Kategorio:Hierarkio