Submitted by jonas on
Als in een rij dominostenen de eerste steen omgegooid wordt, volgt de rest. Zo werkt ook het principe van volledige inductie. Veronderstel dat men wil bewijzen dat een bepaalde eigenschap of formule geldt voor alle natuurlijke getallen $n$. Dan moet men twee dingen bewijzen. Eerst en vooral dat het geldt voor het getal $1$, de eerste dominosteen. Daarna moet men bewijzen dat alle dominostenen dicht genoeg bij elkaar staan zodanig dat als er één omvalt, ook de volgende de grond zal raken. Men moet bewijzen dat als de eigenschap geldt voor een getal $k$, dan ook voor het getal $k+1$. Hieruit volgt dan dat de eigenschap geldt voor $1$, maar dan ook voor $1+1 = 2$, en bijgevolg ook voor $2+1 = 3$. Zo verdergaand geldt de eigenschap voor elk natuurlijk getal.
Bij de bespreking van de hoofdstelling van de rekenkunde hebben we reeds uitgebreid uitgelegd hoe de natuurlijke getallen het bloed zijn dat door de aderen van de wiskunde stroomt. Het hoeft dan ook niet te verbazen dat het belangrijkste onderdeel van dit bloed, het principe van de volledige inductie, zeer hoog genoteerd staat in deze lijst.
In 1889 publiceerde de Italiaanse wiskundige Guiseppe Peano wat nu gekend staat als de Peano-axioma's. Dit is een stel axioma's voor de theorie van de natuurlijke getallen. Wie deze axioma's bekijkt zal onmiddellijk iets opvallen. Ze zijn bedrieglijk eenvoudig. Al wat de eerste axioma's beschrijven is het feit dat er een gelijkheidsrelatie '$=$' bestaat voor natuurlijke getallen en dat de verzameling van de natuurlijke getallen eruit ziet zoals wij hem kennen, namelijk $\{0, 1, 2, \ldots\}$. Er wordt met geen woord gerept over optelling, vermenigvuldiging, deelbaarheid, priemgetallen enzovoort. Het enige axioma dat een niet-triviale inhoud heeft is het axioma van de volledige inductie, dat dus het principe van de volledige inductie oplegt aan de natuurlijke getallen.
Dit toont meteen aan hoe ongelofelijk fundamenteel dit principe is. Met behulp van inductie kan men het volledige gekende arsenaal aan eigenschappen van de natuurlijke getallen afleiden. Men kan de bewerkingen optelling, aftrekking, vermenigvuldiging en deling definiëren. De ganse theorie van de natuurlijke getallen zoals wij die kennen steunt in feite op dit ene axioma, volledige inductie. Hoe onvoorstelbaar het ook mag lijken, elke stelling uit de elementaire getaltheorie (en nog vele andere stellingen), kunnen bewezen worden door enkel en alleen de structuur van de verzameling $\{0, 1, 2, \ldots\}$ en het principe van de volledige inductie te gebruiken.
Maar hier stopt het niet bij. Volledige inductie wordt ook gebruikt ver buiten het domein van de elementaire getaltheorie. Het aantal bewijzen dat steunt op volledige inductie is ontelbaar. En vele bewijzen zouden ondenkbaar zijn zonder dit principe. Inductie levert vaak een relatief eenvoudige oplossing op moeilijke problemen. Wanneer een bepaalde eigenschap moet bewezen worden voor elk natuurlijk getal, is het veel eenvoudiger om de startvoorwaarde en de inductie-overgang te bewijzen dan deze effectief algemeen te bewijzen voor elk natuurlijk getal. En wees gerust, deze vereenvoudiging is in zeer vele gevallen noodzakelijk. De ganse wiskunde is doorspekt met inductiebewijzen, overal waar natuurlijke getallen opduiken (en dit is overal) duikt inductie op.
En er is nog een cruciaal gevolg van het inductieprincipe dat onmisbaar is doorheen de ganse wiskunde, namelijk het recursieprincipe. Vele functies zijn zeer makkelijk recursief te definiëren, maar zeer moeilijk expliciet te definiëren. Een bekend voorbeeld is de rij van Fibonacci $0, 1, 1, 2, 3, 5, 8, \ldots$. Elk element is de som van de twee voorgaande elementen. Dit is de recursieve definitie, en we mogen deze gebruiken door het principe van de volledige inductie. Het is duidelijk dat een expliciete definitie van de vorm $F(n) = \ldots$ een stuk moeilijker te vinden is. Het recursieprincipe vindt zijn toepassing in zeer vele gebieden, vooral in de computeralgebra en alle andere domeinen die met algoritmen te maken hebben, dus ook de ganse informatica.
Bovendien kunnen beide principes uitgebreid worden tot transfiniete inductie en transfiniete recursie, dit betekent inductie of recursie over oneindige ordinaalgetallen in plaats van enkel over de natuurlijke getallen. De transfiniete varianten zijn van onschatbaar belang binnen de verzamelingenleer, bewijstheorie, complexiteitstheorie en andere gerelateerde gebieden.
Het principe van de volledige inductie is echt het allerbelangrijkste principe uit de ganse wiskunde, het axioma van de volledige inductie het allerbelangrijkste axioma. Was wiskunde een gebouw, dan was inductie de eerste steen. En wees maar zeker dat elke wiskundige aanwezig zou zijn bij de legging ervan. Inductie is de alfa en de omega, het begin en het einde van de wiskunde. Zowel de eenvoudigste als de meest diepgaande wiskundige bewijzen gebruiken inductie. Want zonder inductie kan men niet aan wiskunde doen. Zonder inductie zakt de ganse wiskunde als een kaartenhuisje ineen, niets wordt gered, geen enkel domein blijft overeind. Zowel het dak als de fundering barst. Het verdwijnen van het principe van de volledige inductie zou voor de wiskundigen zijn wat 2012 is voor de Maya's. Het einde van de wereld, het vergaan van alles.