Peanoaritmetiek

Peanoaritmetiek, ook wel de Peano-axioma’s genoemd, is de eerste-orde theorie van de natuurlijke getallen gebaseerd op de Peano-axioma’s. De taal bevat 0, de successor-functie S en via definities de bewerkingen optellen en vermenigvuldigen. De kern bestaat uit de Peano-axioma’s: (1) 0 is een natuurlijk getal; (2) voor ieder getal n is er een successor S(n); (3) 0 is niet de successor van enig getal; (4) verschillende getallen hebben verschillende successors; (5) inductie: voor elke eigenschap φ geldt als φ(0) en ∀n(φ(n) → φ(S(n))) dat ∀n φ(n). Additionele definities voor optellen en vermenigvuldigen worden meestal gegeven via recursieve regels: x+0 = x; x+S(y) = S(x+y); x·0 = 0; x·S(y) = x·y + x.

In de standaard eerste-orde Peano-aritmetiek (PA) worden deze axioma’s aangevuld met een inductieschema: voor elke formule φ(n) geldt dat φ(0) en ∀n(φ(n) → φ(S(n))) ⇒ ∀n φ(n). Addition en vermenigvuldiging kunnen als primitieve symbolen worden opgenomen of als definities via de recursieve regels. PA is niet finitair axiomatiseerbaar doordat het inductieschema oneindig is, zelfs als de taal beperkt blijft.

Historisch gezien werd Peanoaritmetiek ontwikkeld door Giuseppe Peano in de late 19e eeuw als formeel fundament voor de getallen. Het vormt de basis voor het formeel redeneren over natuurlijke getallen en dient als uitgangspunt voor de wiskundige logica en de grondslagen van de wiskunde. In de logica tonen Gödel’s onvolledigheidsstellingen aan dat elke consistente, effectively axiomatiseerbare theorie die genoeg rekenskundige uitspraken kan uitdrukken, onvolledig is; dus bevat PA ware maar onbewijsbare stellingen. Deze resultaten hebben geleid tot verdere systemen en discussies over de fundamentos van de wiskunde.