Welpreorde
In de ordetheorie, een deelgebied van de wiskunde, is een welpreorde of welquasiorde een preorde die de volgende eigenschappen heeft:
- er bestaan geen oneindige, strikt aflopende rijen (dat wil zeggen, de orde is welgefundeerd); en
- er bestaan geen oneindige deelverzamelingen waarvan de elementen paarsgewijs helemaal niet door de orde vergeleken worden.
Een wel-partiële orde is een welpreorde die bovendien een partiële orde is.
Definitie
Laat een preorde op zijn. Zoals gebruikelijk schrijven we, voor : als , als maar en als .
Een keten (van ) is een totaal geordende deelverzameling van . Een antiketen is een deelverzameling waarvan alle elementen paarsgewijs onvergelijkbaar zijn (dat wil zeggen: voor alle geldt, dat en ).
De volgende definities zijn equivalent:[1]
- is een welpreorde als er geen oneindige, strikt aflopende keten bestaat en geen oneindige antiketen.
- is een welpreorde als er voor elke oneindige rij een paar met bestaat zodat .
- is een welpreorde als elke oneindige rij een oneindige oplopende subrij bevat.
Voorbeelden
- De orde 'is kleiner dan' op natuurlijke getallen is een welpreorde, omdat er geen oneindige aflopende ketens bestaan en alle paren van natuurlijke getallen met elkaar vergeleken kunnen worden.
- De partiële orde 'deelbaar door' op de natuurlijke getallen, waarin als deelbaar is door , is geen welpreorde. Hoewel er geen oneindige aflopende ketens bestaan, vormen de priemgetallen een oneindige antiketen, een verzameling van getallen die paarsgewijs niet met elkaar vergeleken kunnen worden.
- De minororde op grafen is een bekende welpreorde in de grafentheorie.
Eigenschappen en toepassingen
Omdat elke welpreorde welgefundeerd is, kan op verzamelingen met een welpreorde welgefundeerde inductie worden toegepast. De klasse van welgefundeerde ordes is echter niet afgesloten onder enkele interessante bewerkingen. Een voorbeeld hiervan is het nemen van de machtsverzameling. Als een preorde op de verzameling is, kunnen we als volgt een preorde op de machtsverzameling van definiëren: als er voor elke een bestaat zodat . Er geldt nu dat welgefundeerd is dan en slechts dan als een welpreorde is.[2]
Een tweede toepassing is het representeren van mogelijk oneindige verzamelingen. Als een welpreorde is, en een verzameling die naar boven onder is afgesloten (dat wil zeggen, dat als en , dan ook ), dan kan door een eindig aantal minimale elementen worden gerepresenteerd. Zo is de minororde op grafen een welpreorde, en kan de verzameling van niet-planaire grafen worden gerepresenteerd door , de volledige graaf met 5 knopen, en , de volledige bipartiete graaf met twee keer drie knopen.