Aritmetická hierarchie

Související obrázek 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. +more (\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. +more \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. +more * 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 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 \mathbb{N}, není úplné. +more 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 kolabovala - spor.

Literatura

Švejdar, V., Logika - neúplnost, složitost, nutnost, Academia, Praha, 2002,

Související články

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

Kategorie:Matematická logika Kategorie:Aritmetika Kategorie:Vyčíslitelnost