Svazy Jan Paseka Masarykova univerzita Brno Svazy ­ p.1/37 Abstrakt Zmíníme se krátce o úplných a distributivních svazech, resp. jaké vlastnosti má řetězec reálných čísel. Svazy ­ p.2/37 Abstrakt V této kapitole budeme podrobněji studovat speciální uspořádané množiny ­ Zmíníme se krátce o úplných a distributivních svazech, resp. jaké vlastnosti má řetězec reálných čísel. Svazy ­ p.2/37 Abstrakt V této kapitole budeme podrobněji studovat speciální uspořádané množiny ­ svazy. Zmíníme se krátce o úplných a distributivních svazech, resp. jaké vlastnosti má řetězec reálných čísel. Svazy ­ p.2/37 Obsah přednášky Dolní závora a horní závora. Suprema a infima. Svazy a úplné svazy. Svazy ­ p.3/37 Obsah přednášky Dolní závora a horní závora. Suprema a infima. Svazy a úplné svazy. Suprema a infima ohraničených množin reálných čísel. Svazy jako algebraická struktura. Distributivní svazy. Svazy ­ p.3/37 Dolní závora Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá dolní závora množiny B, jestliže pro každý prvek b B platí a b. Svazy ­ p.4/37 Dolní závora Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá dolní závora množiny B, jestliže pro každý prvek b B platí a b. Podmnožina B A se nazývá zdola ohraničená, má-li alespoň jednu dolní závoru v (A, ). Svazy ­ p.4/37 Příklad dolní závora Příklad Z 1. V hasseovském diagramu a) je např. prvek {a} nebo prvek dolní závorou množiny {{a, b}, {a, c}}. Jiné dolní závory množina {{a, b}, {a, c}} nemá. ¤§¨ a) Svazy ­ p.5/37 Horní závora Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá horní závora množiny B, jestliže pro každý prvek b B platí a b. Svazy ­ p.6/37 Horní závora Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá horní závora množiny B, jestliže pro každý prvek b B platí a b. Podmnožina B A se nazývá shora ohraničená, má-li alespoň jednu horní závoru v (A, ). Svazy ­ p.6/37 Příklad horní závora Příklad Z 2. V hasseovském diagramu b) uspořádané množiny (N, | ) je každé přirozené číslo dělitelné šesti horní závorou množiny {2, 3}. Jiné horní závory množina {2, 3} nemá. ¤§¨ b) Svazy ­ p.7/37 Duální pojmy Horní závora a dolní závora jsou duální pojmy. Svazy ­ p.8/37 Duální pojmy Horní závora a dolní závora jsou duální pojmy. Prvek a A je horní závorou množiny B v (A, ) právě tehdy, když tento prvek je dolní závorou množiny B v duálně uspořádané množině (A, ). Svazy ­ p.8/37 Duální pojmy Horní závora a dolní závora jsou duální pojmy. Prvek a A je horní závorou množiny B v (A, ) právě tehdy, když tento prvek je dolní závorou množiny B v duálně uspořádané množině (A, ). Podmnožina B je shora ohraničená v (A, ) právě tehdy, když je zdola ohraničená v (A, ). Svazy ­ p.8/37 Příklad dolní a horní závora Příklad Z 3. V hasseovském diagramu c) uspořádané množiny (N, ) je každé přirozené číslo ostře větší než 2 horní závorou množiny {2, 3} a každé přirozené číslo ostře menší než 3 dolní závorou množiny {2, 3}. Jiné horní resp. dolní závory množina {2, 3} nemá. c) Svazy ­ p.9/37 Infimum Bud' (A, ) uspořádaná množina a B A podmnožina. Svazy ­ p.10/37 Infimum Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá infimum množiny B, jestliže a je dolní závora množiny B a pro každou dolní závoru c A množiny B platí c a. Svazy ­ p.10/37 Infimum Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá infimum množiny B, jestliže a je dolní závora množiny B a pro každou dolní závoru c A množiny B platí c a. Takový prvek a je největší dolní závorou množiny B. Infimum množiny B, pokud existuje, je určeno jednoznačně a značí se symbolem inf B. Svazy ­ p.10/37 Příklady infima I Příklad U 1. V uspořádané množině (N, ) má každá neprázdná podmnožina M N infimum inf M ­ je jím nejmenší číslo v M. Svazy ­ p.11/37 Příklady infima I Příklad U 1. V uspořádané množině (N, ) má každá neprázdná podmnožina M N infimum inf M ­ je jím nejmenší číslo v M. Pro prázdnou množinu jakožto podmnožinu v N pak infimum neexistuje. Totiž každé číslo m N je dolní závorou prázdné množiny a (N, ) nemá největší prvek. Svazy ­ p.11/37 Příklady infima II Příklad U 2. V uspořádané množině (N, | ) má každá neprázdná podmnožina M N infimum inf M ­ je jím největší společný dělitel čísel obsažených v M. Svazy ­ p.12/37 Příklady infima II Příklad U 2. V uspořádané množině (N, | ) má každá neprázdná podmnožina M N infimum inf M ­ je jím největší společný dělitel čísel obsažených v M. Pro prázdnou množinu jakožto podmnožinu v N pak infimum neexistuje. Totiž každé číslo m N je dolní závorou prázdné množiny a (N, | ) nemá největší prvek. Svazy ­ p.12/37 Supremum Bud' (A, ) uspořádaná množina a B A podmnožina. Svazy ­ p.13/37 Supremum Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá supremum množiny B, jestliže a je horní závora B a pro každou horní závoru c A množiny B platí c a. Svazy ­ p.13/37 Supremum Bud' (A, ) uspořádaná množina a B A podmnožina. Prvek a A se nazývá supremum množiny B, jestliže a je horní závora B a pro každou horní závoru c A množiny B platí c a. Takový prvek a je nejmenší horní závorou množiny B. Supremum množiny B, pokud existuje, je určeno jednoznačně a značí se symbolem sup B. Svazy ­ p.13/37 Supremum a infimum A a Bud' (A, ) uspořádaná množina. Pak inf A a sup existují právě tehdy, když v A existuje nejmenší prvek , a v tom případě platí inf A = sup = . Svazy ­ p.14/37 Supremum a infimum A a Bud' (A, ) uspořádaná množina. Pak inf A a sup existují právě tehdy, když v A existuje nejmenší prvek , a v tom případě platí inf A = sup = . Duální tvrzení platí pro sup A a inf . Svazy ­ p.14/37 Supremum a infimum A a Bud' (A, ) uspořádaná množina. Pak inf A a sup existují právě tehdy, když v A existuje nejmenší prvek , a v tom případě platí inf A = sup = . Duální tvrzení platí pro sup A a inf . To znamená, že tyto prvky existují právě tehdy, když v A existuje největší prvek , a v tom případě platí sup A = inf = . Svazy ­ p.14/37 Supremum a infimum, svaz Bud' dále B A podmnožina. Existují-li prvky inf B, resp. sup B, pak každý z těchto prvků může, ale obecně nemusí ležet v samotné množině B. Svazy ­ p.15/37 Supremum a infimum, svaz Bud' dále B A podmnožina. Existují-li prvky inf B, resp. sup B, pak každý z těchto prvků může, ale obecně nemusí ležet v samotné množině B. První případ nastává právě tehdy, když množina B má nejmenší, resp. největší prvek. Tyto prvky pak představují prvky inf B, resp. sup B. Svazy ­ p.15/37 Supremum a infimum, svaz Bud' dále B A podmnožina. Existují-li prvky inf B, resp. sup B, pak každý z těchto prvků může, ale obecně nemusí ležet v samotné množině B. První případ nastává právě tehdy, když množina B má nejmenší, resp. největší prvek. Tyto prvky pak představují prvky inf B, resp. sup B. Uspořádaná množina (A, ), v níž pro libovolné prvky a, b A existují sup{a, b} a inf{a, b}, se na- zývá svaz. Svazy ­ p.15/37 Příklady svazu Příklad S 1. První hasseovský diagram je svaz, druhý ne (stačí uvážit supremum množiny {a1, a2}). Svazy ­ p.16/37 Ú plný svaz Uspořádaná množina (A, ), v níž pro libovolnou podmnožinu B A existují sup B a inf B, se nazývá úplný svaz. Svazy ­ p.17/37 Ú plný svaz Uspořádaná množina (A, ), v níž pro libovolnou podmnožinu B A existují sup B a inf B, se nazývá úplný svaz. V uspořádané množině (A, ) pro libovolné prvky a, b A platí a b inf{a, b} = a sup{a, b} = b. Svazy ­ p.17/37 Ú plný svaz Uspořádaná množina (A, ), v níž pro libovolnou podmnožinu B A existují sup B a inf B, se nazývá úplný svaz. V uspořádané množině (A, ) pro libovolné prvky a, b A platí a b inf{a, b} = a sup{a, b} = b. Tedy každý řetězec je svaz. Jsou ale řetězce, které nejsou úplnými svazy ­ například řetězec (Q, ). Svazy ­ p.17/37 Příklady úplného svazu I Příklad S 2. Oba hasseovské diagramy jsou úplné svazy, pokud je řetězec množina přirozených čísel. Pokud bude řetězec tvořen nezápornými racionálními čísly, úplnými svazy nebudou. Svazy ­ p.18/37 Příklady úplného svazu II Příklad S 3. Hasseovský diagram uspořádané množiny D180 znázorňuje úplný svaz. Svazy ­ p.19/37 Příklady úplného svazu III Příklad S 4. Bud' A množina a bud' P(A) její potenční množina. Svazy ­ p.20/37 Příklady úplného svazu III Příklad S 4. Bud' A množina a bud' P(A) její potenční množina. Pak v uspořádané množině (P(A), ) libovolná podmnožina Q P(A) má supremum i infimum a platí pro ně Svazy ­ p.20/37 Příklady úplného svazu III Příklad S 4. Bud' A množina a bud' P(A) její potenční množina. Pak v uspořádané množině (P(A), ) libovolná podmnožina Q P(A) má supremum i infimum a platí pro ně sup Q = Q , inf Q = Q . Svazy ­ p.20/37 Příklady úplného svazu III Příklad S 4. Bud' A množina a bud' P(A) její potenční množina. Pak v uspořádané množině (P(A), ) libovolná podmnožina Q P(A) má supremum i infimum a platí pro ně sup Q = Q , inf Q = Q . (Přitom pro podmnožinu P(A) zde chápeme jako A.) Je tedy (P(A), ) úplný svaz. Svazy ­ p.20/37 Příklady úplného svazu IV Příklad S 5. Bud' A množina. Připomeňme, že symbolem E(A) jsme značili množinu všech ekvivalencí na A. Svazy ­ p.21/37 Příklady úplného svazu IV Příklad S 5. Bud' A množina. Připomeňme, že symbolem E(A) jsme značili množinu všech ekvivalencí na A. Tyto ekvivalence jakožto relace na A, tedy jakožto podmnožiny v A × A lze porovnávat množinovou inkluzí . Svazy ­ p.21/37 Příklady úplného svazu IV Příklad S 5. Bud' A množina. Připomeňme, že symbolem E(A) jsme značili množinu všech ekvivalencí na A. Tyto ekvivalence jakožto relace na A, tedy jakožto podmnožiny v A × A lze porovnávat množinovou inkluzí . Vzniká tak uspořádaná množina (E(A), ), která tvoří úplný svaz. Svazy ­ p.21/37 Příklady úplného svazu IV Příklad S 5. Bud' A množina. Připomeňme, že symbolem E(A) jsme značili množinu všech ekvivalencí na A. Tyto ekvivalence jakožto relace na A, tedy jakožto podmnožiny v A × A lze porovnávat množinovou inkluzí . Vzniká tak uspořádaná množina (E(A), ), která tvoří úplný svaz. Pro libovolné podmnožiny G, H E(A) existuje inf G = G a sup H = G H, kde GH = {R E(A) : H R H H}. Svazy ­ p.21/37 Konečná suprema ve svazu Tvrzení. Bud' (A, ) svaz. Pak pro libovolnou neprázdnou konečnou podmnožinu B A existují sup B a inf B. Svazy ­ p.22/37 Konečná suprema ve svazu Tvrzení. Bud' (A, ) svaz. Pak pro libovolnou neprázdnou konečnou podmnožinu B A existují sup B a inf B. Důsledek. Každý konečný neprázdný svaz je úplný. Svazy ­ p.22/37 Konečná suprema ve svazu Tvrzení. Bud' (A, ) svaz. Pak pro libovolnou neprázdnou konečnou podmnožinu B A existují sup B a inf B. Důsledek. Každý konečný neprázdný svaz je úplný. Věta. Bud' (A, ) uspořádaná množina, v níž pro každou podmnožinu B A existuje inf B. Pak pro libovolnou podmnožinu C A existuje také sup C. Svazy ­ p.22/37 Ř etězec reálných čísel Tvrzení. Každá neprázdná zdola ohraničená podmnožina M R má infimum v (R, ). Svazy ­ p.23/37 Ř etězec reálných čísel Tvrzení. Každá neprázdná zdola ohraničená podmnožina M R má infimum v (R, ). Každá neprázdná shora ohraničená podmnožina N R má supremum v (R, ). Svazy ­ p.23/37 Ř etězec reálných čísel Tvrzení. Každá neprázdná zdola ohraničená podmnožina M R má infimum v (R, ). Každá neprázdná shora ohraničená podmnožina N R má supremum v (R, ). Připojme k množině R dva nové prvky - a a rozšiřme uspořádání z R na R {-, } tak, aby pro každé r R platilo - < r < . Tímto způsobem vzniká řetězec (R {-, }, ). Důsledek. Ř etězec (R {-, }, ) je úplný svaz. Svazy ­ p.23/37 Ř etězec reálných čísel Tvrzení. Každá neprázdná zdola ohraničená podmnožina M R má infimum v (R, ). Každá neprázdná shora ohraničená podmnožina N R má supremum v (R, ). Připojme k množině R dva nové prvky - a a rozšiřme uspořádání z R na R {-, } tak, aby pro každé r R platilo - < r < . Tímto způsobem vzniká řetězec (R {-, }, ). Důsledek. Ř etězec (R {-, }, ) je úplný svaz. Svazy ­ p.23/37 Značení Je-li (A, ) svaz, pak pro libovolné prvky a, b A prvek sup{a, b} značíme krátce jako a b a prvek inf{a, b} značíme krátce jako a b. Svazy ­ p.24/37 Značení Je-li (A, ) svaz, pak pro libovolné prvky a, b A prvek sup{a, b} značíme krátce jako a b a prvek inf{a, b} značíme krátce jako a b. Takto jsou současně definována také dvě zobrazení : A × A A a : A × A A přiřazující každé dvojici (a, b) A × A prvek a b, případně a b. Svazy ­ p.24/37 Svaz jako algebraická struktura Tvrzení. Bud' (A, ) svaz. Potom pro libovolné prvky a, b, c A platí následující rovnosti: a a = a a a = a (idempotence ) (idempotence ) Svazy ­ p.25/37 Svaz jako algebraická struktura Tvrzení. Bud' (A, ) svaz. Potom pro libovolné prvky a, b, c A platí následující rovnosti: a a = a a b = b a a a = a a b = b a (idempotence ) (komutativita ) (idempotence ) (komutativita ) Svazy ­ p.26/37 Svaz jako algebraická struktura Tvrzení. Bud' (A, ) svaz. Potom pro libovolné prvky a, b, c A platí následující rovnosti: a a = a a b = b a (a b) c = a (b c) a a = a a b = b a (a b) c = a (b c) (idempotence ) (komutativita ) (asociativita ) (idempotence ) (komutativita ) (asociativita ) Svazy ­ p.27/37 Svaz jako algebraická struktura Tvrzení. Bud' (A, ) svaz. Potom pro libovolné prvky a, b, c A platí následující rovnosti: a a = a a b = b a (a b) c = a (b c) a (a b) = a a a = a a b = b a (a b) c = a (b c) a (a b) = a (idempotence ) (komutativita ) (asociativita ) (absorbce) (idempotence ) (komutativita ) (asociativita ) (absorbce) Svazy ­ p.28/37 Rovnocennost pohledu na svazy I Začněme nejprve se svazem (A, ), na němž výše uvedeným způsobem vznikají binární operace , : A × A A, Svazy ­ p.29/37 Rovnocennost pohledu na svazy I Začněme nejprve se svazem (A, ), na němž výše uvedeným způsobem vznikají binární operace , : A × A A, Dostáváme algebraickou strukturu (A, , ), v níž jsou splněny výše uvedené rovnosti. Svazy ­ p.29/37 Rovnocennost pohledu na svazy I Začněme nejprve se svazem (A, ), na němž výše uvedeným způsobem vznikají binární operace , : A × A A, Dostáváme algebraickou strukturu (A, , ), v níž jsou splněny výše uvedené rovnosti. V (A, ) pro libovolné prvky a, b A platí a b a b = a a b = b. Svazy ­ p.29/37 Rovnocennost pohledu na svazy I Začněme nejprve se svazem (A, ), na němž výše uvedeným způsobem vznikají binární operace , : A × A A, Dostáváme algebraickou strukturu (A, , ), v níž jsou splněny výše uvedené rovnosti. V (A, ) pro libovolné prvky a, b A platí a b a b = a a b = b. Známe-li algebru (A, , ), můžeme z ní uspořádanou množinu (A, ) zpět rekonstruovat. Svazy ­ p.29/37 Rovnocennost pohledu na svazy II Necht' (A, , ) je algebra splňující uvedené rovnosti. Svazy ­ p.30/37 Rovnocennost pohledu na svazy II Necht' (A, , ) je algebra splňující uvedené rovnosti. Pak předchozí formulí je možno k ní pořídit uspořádanou množinu (A, ), která bude svazem, přičemž algebra odvozená z tohoto svazu bude totožná s algebrou výchozí. Svazy ­ p.30/37 Rovnocennost pohledu na svazy III Tvrzení. Bud' (A, , ) množina se dvěma binárními operacemi vyhovujícími všem podmínkám z předchozího tvrzení. Svazy ­ p.31/37 Rovnocennost pohledu na svazy III Tvrzení. Bud' (A, , ) množina se dvěma binárními operacemi vyhovujícími všem podmínkám z předchozího tvrzení. Pak relace na A definovaná pro každá a, b A předpisem a b a b = a a b = b je uspořádání a (A, ) je svaz. Svazy ­ p.31/37 Rovnocennost pohledu na svazy III Tvrzení. Bud' (A, , ) množina se dvěma binárními operacemi vyhovujícími všem podmínkám z předchozího tvrzení. Pak relace na A definovaná pro každá a, b A předpisem a b a b = a a b = b je uspořádání a (A, ) je svaz. Navíc pak v tomto svazu platí, že pro libovolná a, b A je sup{a, b} = a b a inf{a, b} = a b. Svazy ­ p.31/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: Svazy ­ p.32/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), Svazy ­ p.32/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), () (e, f, g A)(e (f g) = (e f) (e g)). Svazy ­ p.32/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), () (e, f, g A)(e (f g) = (e f) (e g)). Svaz (A, ) splňující kteroukoliv z podmínek (), () uvedených v předchozím tvrzení se nazývá distributivní. Svazy ­ p.32/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), () (e, f, g A)(e (f g) = (e f) (e g)). Svaz (A, ) splňující kteroukoliv z podmínek (), () uvedených v předchozím tvrzení se nazývá distributivní. Distributivita je samoduální vlast- nost. Svazy ­ p.32/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: Svazy ­ p.33/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), Svazy ­ p.33/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), () (e, f, g A)(e (f g) = (e f) (e g)). Svazy ­ p.33/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), () (e, f, g A)(e (f g) = (e f) (e g)). Svaz (A, ) splňující kteroukoliv z podmínek (), () uvedených v předchozím tvrzení se nazývá distributivní. Svazy ­ p.33/37 Distributivní svazy I Tvrzení. Bud' (A, ) libovolný svaz. Pak jsou následující dvě podmínky ekvivalentní: () (a, b, c A)(a (b c) = (a b) (a c)), () (e, f, g A)(e (f g) = (e f) (e g)). Svaz (A, ) splňující kteroukoliv z podmínek (), () uvedených v předchozím tvrzení se nazývá distributivní. Distributivita je samoduální vlast- nost. Svazy ­ p.33/37 Příklady distributivních svazů I Příklad D 1. Následující hasseovské diagramy znázorňují úplné svazy, které jsou distributivní. Svazy ­ p.34/37 Příklady nedistributivních svazů I Příklad D 2. Následující hasseovské diagramy znázorňují úplné svazy, které nejsou distributivní. Svazy ­ p.35/37 Příklady nedistributivních svazů I Příklad D 2. Následující hasseovské diagramy znázorňují úplné svazy, které nejsou distributivní. Například v uspořádané množině Mn, n 3, máme rovnosti a1 a3 = = a2 a3, tj. (a1 a3) (a2 a3) = , ale (a1 a2) a3 = a3 = . Svazy ­ p.35/37 Příklady nedistributivních svazů I Příklad D 2. Následující hasseovské diagramy znázorňují úplné svazy, které nejsou distributivní. Svazy ­ p.36/37 Příklady nedistributivních svazů I Příklad D 2. Následující hasseovské diagramy znázorňují úplné svazy, které nejsou distributivní. V uspořádané množině N máme rovnosti ac = a, bc = , tj. (a c) (b c) = a, ale (a b) c = c = a. Svazy ­ p.36/37 Příklady distributivních svazů II Příklad D 3. Následující hasseovský diagram znázorňuje úplný distributivní svaz, který vznikl jako kartézský součin prvního a třetího svazu z příkladu D 1. Svazy ­ p.37/37