Inductie (wiskunde): verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Regel 12:
===Welgefundeerde inductie===
Een algemene vorm van inductie is ''welgefundeerde inductie'' (ook ''Noetheriaanse inductie'' genoemd). Het principe is toepasbaar op een verzameling ''V'' met daarop een [[Welgefundeerde relatie|welgefundeerde]] partiële orde "<math>\prec</math>". Dat impliceert dat elke oneindige keten een minimaal element heeft. Een oneindige keten is dus altijd van de vorm:
:<math>x_0,x_1,x_2,\ldots</math> met voor alle <math>n\geq 0: x_n\prec x_{n+1}</math>
Bij een welgefundeerde partiële orde hoort op natuurlijke wijze een inductieprincipe, ''welgefundeerde inductie'' genoemd. Met dit principe kan van een uitspraak <math>A(v)</math> over elementen <math>v\in V</math> de geldigheid bewezen worden voor alle elementen van ''V'', door:
* de geldigheid te bewijzen voor de minimale elementen van ''V'' (die elementen van ''V'' waarvoor geen kleinere elementen bestaan):
::<math>v\ \text{minimaal} \Rarr A(v)</math>
* de geldigheid voor een willekeurig element <math>v\in V</math> te bewijzen onder de veronderstelling van de geldigheid van alle voorgangers van <math>v</math>.
| |||