Welgefundeerde relatie
In de wiskunde heet een irreflexieve tweeplaatsige relatie op een klasse welgefundeerd, als elke niet-lege deelverzameling van een element bevat dat geen voorganger heeft, wat in dit verband betekent dat er geen element is waarvoor het paar tot de relatie behoort. Het is dus niet mogelijk dat er een hele keten van elementen is waarvan elk een voorganger heeft, en dus oneindig doorloopt.
Definitie
[bewerken | brontekst bewerken]Een tweeplaatsige relatie , die irreflexief is, heet welgefundeerd, als er voor alle niet-lege een bestaat zodanig dat voor alle geldt:
- .
Men kan, bij aanname van het keuzeaxioma, bewijzen dat de relatie welgefundeerd is dan en slechts dan als er geen oneindige dalende keten is, met andere woorden: als er in geen keten is met voor elk natuurlijk getal
Partiële orde
[bewerken | brontekst bewerken]Een partiële orde is reflexief en volgens de definitie daarom niet welgefundeerd. Als echter de bijbehorende strikte partiële orde welgefundeerd is, wordt aanvullend de partiële orde zelf ook als welgefundeerd beschouwd.
Voorbeelden
[bewerken | brontekst bewerken]- De relatie "is een voorganger van", , op de natuurlijke getallen, gedefinieerd als is welgefundeerd. Iedere niet-lege deelverzameling van natuurlijke getallen heeft immers een kleinste element, dat dus geen voorganger heeft.
- Om dezelfde reden is de relatie "is kleiner dan", , op natuurlijke getallen welgefundeerd.
- De relatie "is kleiner dan" op positieve reële getallen is niet welgefundeerd. Beschouw het open interval dat alle reële getallen groter dan en kleiner dan bevat, maar en zelf niet. Aangezien er voor elk reëel getal een reëel getal tussen en bestaat, heeft deze verzameling geen element zonder voorganger. De positieve reële getallen bevatten inderdaad oneindige dalende ketens, bijvoorbeeld: .