Szpilrajn utvidelsessetning

I matematikk , Szpilrajn forlengelse teorem , demonstrert ved Edward Szpilrajn , fremgår det at en hvilken som helst delvis rekkefølgen er inneholdt i en total rekkefølge . Setningen sier intuitivt at en sammenligning mellom elementer som etterlater noen par uforlignelige, kan utvides på en slik måte at hvert element enten er underordnet eller overlegent et annet. Dette er et av mange eksempler på å bruke det valgte aksiomet (i form av Zorns lemma ) for å finne et maksimalt sett med visse egenskaper.

Definisjoner og uttalelse

• Et binært forhold R på et sett S formelt definert som et sett med ordnede par ( x , y ) av elementene S . Betingelsen ( x , y ) ∈ R er generelt forkortet som xRy .
• En rekkefølge (eller delvis rekkefølge) på S er en binær refleksiv ( xRx for alle x ∈ S ), antisymmetrisk ( xRy og yRx innebærer x = y ) og transitiv ( xRy og yRz innebærer xRz ) forhold.
• Hvis det er mer totalt ( xRy eller yRx er sant for hvert par ( x , y ) av elementene i S ), sier vi at det er en total orden.
• Ett forhold R er inneholdt i et annet forhold T når hvert par i det første også er i det andre, dvs. når xRy innebærer xTy .

Den utvidelse teorem angir at et hvilket som helst forhold bestilling (delvis) R inneholdes i en total orden forhold T .

Demonstrasjon

La E alle (ikke-tom) delvis rekkefølgen på S som inneholder den gitte sekvensen R .

Ved å bestille E ved inkludering får vi et induktivt sett . Faktisk, hvilken som helst kjede av E , dvs. en hvilken som helst del C av E fullstendig beordret ved innlemmelse forhold, tatt i E en øvre grense  : den møtet av elementene C .

Ifølge Zorn s lemma, E har derfor minst ett maksimal element Q .

Denne rekkefølgen Q på S er total fordi ellers ville det eksistere i S to elementer Q- sammenlignbar x og y , og man kunne da danne et element T av E som inneholder strengt Q (som ville motsette maksimaliteten til Q ): det ville være tilstrekkelig å ta for T den transitive lukkingen av Q ∪ {( x , y )}. ( T ville være ganske antisymmetrisk, siden Q ∪ {( x , y )} ville være sykløs.)

Andre utvidelsessetninger

• Kenneth Arrow uttalte at enhver forhåndsbestilling (refleksiv og transitiv relasjon) kan utvides til en total forhåndsbestilling; denne påstanden ble senere bevist av Hansson.
• Kotaro Suzumura  (in) beviste at en binær relasjon R kan utvides til å danne en svak orden hvis og bare hvis den er konsistent Suzumura - dvs. d. hvis det ikke er noen syklus av elementer der xRy for hvert par ( x , y ) av påfølgende elementer, og der, for minst ett av disse parene, ikke yRx er sant.

Merknader og referanser

(no) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen "  Szpilrajn-utvidelsesteorem  " ( se forfatterlisten ) .

1. E. Szpilrajn, “  Om utvidelsen av den delvise ordren  ”, fond. Matte. , vol.  16,1930, s.  386-389 ( les online ).