Inductie (wiskunde)

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  met daarop een welgefundeerde strikte partiële orde "". Over het aantal elementen van  worden geen aannames gedaan, maar in de meeste toepassingen is  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
, met steeds 
is, waarbij  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  over elementen  de geldigheid bewezen worden voor alle elementen van , door:
 de geldigheid te bewijzen voor de minimale elementen van  (die elementen van  waarvoor geen kleinere elementen bestaan): 

 de geldigheid voor een willekeurig element  te bewijzen onder de veronderstelling van de geldigheid voor alle voorgangers van .

De afzonderlijke eis dat de uitspraak geldig moet zijn voor de minimale elementen van  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

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  een uitspraak over het natuurlijke getal .
Zwakke inductie
Als voldaan is aan
  geldt voor 
 voor willekeurige  volgt de geldigheid van  uit die van 
dan geldt  voor alle natuurlijke getallen.

Sterke inductie
Als voldaan is aan
  geldt voor 
 voor willekeurige  volgt de geldigheid van  uit die van alle  met 
dan geldt  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

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
alle mogelijke basisobjecten een bepaalde eigenschap  hebben; en
alle manieren om een nieuw object te maken uit oude objecten waarvoor die eigenschap  geldt, weer een object opleveren waarvoor  geldt
dan hebben alle objecten in de verzameling de eigenschap .

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

Transfiniete inductie

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.

Logica
Wiskundige terminologie