Peanoaritmetik

Peanoaritmetik (ibland förkortat PA) är inom talteorin ett sätt att konstruera de naturliga talen N, samt addition och multiplikation med hjälp av Peanos axiom. Peanoaritmetiken kan ses som en sluten algebraisk struktur (N, +, 0, ·, 1), där 0 och 1 är neutrala element för addition respektive multiplikation.

Formulering av de naturliga talen

Peanoaritmetiken behandlar de aritmetiska egenskaperna hos de naturliga talen, ofta representerade av en mängd N (ibland dubbeltecknat, $\mathbb {N}$). Peanos axiom definierar dessa tal genom en konstant 0 och en ”efterföljarfunktion” (eng. successor function) S sådan att S(n) ger det på n efterföljande talet (S(0) ger 1, S(1) ger 2, etc.). I moderna anpassningar har Peanos ursprungliga nio axiom reducerats till fem, ty fyra av dem endast beskriver underförstådda egenskaper hos likhet. Dessa fem är:

1. 0 är ett naturligt tal.
2. För varje naturligt tal n så är S(n) ett naturligt tal. Den naturliga talmängden är sluten under S.
3. För alla naturliga tal m och n, så är S(m)=S(n) om och endast om m = n. S är en injektiv funktion.
4. Det finns inget naturligt tal n sådant att S(n) = 0.
5. Om K är en mängd sådan att

• K innehåller 0, och
• för varje naturligt tal n, om K innehåller n så innehåller K också S(n)

så innehåller K alla naturliga tal.

För att visa att K innehåller S(n), så räcker det att veta att K innehåller n. Det femte axiomet ger alltså ett sätt att definiera den naturliga talmängden genom matematisk induktion.

Definition av operatorer

Med hjälp av efterföljarfunktionen S kan man definiera addition och multiplikation som binära funktioner. De tar två element i N och ger tillbaka ett tredje; de naturliga talen är således slutna under addition och multiplikation.

Addition

Addition definieras rekursivt som

$a+0=a,$

$a+S(b)=S(a+b).$

Till exempel,

$3+2=3+S(1)=S(3+1)=S(3+S(0))=S(S(3+0))=S(S(3))=S(4)=5.$

Multiplikation

Givet addition definieras multiplikation rekursivt som

$a\cdot 0=0,$

$a\cdot S(b)=a+(a\cdot b).$

Till exempel,

$4\cdot 1=4\cdot S(0)=4+(4\cdot 0)=4+0=4.$

Då man låter 0 vara det neutrala elementet för addition följer att 1 är det neutrala elementet för multiplikation. Vidare uppvisar både addition och multiplikation här kommutativa och associativa egenskaper, och multiplikation är distributiv över addition. Den algebraiska strukturen (N, +, 0, ·, 1) bildar således en kommutativ halvring.

Axiomatisering med första ordningens logik

Inom logisk analys är det önskvärt att uttrycka Peanoaritmetik med hjälp av första ordningens logik, då det underlättar vid exempelvis bevisteori. Det är då nödvändigt att låta addition och multiplikation vara en del av axiomen, istället för att definiera dem med hjälp av efterföljarfunktionen. De nya axiomen består delvis av några av de ursprungliga axiomen, delvis av definitionerna för addition och multiplikation ovan.

1. $\forall x\in N.\ S(x)\neq 0$
2. $\forall x,y\in N.\ S(x)=S(y)\Rightarrow x=y$
3. $\forall x\in N.\ x+0=x$
4. $\forall x,y\in N.\ x+S(y)=S(x+y)$
5. $\forall x\in N.\ x\cdot 0=0$
6. $\forall x,y\in N.\ x\cdot S(y)=x+(x\cdot y)$

Att konstatera att en mängd som innehåller 0 och efterföljaren av alla tal i mängden innehåller alla naturliga tal är inte heller möjligt utan andra ordningens logik. Lösningen är att omvandla det ursprungliga femte axiomet till ett första ordningens axiomschema som gäller för alla naturliga tal:

• Om φ(n) är en sats sådan att
  • φ(n) = 0 är sann, och
  • för varje naturligt tal n, om φ(n) är sann, så är också φ(S(n)) sann

så är φ(n) sann för alla naturliga tal.

Detta ger ett axiom för varje tal n och totalt ett oändligt men uppräkneligt antal axiom; man säger då att systemet inte är ändligt axiomatiserat.

Källor

• Hofstadter, Douglas R., 1985. Gödel, Escher, Bach : ett evigt gyllene band. Svensk uppl. Stockholm: Bromberg.
• van Oosten, Jaap, Introduction to Peano Arithmetic - Gödel Incompleteness and Nonstandard Models http://www.staff.science.uu.nl/~ooste110/syllabi/peanomoeder.pdf (Hämtad 5 maj 2015)
• Weisstein, Eric W. "Peano Arithmetic." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PeanoArithmetic.html (Hämtad 5 maj 2015)
• Weisstein, Eric W. "Peano's Axioms." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PeanosAxioms.html (Hämtad 5 maj 2015)