Peanova aritmetika

Peanova aritmetika (PA) je jeden z axiomatických systémů formální teorie aritmetiky. Jde o jednu z nejdůležitějších součástí matematické logiky — slouží například k důkazu slavných Gödelových vět o neúplnosti. Rozšiřuje axiomatiku Robinsonovy aritmetiky o axiomatické schéma indukce. Pojmenována je po italském matematikovi Giuseppem Peanovi.

Axiomy

(PA) je teorie v jazyce aritmetiky. Jejími axiomy jsou axiomy (Q1)–(Q7) Robinsonovy aritmetiky a navíc všechny instance následujícího axiomatického schématu pro formuli $\varphi$ jazyka aritmetiky:

$\left(\varphi (0)\land (\forall x)(\varphi (x)\rightarrow \varphi (Sx))\right)\rightarrow (\forall x)\varphi (x)$ (schéma indukce)

Slovy: Pokud formule platí pro $0$ a zároveň z platnosti formule pro $x$ plyne platnost pro následníka $x$ potom formule platí pro všechna $x$ .

Jelikož toto schéma kvantifikuje přes formule $\varphi$ , což na logické úrovni odpovídá predikátům, tak predikátová logika prvního řádu není dostatečně expresivní pro formalizaci Peanovy aritmetiky a je nutné použít nějakou logiku vyššího řádu. To má praktické důsledky například při snahách o formalizaci aritmetiky pro automatické dokazovače a proof assistanty.

Vlastnosti

Peanova aritmetika je neúplná a dokonce rekurzivně nezúplnitelná teorie (tj. každá její nadteorie s rekurzivně zadanou množinou axiomů je neúplná). To je tvrzení první Gödelovy věty.
Peanova aritmetika má $2^{\aleph _{0}}$ (viz funkce alef) různých úplných rozšíření.
Peanova aritmetika je nerozhodnutelná teorie.
V Peanově aritmetice jsou nedokazatelná následující tvrzení:
- „Peanova aritmetika je bezesporná“. To říká druhá Gödelova věta.
- Goodsteinova věta
- Jisté silnější verze Ramseyovy věty.
V Peanově aritmetice jsou dokazatelné všechny základní vlastnosti přirozených čísel jako jsou:
- komutativita a asociativita + a $\cdot$
- distributivita + vzhledem k $\cdot$
- linearita uspořádání $\leq$
- existence a jednoznačnost dělení se zbytkem
V Peanově aritmetice je definovatelná funkce $x^{y}$ , o které jsou dokazatelné všechny její přirozené vlastnosti.
V Peanově aritmetice lze vyjádřit základní pojmy logické syntaxe i sémantiky jako jsou dokazatelnost nebo bezespornost.
Peanova aritmetika je ekvivalentní teorii konečných množin (tj. Zermelo-Fraenkelově teorii množin, v níž je axiom nekonečna nahrazen jeho negací).
První Stoneův prostor Peanovy aritmetiky má mohutnost kontinua.
Peanova aritmetika nemá spočetný saturovaný model.

Související články