Welgefundeerde relatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de ordetheorie, een deelgebied van de wiskunde, noemt men een irreflexieve relatie R op een klasse X welgefundeerd, als elke niet-lege deelverzameling S van X een element m bevat dat geen voorganger heeft, dus waarvoor geldt dat voor elk element s van S, het paar (s, m) niet tot de relatie R behoort.

In formule: R is welgefundeerd, als:

\forall S \subseteq X\;\, (S \neq \varnothing \to \exists m \in S\;\; \forall s \in S\;\, ( s, m) \notin R)

(Sommige auteurs nemen de extra voorwaarde op dat R verzamelingachtig moet zijn, dat wil zeggen dat de elementen kleiner dan een gegeven element een verzameling vormen.)

Men kan bewijzen, zij het onder de veronderstelling dat het keuzeaxioma geldt, dat de relatie R dan en slechts dan welgefundeerd is, als er geen oneindig aflopende keten is, d.w.z. dat er in X geen keten x_1,x_2,\ldots is met x_{n+1}Rx_n voor elke natuurlijke n.

Partiële orde[bewerken]

Als een relatie niet irreflexief is dan is deze volgens bovenstaande formule niet welgefundeerd. Aanvullend wordt een partiële orde echter als welgefundeerd beschouwd wanneer de bijbehorende stricte partiële orde dat is.