Inductie (wiskunde)

Van Wikipedia

Wiskundige, volledige of structurele inductie is een verzameling van bewijstechnieken binnen de wiskunde, die de waarheid van een stelling voor alle elementen van een (mogelijk oneindige) verzameling bewijzen door gebruik te maken van de onderliggende structuur van de verzameling. Dit is een zeer nuttige vorm van bewijs, omdat bewijs door inductie toegepast kan worden om eigenschappen te bewijzen voor oneindig grote verzamelingen.

Bekende vormen van bewijs door inductie zijn volledige inductie, versterkte volledige inductie en structuurinductie.

Inhoud

1 Algemene principes van bewijs door inductie
2 Inductie op de natuurlijke getallen
3 Bewijs door volledige inductie
4 Bewijs door versterkte volledige inductie
5 Bewijs door structuurinductie
6 Inductie en deductie
7 Bronnen en referenties

[bewerk] Algemene principes van bewijs door inductie

Inductie is een bewijstechniek die toegepast kan worden op de elementen van een welgefundeerde verzameling. Een welgefundeerde verzameling is een verzameling V die door een relatie R op V partieël 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.

[bewerk] Partiële ordening

Zij R een relatie op een verzameling V. Dan is R een partiële ordening op V als

R reflexief is, d.w.z. x R x.
R antisymmetrisch is, d.w.z. x R y en y R x,dan x=y
R transitief is, d.w.z. x R y en y R z impliceert x R z

Voorbeeld; R = ≥, V = $\mathbb{R}$ (de reële getallen), dan is R een partiële ordening op V:

x ≥ x voor alle x in R,
x ≥ y en y ≥ x impliceert x = y,
x ≥ y en y ≥ z impliceert x ≥ z.

[bewerk] Minimaal element en oneindig aflopende ketens

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.

[bewerk] Welgefundeerd

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.

[bewerk] Inductie op de natuurlijke getallen

Wiskundige inductie wordt vaak toegepast op de natuurlijke getallen; deze vorm van inductie wordt ook wel natuurlijke inductie genoemd. Hierbij wordt een eigenschap $P$ van alle natuurlijke getallen bewezen door $P (0)$ (de "basisstap") en de regel "als $P (n)$ , dan $P (n + 1)$ " (de inductiestap) te bewijzen.

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

[bewerk] Bewijs door volledige inductie

Zij nu V een verzameling die goed gefundeerd is ten opzichte van een relatie R. Een volledig inductief bewijs van een stelling $φ$ over V verloopt nu in het algemeen zo:

Bewijs $φ$ voor alle minimale elementen van V
Veronderstel nu dat $φ$ geldt voor een willekeurig element v van V
Bewijs nu dat als $φ$ geldt voor v, dat $φ$ 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 $φ$ geldt voor het de minimale elementen van v en dat $φ$ geldt voor de opvolger van ieder element waar $φ$ voor geldt – zo ontstaat dus een keten van elementen waar $φ$ voor geldt, die zich uitstrekt van de minimale elementen van V tot en met alle elementen van V.

VOORBEELD 0:

Zij V de verzameling van natuurlijke getallen zonder 0 (d.w.z. $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$

STAP 0: 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.

STAP 1 (Inductie Hypothese IH): Veronderstel, voor getal n geldt de stelling.

STAP 2: $\sum^{n + 1}_{k = 1} k * k!$

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

= {I H}(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

Merk op dat in het bovenstaande voorbeeld in stap 2 gebruik wordt gemaakt van de inductie hypothese 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 inductie hypothese) geldt.

Voorbeeld 1:

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

Bewijs: We bewijzen dit met natuurlijke inductie.

Basis: Als

n = 0

, is de som 0, wat inderdaad gelijk is aan $\frac{1}{2}\cdot 0\cdot(0+1)$ .

Stap: Stel de stelling geldt voor zekere n, dat wil zeggen $0+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 $0+1+2+\dots+n+(n+1)=\frac{1}{2}(n+1)(n+2)$ .

Dit bewijzen we aldus:

$\begin{matrix}0+1+2+\dots+n+(n+1)= \\ (0+1+2+\dots+n)+(n+1)= \\ \mbox{(volgens de inductiehypothese)} \\ \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}$

Noot 0: Volledige inductie wordt ook wel gewoon inductie genoemd.
Noot 1: Er is ook een term natuurlijke inductie in omloop voor bewijzen op de verzameling der natuurlijke getallen ( $\N$ ). Natuurlijke inductie wordt soms echter ook gebruikt voor veronderstellende inductie, dus veel mensen kiezen ervoor om deze term te vermijden als het om wiskunde gaat.

[bewerk] Bewijs door versterkte volledige inductie

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.

VOORBEELD:

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

a 1 = 1

a 2 = 1

$\forall_{n \in \N^{+} \backslash \{1,2\}}: a_n = a_{n-1} + a_{n-2}$

Te bewijzen is nu dat voor ieder natuurlijk getal n groter dan nul, n een Fibonacci-getal is of de som van een aantal niet-opeenvolgende Fibonacci-getallen. Hierbij gebruiken we het feit dat ieder dergelijk getal n een Fibonacci-getal is of tussen twee opeenvogende Fibonacci-getallen ligt:

$\forall_{n \in \N^+} \exists_{k \in \N^+} : (a_k \leq n < a_{k+1})$

Verder korten we als volgt af: A(n) = "n is een Fibonacci-getal of de som van een aantal niet-opeenvolgende Fibonacci-getallen".

Zij $n \in \N^+$ .

We moeten nu bewijzen dat $(\forall_{k \in \N^+} : (k < n) \Rightarrow A(k)) \Rightarrow A(n)$ ; veronderstel dus $\forall_{k \in \N^+} : (k < n) \Rightarrow A(k)$ .

Zij nu q zo dat $a_q \leq n < a_{q+1}$ . Nu geldt

$q \neq 1$ : $a 1 = a 2 = 1$ , dus $a_q \leq n < a_{q+1} \equiv 1 \leq n < 1 \equiv 1 < 1 \equiv FALSE$

Verder geldt $a_q \leq n < a_{q+1} \equiv 0 \leq n - a_q < a_{q+1} - a_q = a_{q-1}$

Stel,

n - a q = 0

; dan is n het Fibonacci-getal

a q

, dus A(n). Dus $n - a_q = 0 \Rightarrow A(n)$ .

Stel, $n - a_q \neq 0$ ; dan geldt

n - a q > 0

, want

n > a q

, dus $n - a_q \in \N^{+}$ . Verder $a_q \geq 1$ , dus

n - a q < n

. Maar we hadden verondersteld $\forall_{k \in \N^+} : (k < n) \Rightarrow A(k)$ , dus nu weten we

A (n - a q)

. Dus

n - a q

is zelf een Fibonacci-getal (kleiner dan

a q - 1

, zie boven), of de som van een aantal niet-opeenvolgende, verschillende Fibonacci-getallen (allemaal kleiner dan

a q - 1

, want samen zijn ze ook kleiner dan

a q - 1

). Dus n is

a q

plus dat Fibonacci-getal, of

a q

plus die som van Fibonacci-getallen. Dus A(n). Dus $n - a_q \neq 0 \Rightarrow A(n)$ .

Maar, omdat $n \in \N^+$ , $n - a_q \neq 0 \vee n - a_q = 0 \equiv TRUE$ . Dus er geldt gewoon hoe dan ook A(n), onder de veronderstelling van boven. Maar dan geldt dus $(\forall_{k \in \N^+} : (k < n) \Rightarrow A(k)) \Rightarrow A(n)$ . Maar we hebben n anoniem gekozen (d.w.z., we hebben niet van tevoren bepaald over welke n het precies gaat) dus wat we bewezen hebben, geldt voor elke n: $\forall_{n \in \N^+} : ((\forall_{k \in \N^+} : (k < n) \Rightarrow A(k)) \Rightarrow A(n))$ . Op basis van versterkte volledige inductie mogen we nu dus concluderen $\forall_{n \in \N^+} : A(n)$ .

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

[bewerk] Bewijs door structuurinductie

Structuurinductie is waarschijnlijk de meest algemene vorm van bewijs door inductie en ook de meest fundamentele. Structuurinductie is gebaseerd op het idee dat het geheel van wiskunde en logica een stelsel is van termen in een formele taal, die zelf ook weer opgebouwd worden volgens een bepaalde structuur.

Het idee achter structuurinductie is nu dat als

een stelling geldt voor alle mogelijke basistermen en
alle manieren om een nieuwe term te maken vanuit een aantal termen waar de stelling al voor geldt, weer een term 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).

Een mogelijke vergelijking voor de manier waarop het werkt, is dit:

Iedere LEGO-steen die er is, is op zich een constructie
hoe ik een LEGO-steen ook bij een constructie erbij plaats, het resultaat is weer een constructie
conclusie: alles wat ik met LEGO kan maken, is een constructie

Structuurinductie wordt vaak toegepast binnen de algebra en andere vakgebieden binnen de wiskunde en informatica die naar formele constructies kijken, of anderszins de geordende verzamelingen achter zich laten.

[bewerk] Inductie en deductie

De term inductie wordt in gewoonlijk gebruikt voor een andere bewijs- (of argumentatie-)techniek, waarbij een algemene wetmatigheid wordt afgeleid uit een beperkt aantal gevallen. Wiskundige inductie is echter een methode om, op basis van een eigenschap van een structuur (verzameling of anderszijds) aan te tonen dat een waarheid geldt voor alle onderdelen van die structuur en dus ook voor de hele structuur. De waarde van een bewijs door inductie is dus dat als een object blijkt tot een structuur te horen, op basis van dat gegeven bekend is dat een bepaalde eigenschap voor dat object geldt. Wiskundige inductie is dus eigenlijk een vorm van deductie (algemene kennis van waarheid toepassen op een specifiek geval).

Zie ook Deductie versus inductie

[bewerk] Bronnen en referenties

Bronnen en 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

Categorie: Logica