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.

Algemene principes van bewijs door inductie[bewerken]

Inductie is een bewijstechniek die kan worden toegepast op de elementen van een welgefundeerde verzameling. Een welgefundeerde verzameling is een verzameling V die door een relatie R op V partieel geordend wordt en waarin bij die ordening geen oneindig aflopende ketens voorkomen. Inductie bewijst dan dat een uitspraak geldt voor de hele verzameling door te bewijzen dat de uitspraak geldt voor het minimale element van de partiële ordening en vervolgens te bewijzen dat als de uitspraak geldt voor een deelverzameling van de verzameling, dat de uitspraak dan ook geldt voor alle opvolgers van het minimale element van die deelverzameling.

Minimaal element en oneindig aflopende ketens[bewerken]

Zij R een partiële ordening op een verzameling V. Een minimaal element v van V is een element zodanig dat

\neg \exist_{w \in V, w \not= v} : (w R v)

Oftewel, plat gezegd, in de partiële ordening is er geen element "voor v" of "kleiner dan" v.

Een verzameling V, partieel geordend door een relatie R, bevat een oneindig aflopende keten als V' \subset V en V' bevat geen minimaal element. Een keten met een minimaal element "begint" dus ergens, om het weer plat te zeggen.

Welgefundeerd[bewerken]

Een welgefundeerde verzameling is dus een verzameling die partieel geordend is en waarvan alle ketens ergens beginnen.

Naast welgefundeerdheid is het echter ook nog noodzakelijk dat ieder element van de verzameling een directe voorganger heeft in de partiële ordening. De reden hiervan is technisch, maar het komt erop neer dat als niet ieder element een dergelijke, directe voorganger heeft dat het dan mogelijk is om stellingen te bewijzen die helemaal niet waar zijn door het bewijs een "sprong" te laten maken tussen twee elementen waarvan de "hoogste" geen directe voorganger heeft en zo alle elementen van de verzameling over te slaan waarvoor de stelling niet geldt.

Volledige inductie[bewerken]

Volledige inductie is een methode om te bewijzen dat een uitspraak geldig is voor alle positieve, gehele getallen. Omdat er oneindig veel getallen zijn, kan een dergelijk bewijs niet voor elk getal afzonderlijk worden geleverd. Volledige inductie houdt in dat het bewijs eerst wordt geleverd voor het getal 1, de basisstap. Daarna wordt verondersteld dat de stelling geldig is tot en met het getal n, dit is de inductieveronderstelling. Met de inductieveronderstelling als uitgangspunt wordt de inductiestap gedaan, er moet worden bewezen, dat als de uitspraak geldig is voor n, de uitspraak ook geldig is n+1. Wanneer het inductiebegin geldt en de basisstap kan worden uitgevoerd, is de stelling waar voor alle natuurlijke getallen. Met 1 in de eerste stap is de stelling waar voor alle positieve gehele getallen.

In de formele rekenkunde wordt natuurlijke inductie gevat in een axiomaschema.

Zij nu V een verzameling die welgefundeerd is ten opzichte van een relatie R. Een volledig inductief bewijs van een stelling \phi over V verloopt nu in het algemeen zo:

  1. Bewijs \phi voor alle minimale elementen van V
  2. Veronderstel nu dat \phi geldt voor een willekeurig element v van V
  3. Bewijs nu dat als \phi geldt voor v, dat \phi ook geldt voor de directe opvolger van v (en "directe opvolger" is een term die hier betekenis heeft door de aanwezigheid van de partiële ordening)

Nu is het bewijs klaar. Het bewijs ontstaat doordat \phi geldt voor het de minimale elementen van v en dat \phi geldt voor de opvolger van ieder element waar \phi voor geldt – zo ontstaat dus een keten van elementen waar \phi voor geldt, die zich uitstrekt van de minimale elementen van V tot en met alle elementen van V.

Voorbeeld 1[bewerken]

Stelling: De som van de getallen 1,2,\dots,n is \frac{1}{2}n(n+1)

Bewijs We bewijzen dit met natuurlijke inductie.

Basisstap: Als n=1, is de som 1, wat inderdaad gelijk is aan \frac{1}{2}\cdot 1\cdot(1+1).
Inductiestap: Stel de stelling geldt voor zekere n, dat wil zeggen 1+2+\dots+n=\frac{1}{2}n(n+1). We moeten het nu bewijzen voor n+1, dat wil zeggen, we moeten bewijzen dat 1+2+\dots+n+(n+1)=\frac{1}{2}(n+1)(n+2).
Dit bewijzen we aldus:

\begin{matrix}
1+2+\dots+n+(n+1)= \\
(1+2+\dots+n)+(n+1)= 
\end{matrix}


volgens de inductiehypothese



\begin{matrix}\frac{1}{2}n(n+1)+\frac{1}{2}\cdot2(n+1)= \\
\frac{1}{2}(n(n+1)+2(n+1))= \\
\frac{1}{2}(n+2)(n+1)= \\
\frac{1}{2}(n+1)(n+2)
\end{matrix}


of rechtstreeks


\begin{matrix}
1+2+\dots+n= \\ 
\frac{1}{2}(1+2+\dots+n) + \frac{1}{2}(n+\dots+2+1)= \\
\frac{1}{2}(n*(n+1))\\
\end{matrix}


Voorbeeld 2[bewerken]


Stelling: Zij V de verzameling van natuurlijke getallen zonder 0 (dat wil zeggen  V = \N^{+}). Deze verzameling is partieel geordend door de relatie \leq. Te bewijzen is nu dat voor ieder element n van \N^{+} geldt

\sum^{n}_{k = 1} k * k! = (n + 1)! - 1


Bewijs:

Basisstap: Het minimale element van \N^{+} is 1; er geldt
\sum^{1}_{k = 1} k * k! = 1 * 1! = 1 * 1 = 1 = 2 - 1 = (2 * 1) - 1 = 2! - 1 = (1 + 1)! - 1
dus dat klopt.


Inductiestap: Veronderstel, voor getal n geldt de stelling.

\begin{matrix}
\sum^{n + 1}_{k = 1} k * k! \\
= (n + 1) * (n + 1)! + \sum^{n}_{k = 1} k * k!
\end{matrix}


volgens de inductiehypothese geldt:



\begin{matrix}
= (n + 1) * (n + 1)! + (n + 1)! - 1 \\
= n * (n + 1)! + (n + 1)! + (n + 1)! - 1 \\
= n * (n + 1)! + 2(n + 1)! - 1 \\
= (n + 2)(n + 1)! - 1 \\
= (n + 2)! - 1
\end{matrix}


of rechtstreeks


\begin{matrix}
n*n! + (n-1)*(n-1)! + \dots + 1*1!= \\ 
(n+1)! - n! + n! - (n-1)! + \dots + 2! - 1! = \\
(n+1)! - 1
\end{matrix}


Merk op dat in het bovenstaande voorbeeld in de inductiestap gebruik wordt gemaakt van de inductiehypothese om het bewijs te leveren: we laten zien dat de stelling geldt voor het volgende element, juist omdat het voor het voorgaande (laatste element van de inductiehypothese) geldt.

Bewijs door versterkte volledige inductie[bewerken]

Bewijs door versterkte volledige inductie lijkt heel erg op volledige inductie. Het principe van volledige inductie is dat de waarheid van een stelling over een verzameling bewezen kan worden door het bewijs van het basisgeval en het bewijs voor de opvolger:

(\phi(v_0) \wedge \phi(v_s) \Rightarrow \phi(v_{s + 1})) \Rightarrow \forall_{v \in V} : (\phi(v))

Versterkte volledige inductie zegt nu dat als de waarheid van een stelling voor een willekeurig element volgt uit de waarheid van al zijn voorgangers, dat de stelling dan geldt voor alle elementen van de verzameling:

(\forall_{v \in V} : (\forall_{w \in V} : (w R^{*} v) \Rightarrow \phi(w)) \Rightarrow \phi(v)) \Rightarrow \forall_{v \in V} : \phi(v)

Oftewel, als voor iedere v de stelling voor de aaneengesloten rij van alle voorgangers van v geldt en daarom ook voor het eerstvolgende element v, geldt de stelling voor de hele verzameling. Dit is bijna hetzelfde als volledige inductie, maar het schept de mogelijkheid om de waarheid van een stelling voor een hele verzameling te bewijzen door alleen naar de structuur te kijken en niet naar een bijzonder element.

Het is overigens bewijsbaar dat versterkte volledige inductie als principe volgt uit volledige inductie (maar niet erg makkelijk).

Voorbeeld 3[bewerken]

De Fibonacci-getallen zijn een reeks van getallen die als volgt gevormd worden:

a_1 = 1
a_2 = 1
\forall_{n>2}: a_n = a_{n-1} + a_{n-2}

Stelling: Voor ieder natuurlijk getal n groter dan nul geldt, dat n een Fibonacci-getal is of de som van een aantal niet-opeenvolgende Fibonacci-getallen.


Bewijs:
Gebruik volledige inductie naar de index q van de respectievelijke Fibonacci-getallen


Basisstap:
1 = a_2 is een Fibonaccigetal, 2 = a_3 ook.
Laat q pas bij 3 beginnen te tellen.


Inductiestap
Bewijs dat wanneer voor alle getallen n tot en met het q-de Fibonaccigetal de stelling geldt, de stelling ook voor alle getallen tot en met het q+1-de Fibonaccigetal geldt.
n > a_q vanwege de inductieveronderstelling.
n < a_{q+1}, voor n = a_{q+1} is het geval triviaal.
a_q < n < a_{q+1} \Leftrightarrow 0 < n - a_q < a_{q+1} - a_q = a_{q-1},
dus n - a_q < a_{q-1}.
Nu de inductiehypothese:
a_q komt wel voor in de rij Fibonaccigetallen, waarvan de som samen n is, maar a_{q-1} niet.
Voor het verschil n - a_q kan de inductieveronderstelling worden toegepast.
Samen betekent dit, dat de stelling voor alle getallen tot en met het Fibonaccigetal a_{q+1} geldt.

Voorbeeld 4[bewerken]

De determinant van Vandermonde van de orde is als volgt gedefinieerd

V_n = \begin{vmatrix}
  1 & x_1 & x_1^2 & \cdots & x_1^{n-2} & x_1^{n-1} \\
  1 & x_2 & x_2^2 & \cdots & x_2^{n-2} & x_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
  1 & x_n & x_n^2 & \cdots & x_n^{n-2} & x_n^{n-1}
\end{vmatrix}

Het aantal variabelen x_i in deze determinant is n.

Voor deze determinant geldt:

\displaystyle V_n = \prod_{1 \le i < j \le n} \left({x_j - x_i}\right)

Het bewijs van deze stelling gaat met volledige inductie naar het aantal variabelen x_i in de determinant.

Noot 4: In de wiskunde zijn er voor de twee stellingen uit de voorbeelden 3 en 4, geen andere stellingen die met behulp van één van deze twee worden bewezen.

Structuurinductie[bewerken]

In deelgebieden van de wiskunde waarin inductief gedefinieerde structuren, zoals termen of formules, een rol spelen, wordt ook vaak structuurinductie of structurele inductie toegepast. Een inductief gedefinieerde verzameling structuren bestaat uit een verzameling basisstructuren, die vervolgens wordt afgesloten onder een aantal operatoren. Het idee achter structuurinductie is nu dat als

  1. een stelling geldt voor alle mogelijke basisstructuren en
  2. alle manieren om een nieuwe structuur te maken uit oude structuren waar de stelling al voor geldt, weer een structuur opleveren waar de stelling voor geldt

dat de stelling dan geldt voor alle mogelijke termen die er zijn (dus voor de hele verzameling waar je naar kijkt).

Structuurinductie onderscheidt zich van inductie op de natuurlijke getallen omdat de gebruikte ordening niet totaal is. Bovendien wordt de ordening meestal impliciet gedefinieerd in de inductieve definite. De kleinste objecten zijn de basisobjecten en wanneer objecten samengesteld worden ontstaat een groter object. Structuurinductie komt vaak voor binnen de algebra, logica, theoretische informatica en andere gebieden waarin formules, termen, lijsten, programma's en andere inductief gedefinieerde structuren een rol spelen.

Voorbeeld 5[bewerken]

Definitie. De verzameling positieve propositielogische formules is de kleinste verzameling zodat:

  • een atomaire propositie p_i (voor i\in\mathbb{N}) een positieve formule is;
  • als \varphi en \psi positieve formules zijn, dan ook \varphi\wedge\psi, \varphi\vee\psi en \varphi\to\psi;

Stelling. Een positieve formule \varphi is vervulbaar. Sterker: \varphi wordt vervuld door de evaluatie die aan alle atomaire proposities die in \varphi voorkomen de waarheidswaarde waar toekent.

Bewijs.

Basisstap. Een atomaire formule p_i wordt vervuld door de valuatie die aan p_i de waarheidswaarde waar toekent.
Inductiestap.
Stel dat \varphi van de vorm \varphi_1\wedge\varphi_2 is. Volgens de inductiehypothese kunnen we aannemen, das \varphi_1 en \varphi_2 vervuld worden door de valuaties die aan alle atomaire proposities in \varphi_1 resp. \varphi_2 waar toekenennen. Dat betekent volgens de semantiek van \wedge dat \varphi_1\wedge\varphi_2 vervuld wordt door de valuatie die aan alle atomair proposities waar toekent.
Stel dat \varphi van de vorm \varphi_1\vee\varphi_2 is. Volgens de inductiehypothese kunnen we aannemen, das \varphi_1 en \varphi_2 vervuld worden door de valuaties die aan alle atomaire proposities in \varphi_1 resp. \varphi_2 waar toekenennen. Dat betekent volgens de semantiek van \vee dat \varphi_1\vee\varphi_2 vervuld wordt door de valuatie die aan alle atomair proposities waar toekent.
Stel dat \varphi van de vorm \varphi_1\to\varphi_2 is. Volgens de inductiehypothese kunnen we aannemen, das \varphi_1 en \varphi_2 vervuld worden door de valuaties die aan alle atomaire proposities in \varphi_1 resp. \varphi_2 waar toekenennen. Dat betekent volgens de semantiek van \to dat \varphi_1\to\varphi_2 vervuld wordt door de valuatie die aan alle atomair proposities waar toekent.
Daarmee is de stelling bewezen.


In de grondslagen van de wiskunde worden de natuurlijke getallen soms inductief als volgt gedefefinieerd:

  • 0 (nul) is een natuurlijk getal.
  • Als x een natuurlijk getal is, dan is ook Sx (lees: opvolger van x, of x+1) een natuurlijk getal.
  • Niets anders is een natuurlijk getal.

Als we de natuurlijke getallen zo definiëren, is de "gewone" inductie op natuurlijke getallen een speciaal geval van structuurinductie.

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