] >
Het getal is geen opvolger van een natuurlijk getal. In feite is het het enige natuurlijke getal met die eigenschap. Dat staat niet in de axioma’s. Je kunt het wel uit de axioma’s afleiden. Zo’n afleiding noemen we een bewijs. In een bewijs moet iedere uitspraak volgen uit de axioma’s en eerder bewezen uitspraken.
Bewijs. We bewijzen dat ieder natuurlijk getal een opvolger is. Beschouw de eigenschap
Duidelijk is dat geldt.
Zij een natuurlijk getal waarvoor geldt. Omdat een opvolger is geldt ook .
Dus: geldt voor iedere waarvoor geldt. Uit axioma (N3) volgt dat geldt voor alle . □
Dit bewijs is nogal formeel. Als je begrijpt dat ieder natuurlijk getal met tellen vanaf wordt bereikt, dan is het je al duidelijk.
Om in dit bewijs te laten zien dat volgt uit voor alle , beginnen we met de veronderstelling dat geldt voor een zekere, maar verder willekeurige . Met die vaste redeneren we verder. Zolang de tekst is ingesprongen redeneren we met deze ene vaste . Voor deze leiden we af dat ook geldt. Dan springen we terug en concluderen—die is immers willekeurig—dat voor iedere met ook geldt.
Schematisch gaat een bewijs met volledige inductie als volgt.
volledige inductie
| |
Dus .
| |
Stel is een natuurlijk getal met . | |
Dus . | |
Dus voor alle met .
| |
Met volledige inductie volgt dat voor alle .
| |
De plaatsen waar puntjes () staan zijn voor redeneringen die de erop volgende conclusie rechtvaardigen.
Binnen dit schema voor volledige inductie is een deelschema aanwezig. Laat een verzameling zijn. Om een uitspraak ‘ voor alle ’ te bewijzen kun je een willekeurig element van nemen en de uitspraak bewijzen (voor deze overigens willekeurige ).
alle | |
Zij . | |
Dus . | |
Dus voor alle .
| |
Omdat we van alleen maar gebruiken dat het een element van is, gaat de redenering die tot leidt op voor alle . Bij volledige inductie is de verzameling en de uitspraak .
In het vorige hoofdstuk zagen we in dat de Toren van Hanoi oplosbaar is voor ieder aantal schijven. We deden dat door naar de graaf van deze puzzel te kijken, en vooral naar het verband tussen de graaf en de graaf voor één schijf meer. Deze grafen vertellen meer dan de oplosbaarheid van de puzzel alleen. We kijken nu alleen naar de oplosbaarheid. De oplosbaarheid van de puzzel met schijven kun je zien als een eigenschap van het natuurlijke getal :
Met volledige inductie laten we zien dat de puzzel voor ieder aantal schijven oplosbaar is.
Bewijs. geldt, dat is duidelijk.
Laat een natuurlijk getal zijn waarvoor geldt. We laten zien dat dan ook geldt. We nemen aan dat alle schijven op pin staan en laten zien dat ze volgens de regels naar pin verplaatst kunnen worden. Omdat geldt kunnen we door het doen van zetten alle schijven met uitzondering van de grootste op pin krijgen. Vanuit kunnen we dus de stand bereiken. Vervolgens verplaatsen we de grootste schijf. De stand is dan . De grootste schijf staat dan op pin . Omdat geldt kunnen we ook de resterende schijven op pin krijgen.
Voor ieder natuurlijk getal met geldt dus ook . Omdat ook geldt, geldt dus met volledige inductie voor alle . □