Cesko.wiki Peanova aritmetika
Author
Albert FloresPeanova 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á). +more 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.