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
.
- 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 Σ0 resp. Π0 formule, je-li omezená. - Dále indukcí
je Σn + 1 resp. Πn + 1 formule, je-li tvaru
resp.
, kde ψ je Πn resp. Σn formule.
[editovat] Aritmetická hierarchie
- Množina
se nazývá Σn resp. Πn množina, existuje-li Σn resp. Πn formule
s k volnými proměnnými, že
(poslední ekvivalenci slovně zkracujeme jako "
definuje A v
"). - Množina
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
a
pro
a
a
pro všechna n. - Dále platí
a
pro všechna n a inkluze
pro
. 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
, 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é Σn, pak pro každou množinu z Σn + 1 definovanou formulí
by bylo
a formule na pravé straně této ekvivalence je Σn, tedy i
by bylo Σn, tj. aritmetická hierarchie by kolapsovala - spor.

