Aritmetická hierarchie

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Hierarchie formulí[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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 aritmetiky, 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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]