Inductie (wiskunde)

Een formele beschrijving van wiskundige inductie kan worden geïllustreerd aan de hand van het in de tijd volgordelijke domino-effect.

In de wiskunde verstaat men onder inductie een verzameling bewijstechnieken om te laten zien dat een uitspraak geldt voor alle elementen van een verzameling door gebruik te maken van de onderliggende structuur van de verzameling. Dit is een nuttige vorm van bewijs, omdat inductie kan worden toegepast om eigenschappen te bewijzen voor oneindig grote verzamelingen. In tegenstelling tot filosofische inductie is wiskundige inductie een deductieve methode. De bekendste vorm van bewijs door inductie is het bewijs met volledige inductie.

Om bijvoorbeeld te bewijzen dat de methode van Laplace voor de berekening van een determinant dezelfde uitkomst geeft als de methode van Leibniz, wordt gebruikgemaakt van inductie. Omdat de methode van Laplace recursief is en het bewijs deze recursieve stappen ook volgt, is het een bewijs met inductie.

Men vergelijkt de methode van inductie wel met het domino-effect. Er is een rij dominostenen zo opgesteld dat, als een steen omvalt, ook de volgende omvalt. Als dan de eerste steen omvalt, zullen dus alle stenen omvallen.

Soorten inductie

Inductie is een bewijstechniek die kan worden toegepast op een partieel geordende verzameling, mits aan de voorwaarde wordt voldaan dat elke oneindige keten, dat is een verzameling van elkaar in de ordening opvolgende elementen, een minimaal (kleinste) element moeten hebben. Het inductieprincipe houdt in dat de geldigheid van een uitspraak bewezen wordt voor de minimale elementen en dat voor een willekeurig element de geldigheid van de uitspraak volgt uit de geldigheid voor z'n directe voorganger, als die er is, en anders uit de geldigheid voor alle voorgangers.

Welgefundeerde inductie

Een algemene vorm van inductie is welgefundeerde inductie (ook Noetheriaanse inductie genoemd). Het principe is toepasbaar op een verzameling $V$ met daarop een welgefundeerde strikte partiële orde "$\prec$". Over het aantal elementen van $V$ worden geen aannames gedaan, maar in de meeste toepassingen is $V$ oneindig. Het bestaan van de welgefundeerde relatie impliceert dat elke keten een minimaal element heeft. Dat wil zeggen dat een (oplopende) keten altijd van de vorm

$x_{0},x_{1},x_{2},\ldots$, met steeds $x_{n}\prec x_{n+1}$

is, waarbij $x_{0}$ geen voorganger heeft.

Bij een welgefundeerde partiële orde hoort op natuurlijke wijze een inductieprincipe, welgefundeerde inductie genoemd. Met dit principe kan van een uitspraak $A(v)$ over elementen $v\in V$ de geldigheid bewezen worden voor alle elementen van $V$, door:

• de geldigheid te bewijzen voor de minimale elementen van $V$ (die elementen van $V$ waarvoor geen kleinere elementen bestaan):

$v\ {\text{minimaal}}\Rightarrow A(v)$

• de geldigheid voor een willekeurig element $v\in V$ te bewijzen onder de veronderstelling van de geldigheid voor alle voorgangers van $v$.

$\forall v\in V:(\forall w\in V,w\prec v:A(w))\Rightarrow A(v)$

De afzonderlijke eis dat de uitspraak geldig moet zijn voor de minimale elementen van $V$ is als zodanig niet nodig, aangezien deze al bevat is in de tweede eis. Een minimaal element heeft immers geen voorganger, dus voor alle voorgangers is de uitspraak waar, en uit deze ware uitspraak moet de geldigheid voor het minimale element afgeleid worden.

Volledige inductie

Zie Volledige inductie voor het hoofdartikel over dit onderwerp.

De bekendste vorm van inductie voor de natuurlijke getallen is volledige inductie. De sterke vorm daarvan komt overeen met welgefundeerde inductie. Er is ook een zwakke vorm van volledige inductie.

Zij $P(n)$ een uitspraak over het natuurlijke getal $n$.

Zwakke inductie

Als voldaan is aan

1. $P(n)$ geldt voor $n=0$
2. voor willekeurige $n$ volgt de geldigheid van $P(n+1)$ uit die van $P(n)$

dan geldt $P$ voor alle natuurlijke getallen.

Sterke inductie

Als voldaan is aan

1. $P(n)$ geldt voor $n=0$
2. voor willekeurige $n$ volgt de geldigheid van $P(n)$ uit die van alle $P(k)$ met $0\leq k<n$

dan geldt $P$ voor alle natuurlijke getallen.

De twee vormen van volledige inductie zijn equivalent; dat wil zeggen dat met beide vormen dezelfde stellingen bewezen kunnen worden.

Structurele inductie

Zie Structurele inductie voor het hoofdartikel over dit onderwerp.

Structurele inductie (of structuurinductie) is een vorm van inductie die werkt op inductief gedefinieerde verzamelingen. Een inductief (of recursief) gedefinieerde verzameling bestaat uit een aantal basisobjecten en wordt vervolgens afgesloten onder een aantal operaties. Het principe van structuurinductie is: als

1. alle mogelijke basisobjecten een bepaalde eigenschap $P$ hebben; en
2. alle manieren om een nieuw object te maken uit oude objecten waarvoor die eigenschap $P$ geldt, weer een object opleveren waarvoor $P$ geldt

dan hebben alle objecten in de verzameling de eigenschap $P$.

Ook structurele inductie is een vorm van welgefundeerde inductie (ook structurele inductie kan als equivalente sterke variant worden gedefinieerd).

Transfiniete inductie

Zie Transfiniete inductie voor het hoofdartikel over dit onderwerp.

Een ordinaalgetal is een 'getal' waarmee in een (mogelijkerwijs oneindige) rij een positie kan worden aangegeven. Ordinaalgetallen vormen een uitbreiding van de natuurlijke getallen. Transfiniete inductie is een inductieprincipe voor ordinaalgetallen, of algemener, voor welgeordende verzamelingen.

Bronnen, noten en/of referenties

• "The theory of the foundations of mathematics - 1870 to 1940" - M. Scheffer
• "De taal van de wiskunde - een verkenning van wiskundig taalgebruik en logische redeneerpatronen" - R.P. Nederpelt, Uitgeverij Versluys, ISBN 90-249-1696-8