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 $\leq$ een preorde op $X$ zijn. Zoals gebruikelijk schrijven we, voor $x,y\in X$: $x\geq y$ als $y\leq x$, $x<y$ als $x\leq y$ maar $y\not \leq x$ en $x>y$ als $y<x$.

Een keten (van $\leq$) is een totaal geordende deelverzameling van $X$. Een antiketen is een deelverzameling $K\subseteq X$ waarvan alle elementen paarsgewijs onvergelijkbaar zijn (dat wil zeggen: voor alle $x,y\in K$ geldt, dat $x\not \leq y$ en $y\not \leq x$).

De volgende definities zijn equivalent:

• $\leq$ is een welpreorde als er geen oneindige, strikt aflopende keten $x_{1}>x_{2}>x_{3}>\cdots$ bestaat en geen oneindige antiketen.
• $\leq$ is een welpreorde als er voor elke oneindige rij $x_{1},x_{2},\ldots$ een paar $i,j$ met $i<j$ bestaat zodat $x_{i}\leq x_{j}$.
• $\leq$ is een welpreorde als elke oneindige rij $x_{1},x_{2},\ldots$ een oneindige oplopende subrij $x_{i_{1}}\leq x_{i_{2}}\leq x_{i_{3}}\leq \cdots$ 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 $x<y$ als $y$ deelbaar is door $x$, 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 $\leq$ een preorde op de verzameling $A$ is, kunnen we als volgt een preorde $\leq ^{+}$ op de machtsverzameling ${\mathcal {P}}(A)$ van $A$ definiëren: $X\leq ^{+}Y$ als er voor elke $x\in X$ een $y\in Y$ bestaat zodat $x\leq y$. Er geldt nu dat $\leq ^{+}$ welgefundeerd is dan en slechts dan als $\leq$ een welpreorde is.

Een tweede toepassing is het representeren van mogelijk oneindige verzamelingen. Als $\leq$ een welpreorde is, en $A$ een verzameling die naar boven onder $\leq$ is afgesloten (dat wil zeggen, dat als $x\leq y$ en $x\in A$, dan ook $y\in A$), dan kan $A$ 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 $K_{5}$, de volledige graaf met 5 knopen, en $K_{3,3}$, de volledige bipartiete graaf met twee keer drie knopen.

Bronnen, noten en/of referenties