Welgefundeerde relatie

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

In de ordetheorie, een deelgebied van de wiskunde, noemt men een binaire relatie R op een klasse X welgefundeerd, als elke niet-lege deelverzameling van X een minimaal element heeft met betrekking tot R . Dat wil zeggen: als S een niet-lege deelverzameling van X is, is er een element m van S 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.