Peanova aritmetika

Je navrženo začlenit sem veškerý obsah z článku Peanovy axiomy, třeba jako novou část, a oba tak sloučit. (diskuse)
Odtamtud sem pak má vést přesměrování.

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)–(Q8) Robinsonovy aritmetiky a navíc všechny instance následujícího axiomatického schématu pro $\varphi$ formuli jazyka aritmetiky:

• $\left( \varphi(0)\and (\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Ň pro všechna X (platí pro X ⇒ platí pro následníka X), POTOM formule platí pro všechna X.

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

• Peanovy axiomy
• Robinsonova aritmetika
• Presburgerova aritmetika
• Gödelovy věty o neúplnosti