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.

Související obrázek

DefiniceEditovat

Hierarchie formulíEditovat

Následující definice má smysl pro formule libovolného jazyka L obsahujícího binární predikátový symbol  .

  • Zápisy   resp.   značí formule   resp.  . Říkáme, že tyto formule vznikly omezenou kvantifikací formule  .
  • Omezené formule jazyka L jsou takové formule tohoto jazyka, které vzniknou z atomických formulí libovolnou aplikací logických spojek a omezené kvantifikace.
  • Definujeme   je   resp.   formule, je-li omezená.
  • Dále indukcí   je   resp.   formule, je-li tvaru   resp.  , kde   je   resp.   formule.

Aritmetická hierarchieEditovat

  • Množina   se nazývá   resp.   množina, existuje-li   resp.   formule   s k volnými proměnnými, že   (poslední ekvivalenci slovně zkracujeme jako "  definuje A v  ").
  • Množina   se nazývá   množina, je-li zároveň   i  .
  • Systémy všech   resp.   resp.   množin značíme   resp.   resp.  .
  • Množina se nazývá aritmetická, je-li   pro nějaké n.

VlastnostiEditovat

  • Systémy   a   jsou uzavřené na sjednocení a průnik.   je uzavřen na doplněk.
  • Množina je  , právě když její doplněk je   a naopak.
  • Platí inkluze   a   pro   a   a   pro všechna  .
  • Dále platí   a   pro všechna   a inkluze   pro  . Tedy aritmetická hierarchie nekolabuje.

Důsledky nekolapsu aritmetické hierarchieEditovat

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  , není úplné.

Jediné úplné rozšíření, které má standardní model, je totiž teorie standardního modelu  . Stačí nyní ukázat, že   není rekurzivní. Ukážeme, že dokonce není ani aritmetická. Pokud by totiž byla nějaké  , pak pro každou množinu z   definovanou formulí   by bylo   a formule na pravé straně této ekvivalence je  , tedy i   by bylo  , tj. aritmetická hierarchie by kolabovala - spor.

LiteraturaEditovat

Související článkyEditovat