Aritmetická hierarchie

Z Wikipedie, otevřené encyklopedie

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.

Obsah

[editovat] Definice

[editovat] 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 Σ0 resp. Π0 formule, je-li omezená.
  • Dále indukcí \varphi je Σn + 1 resp. Πn + 1 formule, je-li tvaru (\exists x_1)\ldots(\exists x_k)\psi resp. (\forall x_1)\ldots(\forall x_k)\psi, kde ψ je Πn resp. Σn formule.

[editovat] Aritmetická hierarchie

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

[editovat] Vlastnosti

  • Systémy Πn a Σn jsou uzavřené na sjednocení a průnik. Δn je uzavřen na doplněk.
  • Množina je Σn, právě když její doplněk je Π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.

[editovat] 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é Σn, pak pro každou množinu z Σ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 Σn, tedy i \varphi by bylo Σn, tj. aritmetická hierarchie by kolapsovala - spor.

[editovat] Podívejte se také na

[editovat] Reference

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