Uspořádané množiny
Každá relace /i na množině A, která je současně reflexivní, antisymetrická a tranzitivní, se nazývá (částečné) uspořádání na A. Dvojice (A, /i) se pak nazývá (částečně) uspořádaná množina.
Je-li [i uspořádání na A takové, že navíc platí
(Va, 6 G A)(a /jb V b /i a),
pak /i se nazývá úplné nebo též lineární uspořádání na A a dvojice (A, /i) se pak nazývá úplně nebo lineárně uspořádaná množina nebo též řetězec.
Relace uspořádání na A se obvykle značí symbolem < . Jsou-li a, b G A takové prvky, že a < b, čteme to „a je menší nebo rovno b". Jsou-li a, b G A takové prvky, že platí současně a < b a a/í), užíváme označení a < b a čteme je „a je menší než b".
Množiny N, Z, Q, R všech přirozených, celých, racionálních a reálných čísel s obvyklým uspořádáním podle velikosti jsou úplně uspořádané množiny.
Příklad. Na množině
o; = {0,l,2,3,...}
všech nezáporných celých čísel definujeme relaci | , nazývanou relace dělitelnosti, následujícím předpisem:
(Vra, n G o;)(m \ n <^=^> (3k G uj)(n = m-k)).
Jsou-li ra, n G oj taková čísla, že ra | n, říkáme, že ra dělí n. Pak relace dělitelnosti | je uspořádání na množině oj, takže (o;, |) je uspořádaná množina, není to ale úplně uspořádaná množina.
Příklad. Buď A množina a buď V(A) potenční množina množiny A. Připomeňme, že prvky množiny V(A) jsou všechny
1
podmnožiny X množiny A. Pak množinová inkluze C uvažovaná v rámci podmnožin X množiny A je uspořádání na množině V (A). Je tedy (V (A), C) je uspořádaná množina, ale obecně to není úplně uspořádaná množina.
Pro libovolnou množinu A je diagonální relace uspořádání na A. Uspořádaná množina (A, Aa) se nazývá protiřetězec.
Buď (A, <) uspořádaná množina. Řekneme, že prvky a, b E A jsou srovnatelné, platí-li a < b nebo b < a. Řekneme, že prvky a, b E A jsou nesrovnatelné, jestliže neplatí ani a < b ani b < a. Pro tuto skutečnost užíváme označení a \ \ b. Zřejmě řetězce jsou právě ty uspořádané množiny, v nichž kterékoliv dva prvky jsou srovnatelné. V protiřetězcích naopak každé dva navzájem různé prvky jsou nesrovnatelné.
Je-li (A, <) uspořádaná množina, tedy je-li < uspořádání na množině A, a je-li dále B C A jakákliv podmnožina, pak průnik relace < s kartézským součinem B x B je relací na množině B a je to opět uspořádání, tentokrát ovšem na B. Mluvíme o uspořádání na B, které je indukováno uspořádáním <. Příslušnou takto vzniklou uspořádanou množinu značíme jednoduše (B, <).
Příklad. Vezměme množinu
N = {1,2,3,...}
všech přirozených čísel a zvolme libovolné číslo k G N. Označme
N(fc) ={£GN| £\k}
množinu všech těch přirozených čísel, která dělí číslo k. Pak máme N(fc) C N C o; a můžeme uvažovat uspořádanou množinu (N(fc), |) s uspořádáním relací dělitelnosti indukovaným z celé uspořádané množiny (o;, |).
Řekneme, že v uspořádané množině (A, <) prvek b G A pokrývá prvek a E A, jestliže a < b a přitom neeexistuje žádný prvek c E A, pro který by platilo a < c a c < b.
2
Uspořádanou množinu (A, <) můžeme, zejména je-li množina A konečná, znázornit graficky následujícím způsobem. Prvky z A znázorníme jako body v rovině tak, aby pro kterékoliv dva prvky a, b E A splňující a < b platilo, že bod b leží výše než bod a. To je možné, poněvadž uspořádání je antisymetrická relace. Dále ty dvojice bodů a, b E A splňujících a < b, kde prvek b pokrývá prvek a, pospojujeme úsečkami. Graf, který takto vznikne, se nazývá hasseovský diagram uspořádané množiny (A, <). Je jasné, že je-li množina A konečná, pak původní uspořádání < je možno z tohoto diagramu zpětně zrekonstruovat. To plyne z tranzit i vity a také z reflexivity uspořádání. Je tedy možno konečnou uspořádanou množinu zadat jejím hasseovským diagramem.
Příklad. Je možné kreslit hasseovské diagramy uspořádaných množin (N(fc), |) pro malá přirozená čísla k.
Příklad. Je možné kreslit hasseovské diagramy uspořádaných množin (V(A), C) pro konečné množiny A obashující malý počet prvků.
Je-li < uspořádání na množině A, pak inverzní relace <_1 je rovněž uspořádání na A a toto uspořádání obvykle značíme symbolem > . Příslušná uspořádaná množina (A, >) se pak nazývá duálně uspořádaná k množině (A, <). Je-li množina A konečná, potom hasseovský diagram uspořádané množiny (A, >) vznikne překlopením hasseovského diagramu množiny (A, <) „vzhůru nohama".
Buď (A, <) uspořádaná množina. Prvek a G A se nazývá nejmenší prvek v (A, <), je-li pro každé x E A splněno a < x. Prvek a G A se nazývá minimální prvek v (A, <), neexistuje-li prvek x E A splňující x < a, tedy je-li pro každé x E A splněno a < x nebo a \ \ x. Analogicky se definuje, co jsou největší prvek a maximální prvek v A.
3
Jiným způsobem řečeno, uvážíme-li pro danou uspořádanou množinu (A, <) k ní duálně uspořádanou množinu (A, >), pak prvek a G A je nej větším prvkem v (A, <) právě tehdy, když je nejmenším prvkem v (A, >). Podobně prvek a G A je maximálním prvkem v (A, <) právě tehdy, když je minimálním prvkem v (A, >). V tomto kontextu říkáme, že se jedná o navzájem duální pojmy.
Z antisymetrie uspořádání plyne, že pokud v nějaké uspořádané množině existuje nejmenší prvek, pak je tento prvek jediný. V tom případě je to současně také jediný minimální prvek dané uspořádané množiny. Obecně může v uspořádané množině být minimálních prvků více anebo nemusí existovat vůbec. V úplně uspořádaných množinách ovšem pojmy nej menšího a minimálního prvku splývají. Analogická tvrzení platí také pro nej větší a maximální prvky uspořádaných množin.
Příklad. V uspořádané množině (o;, |) je číslo 1 nejmenším prvkem a číslo 0 je největším prvkem. V uspořádané množině (N, |), kde oproti předchozímu chybí číslo 0, je číslo 1 stále nejmenším prvkem, avšak není zde největší prvek a neexistují zde ani žádné maximální prvky. V uspořádané množině (N — {1}, |) není nejmenší prvek a minimálními prvky jsou zde právě všechna prvočísla.
Je-li A neprázdná množina, pak v protiřetězci (A, Aa) jsou všechny prvky současně minimálními i maximálními prvky. Není-li přitom množina A jednoprvková, neexistují zde nejmenší ani největší prvek.
Nechť (A, <) a (B, C) jsou dvě uspořádané množiny a nechť / : A —y B je zobrazení. Řekneme, že zobrazení / je izotonní, je-li splněna podmínka
{Vx,y E A){x <y f(x)Qf(y)).
4
Příklad. Identické zobrazení id^ na množině N všech přirozených čísel je očividně izotonním zobrazením uspořádané množiny (N, |) s uspořádáním daným dělitelností čidel na uspořádanou množinu (N, <) s obvyklým uspořádáním čísel podle velikosti.
Poznamenejme také, že pro libovolnou uspořádanou množinu (A Je identita idA na A izotonním zobrazením protiřetězce (A, Aa) na množinu (A, <).
Nechť dále opět (A, <) a (B, C) jsou uspořádané množiny a nechť / : A —>• B je zobrazení. Řekneme, že zobrazení / je izomorfismus, jestliže / je bijekce a obě zobrazení / i f~l jsou izotonní. Uvedené požadavky izotonie lze za předpokladu, že / je bijekce, vyjádřit ekvivalentní podmínkou
{Vx,yEA){x<y <=^> f(x)Qf(y)).
Volně řečeno to znamená, že obě uspořádané množiny (A, <) a (B, C) jsou vlastně jenom dvěma kopiemi jedné a téže uspořádané množiny. O takových uspořádaných množinách říkáme, že jsou izomorfní.
Je vhodné si uvědomit, že požadavek, aby také inverzní zobrazení f~l bylo izotonní, nelze v předchozí definici vynechat. Tak v předcházejícím příkladu je identita id^ bijekcí a izotonním zobrazením množiny (N, |) na množinu (N, <), ale tyto množiny nejsou izomorfní.
Buď (A, <) uspořádaná množina. Řekneme, že podmnožina B C A je hustá v (A, <), jestliže pro každá x, y G A splňující x < y existuje z E B takové, že platí x < z < y.
Nechť (A, <) je úplně uspořádaná množina, tedy řetězec, a nechť G, H C A jsou neprázdné podmnožiny. Řekneme, že uspořádaná dvojice (G,H) je řez v množině (A,<), platí-li
5
následující podmínky:
GU H = A, GHH = 0,
{\/x £G){\/y £ H)(x <y).
Je zřejmé, že pak platí také podmínky:
(Va G A)(Vx £ G)(a < x =>- a £ G), {Vb£A){Vy£H){y<b b £ H).
Ve skutečnosti je každá z těchto dvou podmínek ekvivalentní třetí ze shora uvedených podmínek. Řez (G, H) v řetězci (A, <) se nazývá
skok, obsahuje-li G největší prvek a H nejmenší prvek,
mezera, neobsahuje-li G největší prvek ani H nejmenší prvek,
dedekindovský řez 1. druhu, obsahuje-li G největší prvek, avšak H neobsahuje nejmenší prvek,
dedekindovský řez 2. druhu, neobsahuje-li G největší prvek, avšak H obsahuje nejmenší prvek.
Je evidentní, že při obvyklém uspořádání čísel podle velikosti je v řetězci (Z, <) každý řez skokem, zatímco v řetězci (Q, <) žádný skok není. V tomto řetězci ovšem pro každé q £ Q jsou
({x £ Q| x < q}, {y £ Q| q < y}), resp. {{x£Q\ x<q}, {y£Q\ q < y})
dedekindovské řezy 1., resp. 2. druhu a vedle toho pro každé r £ R-Q
({x £ Q | x < r}, {y £ Q | r < y} )
je mezera.
6
Dedekindova konstrukce reálných čísel
Ukážeme jeden ze způsobů, jak lze s pomocí množiny Q všech racionálních čísel sestrojit množinu R všech reálných čísel.
Označme 1Z množinu všech dedekindovských řezů 1. druhu a všech mezer v řetězci (Q, <). Na množině 1Z definujeme relaci ^ následujícím předpisem. Pro libovolné dva řezy (G, H), (K, Ľ) G 1Z klademe:
(G,H)±(K,L) <^ G C K <^ L C H.
Je jasné, že pak ■< je úplné uspořádání na 1Z, takže (1Z, ^) je řetězec. Lze ukázat, že pak zobrazení
dané pro každé r G M předpisem
C(r) = ({x G Q| x < r}, {y G Q| r < y})
je izomorŕismus řetězce (R, <) s obvyklým uspořádáním čísel na řetězec (1Z, ^). V tomto izomorŕismu racionálním číslům odpovídají dedekindovské řezy 1. druhu a iracionálním číslům odpovídají mezery. Chceme-li tedy konstruovat množinu R pomocí Q, nabízí se možnost položit ji přímo rovnu výše uvedené množině řezů 1Z.
Pak lze dokázat například následující fakt.
Tvrzení. Množina Q je hustá v řetězci (R, <).
Důkaz. Nechť x, y G R splňují x < y a nechť £(x) = (G, H) a £(y) = (K, L) jsou odpovídající řezy v 1Z. To znamená, že pak (G, H) -< (K, L), čili podle předchozí definice máme L C H, avšak L ^ H. Existuje tedy z G Q takové, že z G H — L, takže z G H n K. Ve skutečnosti ale existují alespoň dvě z, z' G Q splňující například z < z' taková, že z, z' G H — L, a tedy z, z' G H H K. Kdyby totiž množina H — L byla jednoprvková,
7
bylo by z G H — L nej menším prvkem množiny H, což z definice množiny řezů 1Z není možné. Pro řez = (M, N) pak odtud plyne L C N C poněvadž N = {u G Q| z < w}, avšak L ^ N ^ H, poněvadž z'eN-L&zEH-N. To ukazuje, že platí (G, H) -< (M, N) -< (K, L), odkud zase s ohledem na izomorŕismus £ plyne x < z < y. Je tedy množina Q hustá v (R,<).
8