Pagina 1 di 1

Relazioni d'ordine

Inviato: 11 dic 2005, 15:11
da publiosulpicio
Sia $ X $ un insieme e sia $ S \subseteq X \times X $ una relazione d'ordine parziale su $ X $. Dimostrare che esiste una relazione d'ordine totale $ R $ su $ X $ tale che $ S \subseteq R $.

Inviato: 13 dic 2005, 13:41
da gordio
Speriamo di non dir cavolate... Sia $ A $ l'insieme delle relazioni d'ordine $ P \subseteq X \times X $ tali che $ S \subseteq P. \ A $ è non vuoto perchè ci sta almeno $ S $.
Ordiniamo $ A $ per inclusione, e mostriamo che sono verificate le ipotesi del lemma di zorn:
Sia $ \mathcal{C} $ una catena in $ A $, e sia $ D=\bigcup_{P \in \mathcal{C}}P\ $. $ D $ è ancora una relazione d'ordine $ \in A $ (ad esempio per la proprietà antisimmetrica: supponiamo $ (x,y)\ \text{e}\ (y,x) \in D $. Allora $ (x,y) $ apparterrà ad un certo $ P_1 $, $ (y,x) $ ad un certo $ P_2 $; ma $ \mathcal{C} $ è totalmente ordinato dall'ordine indotto, perciò $ P_1 \subseteq P_2 $ o viceversa, e nell'insieme più grande valgono le proprietà dell'ordine), ed è maggiorante di $ \mathcal{C} $.
Per il lemma di Zorn, $ A $ ammette almeno un elemento massimale $ R $. Ora osserviamo che una relazione d'ordine massimale è per forza totale (anzi dovrebbe valere il se e solo se): se così non fosse, siano $ x \ \text{e}\ y $ tali che né $ (x,y) $ né $ (y,x) $ appartengono ad $ R $ (necessariamente $ x \ne y $). $ R' = R \cup \{(w,z) | (w,x) \in R, (y,z) \in R\} $ , si verifica essere ancora un elemento di $ A $, ed $ R \subsetneq R' $ vi è strettamente incluso perchè almeno $ (x,y) \in R' $, contro l'ipotesi che $ R $ sia massimale.

una relazione d'ordine tra le relazioni d'ordine su X. Si può ricavare qualcosa di bello continuando questo procedimento "nidificando" sempre più le relazioni d'ordine? uhm... :)