Teorema extensiei Szpilrajn

În matematică , teorema extensiei lui Szpilrajn , demonstrată de Edward Szpilrajn , afirmă că orice ordine parțială este conținută într-o ordine totală . Intuitiv, teorema spune că o comparație între elemente care lasă unele perechi incomparabile poate fi extinsă astfel încât fiecare element să fie inferior sau superior altului. Acesta este unul dintre numeroasele exemple de utilizare a axiomei de alegere (sub forma lemei lui Zorn ) pentru a găsi un set maxim cu anumite proprietăți.

Definiții și enunț

• O relație binară R pe un set S este definit formal ca un set de perechi ordonate ( x , y ) ale elementelor S . Condiția ( x , y ) ∈ R este în general prescurtată ca xRy .
• O relație de ordine (sau ordine parțială) pe S este o relație binară reflexivă ( xRx pentru toate x ∈ S ), antisimetrică ( xRy și yRx implică x = y ) și tranzitivă ( xRy și yRz implică xRz ).
• Dacă este mai total ( xRy sau yRx este adevărat pentru fiecare pereche ( x , y ) de elemente ale lui S ), spunem că este o ordine totală.
• O relație R este conținută într-o altă relație T atunci când fiecare cuplu din prima este, de asemenea, în a doua, adică când xRy implică xTy .

Stările extensie teorema că orice relație ordonare (parțială) R este conținută într - un total de relație T .

Demonstrație

Să E totul (non-gol) ordine parțială S care conțin secvență dată R .

Ordonând E prin incluziune, obținem un set inductiv . Într-adevăr, orice lanț de E , adică orice parte C din E total ordonat de relația de incluziune, admise în E un superior obligat  : a reuniune a elementelor C .

În conformitate cu lema lui Zorn, E are deci cel puțin un element Q maxim .

Această ordine Q pe S este totală pentru că altfel, ar exista în S două elemente Q -incomparabile x și y , și s-ar putea forma apoi un element T de E conținând strict Q (ceea ce ar contrazice maximul lui Q ): ar fi suficient să ia pentru T închiderea tranzitivă a Q ∪ {( x , y )}. ( T ar fi destul de antisimetric, deoarece Q ∪ {( x , y )} ar fi fără ciclu.)

Alte teoreme de extensie

• Kenneth Arrow a afirmat că orice precomandă (relație reflexivă și tranzitivă) poate fi extinsă într-o precomandă totală; această afirmație a fost dovedită ulterior de Hansson.
• Kotaro Suzumura  (în) a dovedit că o relație binară R poate fi extinsă pentru a forma o ordine slabă dacă și numai dacă este consecventă Suzumura - adică d. dacă nu există un ciclu de elemente în care xRy pentru fiecare pereche ( x , y ) de elemente consecutive și în care, pentru cel puțin una dintre aceste perechi, yRx nu este adevărat.

Note și referințe

(ro) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „  Teorema extensiei Szpilrajn  ” ( vezi lista autorilor ) .

1. E. Szpilrajn, „  Despre extinderea ordinului parțial  ”, fond. Matematica. , vol.  16,1930, p.  386-389 ( citește online ).