Axioma's van Peano

In de wiskundige logica zijn de axioma's van Peano (ook bekend als de axioma's van Dedekind-Peano of de postulaten van Peano) een verzameling axioma's voor de natuurlijke getallen, geformuleerd door de 19e-eeuwse Italiaanse wiskundige Giuseppe Peano. Deze axioma's zijn in vrijwel onveranderde vorm in een aantal metawiskundige onderzoekingen gebruikt, waaronder fundamenteel onderzoek naar de consistentie en volledigheid van de getaltheorie.

De behoefte aan formalisme in de rekenkunde werd niet op waarde geschat tot het werk van Hermann Grassmann, die in de jaren 1860 liet zien dat veel feiten in de rekenkunde kunnen worden afgeleid uit fundamentele eigenschappen van de opvolgeroperatie en de methode van de volledige inductie. In 1888 stelde Richard Dedekind een collectie van axioma's voor over de getallen, en in 1889 publiceerde Peano een meer precies geformuleerde versie ervan als een collectie van axioma's in zijn boek, Arithmetices principia, nova methodo exposita (Latijn voor: De beginselen van de rekenkunde op een nieuwe methode gepresenteerd).

De axioma's van Peano bevatten drie typen van uitspraken. De eerste vier uitspraken zijn algemene uitspraken over gelijkheid; in moderne behandelingen worden deze uitspraken vaak gezien als axioma's van pure logica. De volgende vier axioma's zijn uitspraken binnen de predicatenlogica, zij gaan over de natuurlijke getallen, die de fundamentele eigenschappen van de opvolgeroperatie uitdrukken. Het negende en laatste axioma legt de methode van volledige inductie over de natuurlijke getallen vast. Een zwakker eerste-orde systeem, dat Peano-rekenkunde wordt genoemd, wordt verkregen door dit tweede-orde inductie-axioma te vervangen door een eerste-orde axiomaschema.

De axioma's van Peano

De taal waarin de axioma's van Peano worden opgeschreven bevat het getal 0 en een eenplaatsig functiesymbool $S$ (de opvolgerfunctie).

Ten eerste wordt gesteld dat 0 een natuurlijk getal is.

1. 0 is een natuurlijk getal.

De volgende vier axioma's definiëren gelijkheid. Axioma's 2-4 zeggen dat gelijkheid reflexief, symmetrisch en transitief is. Axioma 5 zegt dat de verzameling van de natuurlijke getallen onder gelijkheid gesloten is.

2. Voor alle natuurlijke getallen $x$ geldt: $x=x$.
3. Voor alle natuurlijke getallen $x$ en $y$ geldt: als $x=y$ dan $y=x$.
4. Voor alle natuurlijke getallen $x,\,y$ en $z$ geldt: als $x=y$ en $y=z$, dan $x=z$.
5. Voor alle $a$ en $b$ geldt: als $a$ een natuurlijk getal is en $a=b$, dan is $b$ ook een natuurlijk getal.

Vervolgens worden de eigenschappen van de opvolgerfunctie $S$ gedefinieerd.

6. Voor elk natuurlijk getal $x$ geldt, dat $S(x)$ ook een natuurlijk getal is.
7. Voor elke $x$ geldt, dat $S(x)=0$ onwaar is.
8. Voor alle natuurlijke getallen $x$ en $y$ geldt: als $S(x)=S(y)$, dan $x=y$.

Het laatste axioma is het inductieaxioma, dat de bewijzen met behulp van volledige inductie mogelijk maakt:

9. Elke verzameling $N$, waarvoor geldt dat
   • $0\in N$
   • als $x\in N$ dan $S(x)\in N$

bevat alle natuurlijke getallen.

Het inductieaxioma wordt gekwantificeerd over verzamelingen; dat maakt het een tweede-orde-axioma. Eerste-orde-axioma's, waarin alleen over natuurlijke getallen en niet over verzamelingen wordt gekwantificeerd, zijn in de praktijk handiger. Daarom wordt het inductieaxioma vaak vervangen door een axiomaschema, waardoor aftelbaar oneindig veel axioma's ontstaan. De eerste-orde-Peano-axioma's zijn echter echt zwakker dan de tweede-orde-Peano-axioma's.

Peano-rekenkunde

Met behulp van tweede-orde-logica kunnen de gebruikelijke rekenkundige operaties worden gedefinieerd.

Optelling

De optelling is de (unieke) binaire operatie ${+}\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N}$ waarvoor geldt:

$x+0=x$

$x+S(y)=S(x+y)$

Deze relaties houden een recursie in:

$x+0=x$

$x+1=x+S(0)=S(x+0)=S(x)$

$x+2=x+S(1)=S(x+1)=S(S(x))$

$x+3=x+S(2)=S(x+2)=S(S(S(x)))$

enz.

De zo gedefinieerde optelling heeft 0 als neutraal element en is commutatief en associatief.

Neutraal element

Voor het getal 0 geldt ook:

$0+x=x$

Immers met inductie:

$0+0=0$

en stel voor zekere $x$ geldt:

$0+x=x$

dan volgt

$0+S(x)=S(0+x)=S(x)$

De optelling is commutatief

Hulpstelling:

$S(x+y)=S(x)+y$

Met inductie naar $y$:

$S(x+0)=S(x)=S(x)+0$

Stel voor alle $x$ en zekere $y$

$S(x+y)=S(x)+y$

dan

$S(x+S(y))=S(S(x+y))=S(S(x)+y)=S(x)+S(y)$

Commutativiteit:

$x+y=y+x$

Met inductie naar $y$:

$x+0=0+x$

Stel voor alle $x$ en zekere $y$

$x+y=y+x$

dan met de hulpstelling

$x+S(y)=S(x+y)=S(y+x)=S(y)+x$

De optelling is associatief

$(x+y)+z=x+(y+z)$

Met inductie naar $z$:

$(x+y)+0=x+y=x+(y+0)$

Stel voor alle $x,y$ en zekere $z$

$(x+y)+z=x+(y+z)$

dan

$(x+y)+S(z)=S((x+y)+z)=S(x+(y+z))=x+S(y+z)=$

$=x+S(z+y)=x+(S(z)+y)=x+(y+S(z))$

Vermenigvuldiging

De vermenigvuldiging is de (unieke) binaire operatie $\cdot \,\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N}$ waarvoor geldt:

$x\cdot 0=0$

$x\cdot S(y)=x+(x\cdot y)$

De vermenigvuldiging $2\cdot 2$ kan dan bijvoorbeeld als volgt worden uitgerekend:

$S(S(0))\cdot S(S(0))=S(S(0))+{\big (}S(S(0))\cdot S(0){\big )}=$

$=S(S(0))+{\big (}S(S(0))+(S(S(0){\big )}\cdot 0)=$

$=S(S(0))+S(S(0))+0=$

$=\ldots =S(S(S(S(0))))$

De definiërende relaties houden de volgende recursie in:

$x\cdot 0=0$

$x\cdot 1=x\cdot S(0)=x+(x\cdot 0)=x+0=x$

$x\cdot 2=x\cdot S(1)=x+(x\cdot 1)=x+x$

$x\cdot 3=x\cdot S(2)=x+(x\cdot 2)=x+(x+x)$

enz.

Hieruit blijkt ook dat vermenigvuldigen herhaald optellen is. Ook blijkt overzichtelijker:

$2\cdot 2=2+2=(2+1)+1=3+1=4$

De zo gedefinieerde vermenigvuldiging heeft 1 als eenheidselement en is distritief over de optelling, en commutatief en associatief.

Eenheidselement

Voor het getal 1 geldt ook:

$1\cdot x=x$

Immers met inductie:

$1\cdot 0=0$

en stel voor zekere $x$ geldt:

$1\cdot x=x$

dan volgt

$1\cdot S(x)=1+1\cdot x=1+x=S(x)$

In de volgende bewijzen is voor het gemak de punt van de vermenigvuldiging weggelaten.

Distributiviteit

$x(y+z)=xy+xz$

Met inductie naar $z$:

$x(y+0)=xy=xy+x0$

en stel voor alle $x,y$ en zekere $z$ geldt:

$x(y+z)=xy+xz$

dan

$x(y+S(z))=xS(y+z)=x+x(y+z)=x+xy+xz=xy+x+xz=xy+xS(z)$

Verder geldt ook:

$(x+y)z=xz+yz$

want

$(x+y)0=0=x0+y0$

en stel voor alle $x,y$ en zekere $z$ geldt:

$(x+y)z=xz+yz$

dan

$(x+y)S(z)=(x+y)+(x+y)z=(x+y)+(xz+yz)=x+xz+y+yz=xS(z)+yS(z)$

De vermenigvuldiging is commutatief

Hulpstelling:

$0\,x=0$

Met inductie naar $x$:

$0\cdot 0=0$

Stel voor zekere $x$

$0\,x=0$

dan

$0\,S(x)=0+0\,x=0+0=0$

Commutativiteit:

$xy=yx$

Met inductie naar $y$:

$x\,0=0=0\,x$

en stel voor alle $x$ en zekere $y$ geldt:

$xy=yx$

dan

$xS(y)=x+xy=x+yx=(1+y)x=S(y)x$

De vermenigvuldiging is associatief

$(xy)z=x(yz)$

Met inductie naar $z$:

$(xy)0=0=x(y0)$

Stel voor alle $x,y$ en zekere $z$

$(xy)z=x(yz)$

dan

$(xy)S(z)=xy+(xy)z=xy+x(yz)=x(y+yz)=x(yS(z))$

Ordening

De gebruikelijke ordening ${\leq }\in \mathbb {N} \times \mathbb {N}$ kan als volgt worden gedefinieerd:

$x\leq y$ als er een $z$ is zodat $x+z=y$.

Eerste-orde-Peano-rekenkunde

Functies en relaties kunnen alleen met tweede-orde-logica worden gedefinieerd. Peano-rekenkunde kan echter ook met de eerste-orde-Peano-axioma's worden gebruikt. Daarvoor moet de taal worden uitgebreid met de symbolen $\ +,\ \cdot \$ en $\ \leq \$ en moeten de bovenstaande vergelijkingen als axioma's worden ingevoerd.