Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.1.Zbioryuporządkowaneiliniowouporządkowane
23
(2):Załóżmy,żerelacja⊑iliniowoporządkujeR.Wówczasrównieżrelacja⊑
liniowoporządkujeR.Zatemnamocy(1)relacjaŚjestporządkiemwzbiorze
Soraz(XjŚ)⊑(SjŚ)dlakażdego(XjŚ)∈R.Pozostajewięcsprawdzić,że
jeśli(XjŚ)∈R,xjg∈XorazxŚg,toxŚg.Niechwięc(YjŚ′)∈Rbędzie
takimzbiorem,żexŚ′g.Skoro⊑iporządkujeliniowoR,to(XjŚ)⊑i(YjŚ′)lub
(YjŚ′)⊑i(XjŚ).Pierwszyprzypadekoznacza,żeporządekŚjestindukowany
przezporządekŚ′,awięcxŚg.WdrugimprzypadkurównieżxŚg,gdyżwtedy
wszczególnościŚjestprzedłużeniemporządkuŚ′,cokończydowód.
WprzypadkugdyRjestrodzinązbiorówuporządkowanychorazrelacja⊑
liniowoporządkujerodzinęR,zbióruporządkowany(SjŚ)zdefiniowanytak,jak
wlemacie2.1nazywamysumąrodzinyzbiorówuporządkowanychR.
JeśliporządekindukowanyprzezŚnapodzbiorzeY⊆Xjestliniowy,to
mówimyzwykle,żeYjestłańcuchemwzbiorze(XjŚ).
Niech(XjŚ)będziezbioremuporządkowanym,aA⊆X.Mówimy,żeelement
a∈AjestelementemmaksymalnymzbioruA,gdynieistniejewzbiorzeAelement
odniegowiększy,tzn.gdyspełnionyjestwarunek:
jeślix∈AorazaŚxjtox=a.
Analogicznie,elementb∈AnazywamyelementemminimalnymzbioruA,gdy
wAniemaelementumniejszegoodb,tzn.gdyspełnionyjestwarunek:
jeślig∈AorazgŚbjtog=b.
Elementx∈AnazywamyelementemnajwiększymzbioruA,tzn.x=maxA,jeśli
gŚxdlakażdegog∈A.
Elementx∈AnazywamyelementemnajmniejszymzbioruA,tzn.x=minA,jeśli
xŚgdlakażdegog∈A.
WprzypadkugdyA=X,mówimyoelementachmaksymalnych,minimalnych,
największychbądźnajmniejszychzbioruuporządkowanego(XjŚ).Zanotujmyna-
stępującyprostyzwiązekmiędzyelementemnajwiększymamaksymalnymoraz
międzyelementemminimalnymanajmniejszym:
Lemat2.2.Niech(XjŚ)będziezbioremuporządkowanym.Wówczas:
(1)Jeślixjestelementemnajwiększymw(XjŚ),toxjestjedynymelementem
maksymalnymtegozbioru.
(2)Jeślixjestelementemnajmniejszymw(XjŚ),toxjestjedynymelemen-
temminimalnymtegozbioru.
(3)Jeśli(XjŚ)jestporządkiemliniowym,tokażdyelementmaksymalnytego
zbiorujestnajwiększy,akażdyelementminimalnyjestnajmniejszy.
Dowód.(1):Przypuśćmy,żexŚg,gdzieg∈X.Ponieważelementxjestnaj-
większy,więcgŚx,azatemx=g.Jeślia∈Xjestelementemmaksymalnym,to
aŚx,gdyżelementxjestnajwiększy.Zmaksymalnościelementuaotrzymujemy
x=a.