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.
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
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
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
Snadným důsledkem tvrzení, že aritmetická hierarchie nekolabuje, je silnější verze první Gödelovy věty, kterou lze vyslovit takto:
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.
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.