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

## [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.

## [editovat] Podívejte se také na

- Peanova aritmetika
- Robinsonova aritmetika
- Gödelovy věty o neúplnosti

## [editovat] Reference

- Švejdar, V., Logika - neúplnost, složitost, nutnost, Academia, Praha, 2002, ISBN 80-200-1006-X

Citováno z „http://cs.wikipedia.org../../../a/r/i/Aritmetick%C3%A1_hierarchie.html“

Kategorie: Matematická logika | Teorie rekurze | Aritmetika

##### Views

- Článek
- Diskuse
- Aktuální verze

##### Hledání

##### V jiných jazycích

- English
- Esperanto
- Français