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.

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

• Zápisy ${\displaystyle (\forall x\leq y)\varphi }$ resp. ${\displaystyle (\exists x\leq y)\varphi }$ značí formule ${\displaystyle (\forall x)(x\leq y\rightarrow \varphi )}$ resp. ${\displaystyle (\exists x)(x\leq y\wedge \varphi )}$. Říkáme, že tyto formule vznikly omezenou kvantifikací formule ${\displaystyle \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 ${\displaystyle \varphi }$ je ${\displaystyle \Sigma _{0}}$ resp. ${\displaystyle \Pi _{0}}$ formule, je-li omezená.
• Dále indukcí ${\displaystyle \varphi }$ je ${\displaystyle \Sigma _{n+1}}$ resp. ${\displaystyle \Pi _{n+1}}$ formule, je-li tvaru ${\displaystyle (\exists x_{1})\ldots (\exists x_{k})\psi }$ resp. ${\displaystyle (\forall x_{1})\ldots (\forall x_{k})\psi }$, kde ${\displaystyle \psi }$ je ${\displaystyle \Pi _{n}}$ resp. ${\displaystyle \Sigma _{n}}$ formule.

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

• Systémy ${\displaystyle \Pi _{n}}$ a ${\displaystyle \Sigma _{n}}$ jsou uzavřené na sjednocení a průnik. ${\displaystyle \Delta _{n}}$ je uzavřen na doplněk.
• Množina je ${\displaystyle \Sigma _{n}}$, právě když její doplněk je ${\displaystyle \Pi _{n}}$ a naopak.
• Platí inkluze ${\displaystyle \Delta _{n}\subsetneq \Pi _{n}}$ a ${\displaystyle \Delta _{n}\subsetneq \Sigma _{n}}$ pro ${\displaystyle n\geq 1}$ a ${\displaystyle \Sigma _{n}\subsetneq \Pi _{n+1}}$ a ${\displaystyle \Pi _{n}\subsetneq \Sigma _{n+1}}$ pro všechna ${\displaystyle n}$.
• Dále platí ${\displaystyle \Pi _{n}\subsetneq \Pi _{n+1}}$ a ${\displaystyle \Sigma _{n}\subsetneq \Sigma _{n+1}}$ pro všechna ${\displaystyle n}$ a inkluze ${\displaystyle \Sigma _{n}\cup \Pi _{n}\subsetneq \Delta _{n+1}}$ pro ${\displaystyle n\geq 1}$. Tedy aritmetická hierarchie nekolabuje.

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

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

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

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

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