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 .

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

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

Vlastnosti[editovat | editovat zdroj]

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

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.

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]