Aritmetická hierarchie

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.

Definice

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 $\Sigma_0$ resp. $\Pi_0$ formule, je-li omezená.
• Dále indukcí $\varphi$ je $\Sigma_{n+1}$ resp. $\Pi_{n+1}$ formule, je-li tvaru $(\exists x_1)\ldots(\exists x_k)\psi$ resp. $(\forall x_1)\ldots(\forall x_k)\psi$, kde $\psi$ je $\Pi_{n}$ resp. $\Sigma_{n}$ formule.

Aritmetická hierarchie

• Množina $A\subseteq \mathbb{N}^k$ se nazývá $\Sigma_n$ resp. $\Pi_n$ množina, existuje-li $\Sigma_n$ resp. $\Pi_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á $\Delta_n$ množina, je-li zároveň $\Sigma_n$ i $\Pi_n$.
• Systémy všech $\Sigma_n$ resp. $\Pi_n$ resp. $\Delta_n$ množin značíme $\Sigma_n$ resp. $\Pi_n$ resp. $\Delta_n$.
• Množina se nazývá aritmetická, je-li $\Sigma_n$ pro nějaké n.

Vlastnosti

• Systémy $\Pi_n$ a $\Sigma_n$ jsou uzavřené na sjednocení a průnik. $\Delta_n$ je uzavřen na doplněk.
• Množina je $\Sigma_n$, právě když její doplněk je $\Pi_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.

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é $\Sigma_n$, pak pro každou množinu z $\Sigma_{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 $\Sigma_n$, tedy i $\varphi$ by bylo $\Sigma_n$, tj. aritmetická hierarchie by kolapsovala - spor.

Související články

• Peanova aritmetika
• Robinsonova aritmetika
• Gödelovy věty o neúplnosti

Reference

• Švejdar, V., Logika - neúplnost, složitost, nutnost, Academia, Praha, 2002, ISBN 80-200-1006-X