Inductie (wiskunde)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een formele beschrijving van wiskundige inductie kan worden geïllustreerd aan de hand van het in de tijd volgordelijke domino-effect.

Inductie is een verzameling van technieken binnen de wiskunde om een bewijs te geven van een stelling voor alle elementen van een verzameling door gebruik te maken van de onderliggende structuur van de verzameling. Dit is een zeer nuttige vorm van bewijs, omdat bewijs door inductie kan worden toegepast om eigenschappen te bewijzen voor oneindig grote verzamelingen. De bekendste vorm van bewijs door inductie is het bewijs met volledige inductie.

Om bijvoorbeeld te bewijzen, dat de methode van Laplace om een determinant te berekenen dezelfde uitkomst geeft als de methode van Leibniz, wordt de bewijsmethode van inductie gebruikt. Omdat de methode van Laplace recursief is en het bewijs deze recursieve stappen ook teruggaat, is het bewijs een bewijs met inductie.

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

Algemene principes van bewijs door inductie[bewerken]

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[bewerken]

Een algemene vorm van inductie is welgefundeerde inductie (ook Noetheriaanse inductie genoemd). Het principe is toepasbaar op een verzameling V met daarop een welgefundeerde partiële orde "\prec". Dat impliceert dat elke oneindige keten een minimaal element heeft. Een oneindige keten is dus altijd van de vorm:

x_0,x_1,x_2,\ldots  met voor alle n\geq 0: x_n\prec x_{n+1}

en waarin x_0 een minimaal element is, d.w.z. er is geen element in V dat "kleiner" is:

\neg \exist v \in V, v \neq x_0 : v \prec x_0

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:
v\ \text{minimaal} \Rarr A(v)
  • de geldigheid voor een willekeurig element v\in V te bewijzen onder de veronderstelling van de geldigheid van alle voorgangers van v.
\forall v\in V:(\forall w\in V, w \prec v: A(w)) \Rarr 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[bewerken]

Nuvola single chevron right.svg 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 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[bewerken]

Nuvola single chevron right.svg 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 geldt 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[bewerken]

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.

Voor ordinaalgetallen bestaat een bewijs met transfiniete inductie, dat een uitspraak P geldig is voor alle ordinaalgetallen, meestal uit drie delen:

  1. een bewijs dat P(\alpha) geldig is voor \alpha=0;
  2. een bewijs dat, uit de veronderstelling dat P(\alpha) geldig is voor een willekeurig, ordinaalgetal \alpha dat geen limiet-ordinaal is, volgt dat ook P(\alpha+1) geldig is;
  3. een bewijs dat, uit de veronderstelling dat voor een willekeurig limiet-ordinaal \lambda, P(\alpha) geldig is voor alle \alpha < \lambda volgt, dat P(\lambda) geldig is.

Zie ook[bewerken]

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