Teorema di estensione di Szpilrajn

Teorema di estensione di Szpilrajn Nella teoria degli ordini, il teorema di estensione di Szpilrajn (chiamato anche principio di estensione dell'ordine), dimostrato da Edward Szpilrajn in 1930,[1] afferma che ogni ordine parziale rigoroso è contenuto in un ordine totale. Intuitivamente, il teorema dice che qualsiasi metodo di confronto di elementi che lasci incomparabili alcune coppie può essere esteso in modo tale che ogni coppia diventi comparabile. Il teorema è uno dei tanti esempi dell'uso dell'assioma della scelta nella forma del lemma di Zorn per trovare un insieme massimale con determinate proprietà.

Contenuti 1 Definizioni e affermazione 2 Prova 3 Altri teoremi di estensione 4 Guarda anche 5 References Definitions and statement A binary relation {stile di visualizzazione R} su un set {stile di visualizzazione X} è formalmente definito come un insieme di coppie ordinate {stile di visualizzazione (X,y)} di elementi di {stile di visualizzazione X,} e {stile di visualizzazione (X,y)in r} è spesso abbreviato come {displaystyle xRy.} Una relazione è riflessiva se {stile di visualizzazione xRx} vale per ogni elemento {stile di visualizzazione xin X;} è transitivo se {displaystyle xRy{testo{ e }}e Rz} implicare {stile di visualizzazione xRz} per tutti {stile di visualizzazione x,y,zin X;} è antisimmetrico se {displaystyle xRy{testo{ e }}yRx} implicare {stile di visualizzazione x=y} per tutti {stile di visualizzazione x,yin X;} ed è una relazione di connessione se {displaystyle xRy{testo{ o }}yRx} vale per tutti {stile di visualizzazione x,Yin X.} Un ordine parziale è, per definizione, un riflessivo, relazione transitiva e antisimmetrica. Un ordine totale è un ordine parziale connesso.

Una relazione {stile di visualizzazione R} è contenuto in un'altra relazione {stile di visualizzazione S} quando tutte le coppie ordinate entrano {stile di visualizzazione R} appaiono anche in {stile di visualizzazione S;} questo è, {displaystyle xRy} implica {displaystyle xSy} per tutti {stile di visualizzazione x,Yin X.} Il teorema di estensione afferma che ogni relazione {stile di visualizzazione R} questo è riflessivo, transitivo e antisimmetrico (questo è, un ordine parziale) è contenuto in un'altra relazione {stile di visualizzazione S} che è riflessivo, transitivo, antisimmetrico e connesso (questo è, un ordine totale).

Proof The theorem is proved in two steps. Primo, se un ordine parziale non viene confrontato {stile di visualizzazione x} e {stile di visualizzazione y,} può essere esteso aggiungendo prima la coppia {stile di visualizzazione (X,y)} e quindi eseguire la chiusura transitiva, e secondo, poiché questa operazione genera un ordinamento che contiene rigorosamente quello originario e può essere applicato a tutte le coppie di elementi incomparabili, esiste una relazione in cui tutte le coppie di elementi sono state rese comparabili.

Il primo passo è dimostrato come un lemma preliminare, in cui un ordine parziale in cui una coppia di elementi {stile di visualizzazione x} e {stile di visualizzazione y} sono incomparabili viene modificato per renderli comparabili. Questo viene fatto aggiungendo prima la coppia {displaystyle xRy} alla relazione, che può risultare in una relazione non transitiva, e quindi ripristinando la transitività aggiungendo tutte le coppie {stile di visualizzazione qRp} tale che {stile di visualizzazione qRx{testo{ e }}yRp.} Questo viene fatto su una singola coppia di elementi incomparabili {stile di visualizzazione x} e {stile di visualizzazione y,} e produce una relazione che è ancora riflessiva, antisimmetrico e transitivo e che contiene rigorosamente quello originario.

Successivamente viene mostrato che il poset di ordini parziali contiene {stile di visualizzazione R,} ordinato per inclusione, ha un elemento massimo. L'esistenza di un tale elemento massimale è dimostrata applicando il lemma di Zorn a questo poset. Una catena in questo poset è un insieme di relazioni che contengono {stile di visualizzazione R} tale che date due di queste relazioni, uno è contenuto nell'altro.

Per applicare il lemma di Zorn, si deve dimostrare che ogni catena ha un limite superiore nel poset. Permettere {stile di visualizzazione {matematico {C}}} essere una tale catena, e resta da dimostrare che l'unione dei suoi elementi, {tazza grande in stile display {matematico {C}},} è un limite superiore per {stile di visualizzazione {matematico {C}}} che è nel poset: {stile di visualizzazione {matematico {C}}} contiene la relazione originaria {stile di visualizzazione R} poiché ogni elemento di {stile di visualizzazione {matematico {C}}} è un ordine parziale contenente {stile di visualizzazione R.} Prossimo, è dimostrato che {tazza grande in stile display {matematico {C}}} è una relazione transitiva. Supporre che {stile di visualizzazione (X,y)} e {stile di visualizzazione (y,z)} sono dentro {tazza grande in stile display {matematico {C}},} in modo che esistano {stile di visualizzazione S,Lattina {matematico {C}}} tale che {stile di visualizzazione (X,y)a s{testo{ e }}(y,z)in t.} Da {stile di visualizzazione {matematico {C}}} è una catena, o {displaystyle Ssottoseteq T{testo{ o }}Tsubseteq S.} Supponiamo {displaystyle Ssottoseteq T;} l'argomento per quando {displaystyle Tsubseteq S} è simile. Quindi {stile di visualizzazione (X,y)in t.} Poiché tutte le relazioni prodotte dal nostro processo sono transitive, {stile di visualizzazione (X,z)} è dentro {stile di visualizzazione T} e quindi anche in {tazza grande in stile display {matematico {C}}.} Allo stesso modo, lo si può dimostrare {tazza grande in stile display {matematico {C}}} è antisimmetrico.

Quindi per il lemma di Zorn l'insieme degli ordini parziali che contiene {stile di visualizzazione R} ha un elemento massimo {stile di visualizzazione Q,} e non resta che dimostrarlo {stile di visualizzazione Q} è totale. Infatti se {stile di visualizzazione Q} aveva una coppia di elementi incomparabili, allora è possibile applicarvi il processo del primo passaggio, portando a un altro rigoroso ordine parziale che contiene {stile di visualizzazione R} e contiene rigorosamente {stile di visualizzazione Q,} contraddicendolo {stile di visualizzazione Q} è massimo. {stile di visualizzazione Q} è quindi un ordine totale contenente {stile di visualizzazione R,} completando la dimostrazione.

Other extension theorems Arrow stated that every preorder (relazione riflessiva e transitiva) può essere esteso a un preordine totale (relazione transitiva e di connessione), e questa affermazione è stata successivamente dimostrata da Hansson.

Suzumura ha dimostrato che una relazione binaria può essere estesa a un preordine totale se e solo se è coerente con Suzumura, il che significa che non esiste un ciclo di elementi del genere {displaystyle xRy} per ogni coppia di elementi consecutivi {stile di visualizzazione (X,y),} e c'è una coppia di elementi consecutivi {stile di visualizzazione (X,y)} nel ciclo per il quale {stile di visualizzazione yRx} non tiene.

See also Linear extension – Mathematical ordering of a partial order References ^ Szpilrajn, Edoardo (1930), "Sulla proroga dell'ordinanza parziale" (PDF), Fondamenti di matematica (in francese), 16: 386–389, doi:10.4064/fm-16-1-386-389. Categorie: Assioma di sceltaTeoremi nei fondamenti della matematicaTeoria degli ordini