Aritmetika hierarkio

El Vikipedio

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 tarski-kuratowski-a algoritmo provizas supera baron por la grado de solvebleco de aritmetika formulo.

[redaktu] 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 rekursie difinita kiel

$\Sigma^0_0$ estas la kolekto de rekursiaj aroj

$\Sigma^0_{n+1}$ estas la kolekto de A-rekursie numerigeblaj aroj por $A \in \Sigma^0_n$

$\Pi^0_n$ la kolekto de komplementoj de A-rekursie numerigeblaj aroj

$\Delta^0_n := \Sigma^0_n \cap \Pi^0_n$ estas kolekto de A-rekursie numerigeblaj aroj por $A \in \Sigma^0_{n-1}$ .

Bonvolu noti ke oni devas uzi tiel-nomata $\Sigma^0_n$ -plena aro A por la defino 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 tiel kiel B estas A-rekursie numerigebla.

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

Estas noto ke malofte estas senco paroli pri $\Delta^0_n$ -aj formuloj; la unua kvantumilo de formulo estas aŭ ekzisteca aŭ universala. Do $\Delta^0_n$ -a aro estas ne difinita per $\Delta^0_n$ -a formulo; iom, estas $\Sigma^0_n$ formulo kaj $\Pi^0_n$ -a formulo, kiuj ambaŭ difinas la aron.

La supra indico indikas la tipon de la objektoj kiuj estas kvantigita, 0 estas por la naturaj nombroj. Kvantoro de pli alta tipo, kiel aroj de naturaj nombroj, estas priskribita per supra indico pli granda ol 0, kiel en la analitika hierarkio. En alia vortoj, la supra indico 0 indikas logikon de la unua ordo, 1 - logikon de la dua ordo, kaj tiel plu.

[redaktu] Ekzemploj

$\Sigma^0_0 = \Pi^0_0 = \Sigma^0_1 \cap \Pi^0_1$ , la kolekto de rekursiaj aroj

$\Sigma^0_1$ estas tiuj propozicioj kun unu ekzisteca kvantumilo, $\exists x_1 :$ propozicio tenas. Ĉi tiuj estas precize la rekursie numerigeblaj 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)

[redaktu] 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$

[redaktu] Rilato al turing-aj aŭtomatoj

Supozu ke estas orakolaj maŝinaj povaj kalkuli ĉiujn funkciojn en nivelo $\Delta^0_n$ . Ĉi tiu maŝino estas nekapabla solvi sian propran problemon de haltado (Turing-a's pruvo ankoraŭ aplikas). La problemo de haltado por $\Delta^0_n$ fakte estas en $\Delta^0_{n+1}$ .

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.

Elŝutita el "http://eo.wikipedia.org../../../a/r/i/Aritmetika_hierarkio.html"

Kategorioj: Teorio de efikaj priskribaj aroj | Hierarkio