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 ${\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.

Aritmetická hierarchie

• 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.

Vlastnosti

• 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.

Důsledky nekolapsu aritmetické hierarchie

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.

Literatura

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

Související články

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