Aritmetická hierarchie

Z Wikipedie, otevřené encyklopedie

Aritmetická hierarchie (také Kleeneova hierarchie) je v matematické logice způsob klasifikace podmnožin přirozených čísel s ohledem na složitost formulí, které je definují. Studium aritmetické hierarchie hraje důležitou roli v teorii rekurze a studiu formálních aritmetických teorií jako je například Peanova aritmetika. Aritmetickou hierarchii lze také použít pro elegantní důkaz silnější varianty první Gödelovy věty.

Obsah

1 Definice
- 1.1 Hierarchie formulí
- 1.2 Aritmetická hierarchie
2 Vlastnosti
3 Důsledky nekolapsu aritmetické hierarchie
4 Podívejte se také na
5 Reference

[editovat] Definice

[editovat] Hierarchie formulí

Následující definice má smysl pro formule libovolného jazyka L obsahujícího binární predikátový symbol $\leq$ .

Zápisy $(\forall x\leq y)\varphi$ resp. $(\exists x\leq y)\varphi$ značí formule $(\forall x)(x\leq y \rightarrow \varphi)$ resp. $(\exists x) (x\leq y \wedge \varphi)$ . Říkáme, že tyto formule vznikly omezenou kvantifikací formule $\varphi$ .
Omezené formule jazyka L jsou takové formule tohoto jazyka, které vzniknou z atomických formulí libovolnou aplikací logických spojek a omezené kvantifikace.
Definujeme $\varphi$ je $Σ 0$ resp. $Π 0$ formule, je-li omezená.
Dále indukcí $\varphi$ je $Σ n + 1$ resp. $Π n + 1$ formule, je-li tvaru $(\exists x_1)\ldots(\exists x_k)\psi$ resp. $(\forall x_1)\ldots(\forall x_k)\psi$ , kde $ψ$ je $Π n$ resp. $Σ n$ formule.

[editovat] Aritmetická hierarchie

Množina $A\subseteq \mathbb{N}^k$ se nazývá $Σ n$ resp. $Π n$ množina, existuje-li $Σ n$ resp. $Π n$ formule $\varphi$ s k volnými proměnnými, že $\mathbb{N}\models\varphi(a_1,\ldots,a_k) \Leftrightarrow (a_1,\ldots,a_k)\in A$ (poslední ekvivalenci slovně zkracujeme jako " $\varphi$ definuje A v $\mathbb{N}$ ").
Množina $A\subseteq \mathbb{N}^k$ se nazývá $Δ n$ množina, je-li zároveň $Σ n$ i $Π n$ .
Systémy všech $Σ n$ resp. $Π n$ resp. $Δ n$ množin značíme $Σ n$ resp. $Π n$ resp. $Δ n$ .
Množina se nazývá aritmetická, je-li $Σ n$ pro nějaké n.

[editovat] Vlastnosti

Systémy $Π n$ a $Σ n$ jsou uzavřené na sjednocení a průnik. $Δ n$ je uzavřen na doplněk.
Množina je $Σ n$ , právě když její doplněk je $Π n$ a naopak.
Platí inkluze $\Delta_n \subsetneq \Pi_n$ a $\Delta_n \subsetneq \Sigma_n$ pro $n \geq 1$ a $\Sigma_n \subsetneq \Pi_{n+1}$ a $\Pi_n \subsetneq \Sigma_{n+1}$ pro všechna $n$ .
Dále platí $\Pi_n \subsetneq \Pi_{n+1}$ a $\Sigma_n \subsetneq \Sigma_{n+1}$ pro všechna $n$ a inkluze $\Sigma_n \cup \Pi_n \subsetneq \Delta_{n+1}$ pro $n \geq 1$ . Tedy aritmetická hierarchie nekolapsuje.

[editovat] Důsledky nekolapsu aritmetické hierarchie

Snadným důsledkem tvrzení, že aritmetická hierarchie nekolapsuje, je silnější verze první Gödelovy věty, kterou lze vyslovit takto:

Žádné rekurzivní rozšíření (tj. s rekurzivní množinou axiomů) Peanovy aritemtiky, které má standardní model $\mathbb{N}$ , není úplné.

Jediné úplné rozšíření, které má standardní model, je totiž teorie standardního modelu $Th(\mathbb{N})$ . Stačí nyní ukázat, že $Th(\mathbb{N})$ není rekurzivní. Ukážeme, že dokonce není ani aritmetická. Pokud by totiž byla nějaké $Σ n$ , pak pro každou množinu z $Σ n + 1$ definovanou formulí $\varphi$ by bylo $\varphi(a)\leftrightarrow \overline{\varphi(a)}\in Th(\mathbb{N})$ a formule na pravé straně této ekvivalence je $Σ n$ , tedy i $\varphi$ by bylo $Σ n$ , tj. aritmetická hierarchie by kolapsovala - spor.