Welgefundeerde relatie

In de wiskunde heet een irreflexieve tweeplaatsige relatie ${\displaystyle R}$ op een klasse${\displaystyle X}$ welgefundeerd, als elke niet-lege deelverzameling ${\displaystyle S}$ van ${\displaystyle X}$ een element ${\displaystyle m}$ bevat dat geen voorganger heeft, wat in dit verband betekent dat er geen element ${\displaystyle s\in S,}$ is waarvoor het paar ${\displaystyle (s,m)}$ tot de relatie ${\displaystyle R}$ behoort. Het is dus niet mogelijk dat er een hele keten van elementen is waarvan elk een voorganger heeft, die dus oneindig doorloopt.

Definitie

Een tweeplaatsige relatie ${\displaystyle R\subseteq X\times X}$, die irreflexief is, heet welgefundeerd, als voor alle ${\displaystyle S\subseteq X,\ S\neq \varnothing }$ er een ${\displaystyle m\in S}$ bestaat zodanig, dat voor alle ${\displaystyle s\in S}$

${\displaystyle (s,m)\notin R}$

Men kan bewijzen, zij het onder de veronderstelling dat het keuzeaxioma geldt, dat de relatie ${\displaystyle R}$ dan en slechts dan welgefundeerd is, als er geen oneindig dalende keten is, anders gezegd als er in ${\displaystyle X}$ geen keten ${\displaystyle x_{1},x_{2},\ldots }$ is met ${\displaystyle x_{n+1}Rx_{n}}$ voor elke natuurlijke ${\displaystyle n.}$

Partiële orde

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

• De relatie "voorganger" ${\displaystyle \prec }$ op de natuurlijke getallen, gedefinieerd als ${\displaystyle n\prec m\Leftrightarrow n+1=m}$ 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 "kleiner dan" ${\displaystyle <}$ op natuurlijke getallen welgefundeerd.
• De relatie "kleiner dan" op positieve reële getallen is niet welgefundeerd. Neem het open interval ${\displaystyle S=(1,2)}$, dat alle reële getallen tussen ${\displaystyle 1}$ en ${\displaystyle 2}$ bevat, maar ${\displaystyle 1}$ en ${\displaystyle 2}$ zelf niet. Aangezien voor elk reële getal ${\displaystyle r\in S}$ een reëel getal tussen ${\displaystyle 1}$ en ${\displaystyle r}$ bestaat, heeft deze verzameling ${\displaystyle S}$ geen element zonder voorganger. Inderdaad bevatten de positieve reële getallen oneindig dalende ketens, bijvoorbeeld: ${\displaystyle 1{,}1;1{,}01;1{,}001;\cdots }$.