Inductie (wiskunde): verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k →Voorbeeld 2: regel ingevoegd |
→Algemene principes van bewijs door inductie: opmaak gewijzigd, zie overlegpagina |
||
Regel 10:
Inductie is een bewijstechniek die kan worden toegepast op de [[element (wiskunde)|element]]en van een [[welgefundeerde relatie|welgefundeerde]] [[verzameling (wiskunde)|verzameling]]. Een welgefundeerde verzameling is een verzameling met daarop een [[partiële orde]], waarin bij die ordening geen oneindig aflopende ketens voorkomen. Met inductie bewijst men 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.
We zien dat de volgende drie begrippen van belang zijn: 'minimaal element', 'oneindig aflopende keten' en 'welgefundeerde verzameling'.
*Zij ''V'' een verzameling met daarop een partiële ordening ''R''. Een element <math>v \in V</math> is een ''minimaal element'' als
:<math>\neg \exist_{w \in V, w \not= v} : (w R v)</math>
:Eenvoudig gezegd: ''v'' is een minimaal element als er in de partiële ordening geen element "voor" ''v'' of "kleiner dan" ''v'' is.▼
*Een deelverzameling <math>V'\subset V</math> is een ''oneindig aflopende keten'' als <math>V'</math> geen minimaal element bevat. Een oneindig aflopende keten heeft, eenvoudig gezegd, geen "begin", en een keten met een minimaal element "begint" dus ergens.▼
▲Eenvoudig gezegd: ''v'' is een minimaal element als er in de partiële ordening geen element "voor" ''v'' of "kleiner dan" ''v'' is.
*Een welgefundeerde verzameling is een verzameling die partieel geordend is en waarvan dus alle ketens ergens beginnen.▼
▲Een deelverzameling <math>V'\subset V</math> is een ''oneindig aflopende keten'' als <math>V'</math> geen minimaal element bevat. Een oneindig aflopende keten heeft, eenvoudig gezegd, geen "begin", en een keten met een minimaal element "begint" dus ergens.
▲Een welgefundeerde verzameling is een verzameling die partieel geordend is en waarvan dus 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.
| |||