Inductie (wiskunde): verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Versie 41427929 van Hoopje ongedaan gemaakt. Veel lezers willen misschien graag weten wat het verschil is. . |
Geen bewerkingssamenvatting |
||
Regel 9:
==Algemene principes van bewijs door inductie==
Inductie is een bewijstechniek die kan worden toegepast op een [[partiële orde|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===
:<math>x_0,x_1,x_2,\ldots</math> met voor alle <math>n\geq 0: x_n\prec x_{n+1}</math>
Regel 31 ⟶ 28:
===Volledige inductie===
{{Zie hoofdartikel|Volledige inductie}}
De bekendste vorm van inductie voor de [[Natuurlijk getal|natuurlijke getallen]] is ''volledige inductie''.
;Zwakke inductie
:# uit het feit dat <math>P</math> geldt voor <math>n</math> volgt dat <math>P</math> geldt voor <math>n+1</math>;▼
Als voldaan is aan
: dan geldt <math>P</math> voor alle natuurlijke getallen.▼
# voor willekeurige <math>n</math> volgt de geldigheid van <math>P(n+1)</math> uit die van <math>P(n)</math>
:# <math>P</math> geldt voor 0; en▼
;Sterke inductie
De twee vormen van volledige inductie zijn equivalent; dat wil zeggen dat met beide vormen dezelfde stellingen bewezen kunnen worden. Sterke inductie is direct een instantie van welgefundeerde inductie.▼
Als voldaan is aan
▲
▲De twee vormen van volledige inductie zijn equivalent; dat wil zeggen dat met beide vormen dezelfde stellingen bewezen kunnen worden.
===Structurele inductie===
| |||