Matematick´y ustav ´ Slezske´ univerzity v Opaveˇ Uˇcebn´ı texty k pˇrednaˇ ´ sce ALGEBRA I, zimní semestr 2000/2001 Michal Marvan
8. Uspoˇra´ d´an´ı a svazy Uspoˇra´ d´an´ı je dalˇs´ı uˇziteˇcn´a abstraktn´ı struktura na mnoˇzinˇe. Modeluje takov´e vztahy mezi prvky jako vˇetˇs´ı (menˇs´ı), obsaˇzen´y (obsahuj´ıc´ı) apod. Pˇrid´av´an´ım podm´ınek postupnˇe dojdeme ke speci´aln´ım uspoˇra´ dan´ym mnoˇzin´am – svaz˚um a Booleov´ym algebr´am –, kter´e jsou z´aroveˇn algebrami se dvˇema bin´arn´ımi operacemi a maj´ı d˚uleˇzit´e aplikace, zejm´ena v informatice.
1. Uspoˇra´ dan´e mnoˇziny Pˇripomeˇnme, zˇ e relace na mnoˇzinˇe M je libovoln´a podmnoˇzina kart´ezsk´eho souˇcinu M 2 = M × M . Je-li ρ ⊆ M 2 relace, pak vztah (x, y) ∈ ρ zapisujeme x ρ y . Definice. Bud’ d´ana mnoˇzina M . Relace ρ na M se naz´yv´a 1◦ reflexivn´ı, plat´ı-li aρa pro vˇsechna a ∈ M , 2◦ antisymetrick´a, plat´ı-li implikace aρb, bρa ⇒ a = b, 3◦ tranzitivn´ı, plat´ı-li implikace aρb, bρc ⇒ aρc. Relace, kter´a je reflexivn´ı, antisymetrick´a a tranzitivn´ı z´aroveˇn, se naz´yv´a uspoˇra´ d´an´ı. Dvojice (M, ρ) se pak naz´yv´a uspoˇra´ dan´a mnoˇzina. Pˇr´ıklady. 0) Na kaˇzd´e mnoˇzinˇe M je identick´a relace id M uspoˇra´ d´an´ım (pˇripomeˇnme, zˇ e a id M b ⇔ a = b). 1) (R, ≤), (Z, ≤), (N, ≤) atd. jsou uspoˇra´ dan´e mnoˇziny, je-li ≤ obvykl´e uspoˇra´ d´an´ı cˇ´ısel podle velikosti. 2) Bud’ M mnoˇzina, bud’ P(M) mnoˇzina vˇsech podmnoˇzin mnoˇziny M. Inkluze ⊆ je uspoˇra´ d´an´ı na P(M) a (P(M), ⊆) je uspoˇra´ dan´a mnoˇzina. 3) (N, |), kde a|b (ˇcteme a dˇel´ı b) pr´avˇe tehdy, kdyˇz existuje m ∈ N takov´e, zˇ e am = b. Relace ,, | “ se naz´yv´a relace dˇelitelnosti a je uspoˇra´ d´an´ım. Podejme d˚ukaz antisymetrie. Jestliˇze a|b a b|a, pak existuj´ı m, n ∈ N takov´a, zˇ e am = b a bn = a. Odtud a = amn, ale a = 0, naˇceˇz 1 = mn. Rovnice 1 = mn vˇsak m´a v pˇrirozen´ych cˇ´ıslech jedin´e rˇeˇsen´ı: m = 1 a n = 1. Potom b = a · 1 = a. Upozornˇeme, zˇ e analogicky definovan´a relace dˇelitelnosti na mnoˇzinˇe Z cel´ych cˇ´ısel nen´ı antisymmetrick´a, protoˇze 1|−1 a −1|1, a pˇresto 1 = −1 (to souvis´ı s t´ım, zˇ e rovnice 1 = mn m´a v cel´ych cˇ´ıslech jeˇstˇe dalˇs´ı ˇreˇsen´ı m = −1 a n = −1).
Bud’ ρ uspoˇra´ d´an´ı na mnoˇzinˇe M . Opaˇcn´a relace ρ −1 (tj. relace definovan´a pˇredpisem ,,aρ −1 b ˇ pr´avˇe kdyˇz bρa “) je zase uspoˇra´ d´an´ı. Naz´yv´a se du´aln´ı uspoˇra´ d´an´ı. Casto se obecn´e uspoˇra´ d´an´ı −1 oznaˇcuje symbolem ,,≤“. Du´aln´ı uspoˇra´ d´an´ı ≤ se pak oznaˇcuje symbolem ,,≥“: a ≥ b pr´avˇe tehdy, kdyˇz b ≤ a . Podobnˇe nakl´ad´ame se symboly ,,⊆“ atp. Kaˇzd´a podmnoˇzina N ⊆ M uspoˇra´ dan´e mnoˇziny (M, ≤) je opˇet uspoˇra´ dan´a mnoˇzina. Relace ≤ N , zadan´a pro libovoln´a x, y ∈ N pˇredpisem x ≤ N y ⇔ x ≤ y , je totiˇz uspoˇra´ d´an´ı na N . Naz´yv´a se indukovan´e uspoˇra´ d´an´ı a znaˇc´ı se rovnˇezˇ ≤.
8. Uspoˇra´ d´an´ı a svazy
Pˇr´ıklady. 1) Pˇrirozen´e uspoˇra´ d´an´ı ≤ na mnoˇzinˇe N je totoˇzn´e s uspoˇra´ d´an´ım indukovan´ym z pˇrirozen´eho uspoˇra´ d´an´ı mnoˇziny Z. Tot´ezˇ plat´ı pro dalˇs´ı dvojice z mnoˇzin N, Z, Q, R. 2) Bud’ A mnoˇzina, uvaˇzujme o mnoˇzinˇe A2 = A × A. Mnoˇzina vˇsech podmnoˇzin mnoˇziny A2 , cˇ ili P(A2 ), je vlastnˇe mnoˇzina vˇsech bin´arn´ıch relac´ı na mnoˇzinˇe A. Inkluze ⊆ pak pˇredstavuje uspoˇra´ d´an´ı na P(A2 ). Pˇritom ρ⊆σ pr´avˇe tehdy, kdyˇz plat´ı implikace (x, y) ∈ ρ ⇒ (x, y) ∈ σ , to jest, implikace xρy ⇒ xσ y.
ˇ Definice. Rekneme, zˇ e prvky a, b uspoˇra´ dan´e mnoˇziny M jsou srovnateln´e, plat´ı-li a ≤ b nebo a ≥ b. Uspoˇra´ dan´a mnoˇzina M se naz´yv´a rˇ etˇezec, jsou-li kaˇzd´e dva prvky a, b ∈ M srovnateln´e. Pˇr´ıklad. (R, ≤), (Z, ≤), (N, ≤) atd. jsou ˇretˇezce. Cviˇcen´ı. Dokaˇzte, zˇ e kaˇzd´a podmnoˇzina ˇretˇezce je opˇet ˇretˇezec, vzhledem k indukovan´emu uspoˇra´ d´an´ı.
Bud’ ≤ uspoˇra´ d´an´ı na M . Zaved’me oznaˇcen´ı a < b, jestliˇze a ≤ b a z´aroveˇn a = b. D´ale zaved’me oznaˇcen´ı a <◦ b, jestliˇze a < b a neexistuje c ∈ M takov´e, zˇ e a < c, c < b. Je-li a <◦ b, pak ˇr´ık´ame, zˇ e prvek b pokr´yv´a prvek a . Pˇr´ıklady. 1) V mnoˇzinˇe N s pˇrirozen´ym upoˇra´ d´an´ım podle velikosti plat´ı 1 < 2 a 1 <◦ 2. D´ale plat´ı 1 < 3 ale nikoliv 1 <◦ 3. 2) V mnoˇzinˇe Q vˇsech racion´aln´ıch cˇ´ısel s pˇrirozen´ym uspoˇra´ d´an´ım neplat´ı a <◦ b pro zˇ a´ dnou dvojici a < b. Skuteˇcnˇe, prvek c = 12 (a + b) pak splˇnuje a < c, c < b.
Koneˇcnou uspoˇra´ danou mnoˇzinu (M, ≤) m˚uzˇ eme zn´azornit diagramem. Prvky mnoˇziny M zn´azorn´ıme jako body v rovinˇe, v n´ızˇ je zad´an horizont´aln´ı smˇer. Prvky a, b, splˇnuj´ıc´ı a <◦ b vyznaˇc´ıme tak, zˇ e a leˇz´ı n´ızˇ e neˇz b a spoj´ıme je u´ seˇckou. Z diagramu pak m˚uzˇ eme urˇcit uspoˇra´ d´an´ı mnoˇziny M : a ≤ b pr´avˇe tehdy, kdyˇz a leˇz´ı n´ızˇ e neˇz b a existuje zdola nahoru smˇeˇruj´ıc´ı posloupnost na sebe navazuj´ıc´ıch u´ seˇcek z bodu a do bodu b. Pˇr´ıklad. V uspoˇra´ dn´e mnoˇzinˇe Y s diagramem vpravo plat´ı: – c <◦ a, c <◦ b, d <◦ c; – d < a, ale nikoliv d <◦ a; – prvky a, b jsou nesrovnateln´e.
a
b c d
Cviˇcen´ı. Nakreslete diagram 1) cˇ tyˇrprvkov´eho ˇretˇezce; 2) uspoˇra´ dan´e mnoˇziny du´aln´ı k uspoˇra´ dan´e mnoˇzinˇe Y z pˇredchoz´ıho pˇr´ıkladu; 3) Uspoˇra´ d´an´e mnoˇziny (P(M), ⊆), je-li M jedno-, dvou-, tˇr´ı- a cˇ tyˇrprvkov´a mnoˇzina.
Definice. Bud’ (M, ≤) uspoˇra´ dan´a mnoˇzina. Prvek x ∈ M se naz´yv´a – nejmenˇs´ı, je-li x ≤ a pro vˇsechna a ∈ M ; – nejvˇetˇs´ı, je-li x ≥ a pro vˇsechna a ∈ M ; – maxim´aln´ı, neexistuje-li a ∈ M takov´y, zˇ e a > x ; – minim´aln´ı, neexistuje-li a ∈ M takov´y, zˇ e a < x . 2
8. Uspoˇra´ d´an´ı a svazy
Pˇr´ıklad. V uspoˇra´ dn´e mnoˇzinˇe Y z pˇredchoz´ıho pˇr´ıkladu plat´ı: – d je nejmenˇs´ı prvek a z´aroveˇn jedin´y prvek minim´aln´ı; – nejvˇetˇs´ı prvek neexistuje, zat´ımco a, b jsou dva prvky maxim´aln´ı; Cviˇcen´ı. Dokaˇzte: (1) V kaˇzd´e uspoˇra´ dan´e mnoˇzinˇe existuje nejv´ysˇe jeden nejvˇetˇs´ı a nejv´ysˇe jeden nejmenˇs´ı prvek. (2) Existuje-li nejmenˇs´ı prvek, pak je jedin´ym minim´aln´ım prvkem. Existuje-li nejvˇetˇs´ı prvek, pak je jedin´ym maxim´aln´ım prvkem.
Definice. Bud’ A ⊆ M podmnoˇzina uspoˇra´ dan´e mnoˇziny (M, ≤). Prvek x ∈ M se naz´yv´a – doln´ı z´avora mnoˇziny A, je-li x ≤ a pro vˇsechna a ∈ A; – horn´ı z´avora mnoˇziny A, je-li x ≥ a pro vˇsechna a ∈ A; – supremum mnoˇziny A, je-li x nejmenˇs´ı prvek mnoˇziny vˇsech horn´ıch z´avor mnoˇziny A; p´ısˇeme x = sup A; – infimum mnoˇziny A, je-li x nejvˇetˇs´ı prvek mnoˇziny vˇsech doln´ıch z´avor mnoˇziny A; p´ısˇeme x = inf A. Pˇr´ıklad. V naˇs´ı uspoˇra´ dn´e mnoˇzinˇe Y plat´ı: – podmnoˇzina { a, b } m´a doln´ı z´avory c, d, z nich nejvˇetˇs´ı je c, a proto inf{ a, b } = c. – podmnoˇzina { a, b } nem´a zˇ a´ dnou horn´ı z´avoru, a proto sup{ a, b } neexistuje (mnoˇzina horn´ıch z´avor je pr´azdn´a, a proto nem´a nejvˇetˇs´ı prvek). Cviˇcen´ı. Dokaˇzte: (1) Kaˇzd´a podmnoˇzina m´a nejv´ysˇe jedno supremum a nejv´ysˇe jedno infimum. (2) Jestliˇze x ≤ y, pak inf{ x, y } = x a sup{ x, y } = y. (3) Jestliˇze inf{ x, y } = x, pak x ≤ y. (4) Jestliˇze sup{ x, y } = y, pak x ≤ y.
Uvaˇzujme o matematick´em pojmu, v jehoˇz definici vystupuje nˇejak´e uspoˇra´ d´an´ı ≤. Nahrad´ımeli toto uspoˇra´ d´an´ı du´aln´ım uspoˇra´ d´an´ım ≥, obdrˇz´ıme definici du´aln´ıho pojmu. Tak napˇr´ıklad, du´aln´ım pojmem k pojmu nejmenˇs´ıho prvku je pojem nejvˇetˇs´ıho prvku. Bud’ A libovoln´e tvrzen´ı o uspoˇra´ d´an´ych mnoˇzin´ach. N´ahradou pojm˚u du´aln´ımi pojmy vznikne du´aln´ı tvrzen´ı B . Jestliˇze obecnˇe plat´ı tvrzen´ı A, pak obecnˇe plat´ı i du´aln´ı tvrzen´ı B . D˚ukaz tvrzen´ı B obdrˇz´ıme, nahrad´ıme-li ve vˇsech kroc´ıch d˚ukazu tvrzen´ı A vˇsechny pojmy pojmy du´aln´ımi. 2. Izotonn´ı zobrazen´ı Definice. Bud’te (M, ≤), (N , ≤) dvˇe uspoˇra´ dan´e mnoˇziny. Zobrazen´ı f : M → N se naz´yv´a izotonn´ı, jestliˇze plat´ı implikace a ≤ b ⇒ f (a) ≤ f (b). Je-li zobrazen´ı f bijektivn´ı a f i f −1 jsou izotonn´ı, pak ˇr´ık´ame, zˇ e f je izomorfismus uspoˇra´ dan´ych mnoˇzin, a zˇ e uspoˇra´ dan´e mnoˇziny (M, ≤), (N , ≤) jsou izomorfn´ı. Pˇr´ıklad. Identick´e zobrazen´ı id : (N, |) → (N, ≤) je izotonn´ı zobrazen´ı. Skuteˇcnˇe, jestliˇze a|b, pak b = na pro nˇejak´e n ∈ N, ale n ≥ 1, a proto b = na ≥ a. Inverzn´ı zobrazen´ı id : (N, ≤) → (N, |) nen´ı izotonn´ı zobrazen´ı, protoˇze neplat´ı implikace a ≤ b ⇒ a|b (napˇr´ıklad 2 ≤ 3, ale neplat´ı 2|3).
3
8. Uspoˇra´ d´an´ı a svazy
Pˇr´ıklad. Bud’te A = B = { 0, 1 } dvouprvkov´e mnoˇziny, opatˇren´e uspoˇra´ d´an´ım podle n´asleduj´ıc´ıch diagram˚u: A
f
B
Bud’ f : A → B identick´e zobrazen´ı. Pak f je izotonn´ı bijekce, jej´ızˇ inverze f −1 nen´ı izotonn´ı. Cviˇcen´ı. Dokaˇzte, zˇ e kompozice izotonn´ıch zobrazen´ı je izotonn´ı zobrazen´ı.
Svazy Definice. Bud’ (M, ≤) uspoˇra´ dan´a mnoˇzina. Necht’ pro kaˇzd´e dva prvky x, y ∈ M existuje infimum inf{ x, y } a supremum sup{ x, y }. Pak ˇr´ık´ame, zˇ e M je svazovˇe uspoˇra´ dan´a mnoˇzina. Pˇr´ıklady. 1) Bud’ M mnoˇzina, pak je (P(M), ⊆) svazovˇe uspoˇra´ dan´a mnoˇzina, pˇriˇcemˇz plat´ı inf{ X, Y } = X ∩ Y a sup{X, Y } = X ∪ Y pro libovoln´e prvky X, Y ∈ P(M). 2) (N, |) je svazovˇe uspoˇra´ dan´a mnoˇzina, pˇriˇcemˇz inf{ a, b } = nejvˇetˇs´ı spoleˇcn´y dˇelitel, sup{ a, b } = nejmenˇs´ı spoleˇcn´y n´asobek cˇ´ısel a, b ∈ N. 3) Kaˇzd´y ˇretˇezec (M, ≤) je svazovˇe uspoˇra´ dan´a mnoˇzina, pˇriˇcemˇz inf{ a, b } = min{ a, b } je menˇs´ı, resp. sup{ a, b } = max{ a, b } je vˇetˇs´ı z prvk˚u a, b ∈ M.
Tvrzen´ı. Bud’ (M, ≤) svazovˇe uspoˇra´ dan´a mnoˇzina. Oznaˇcme
x ∨ y := sup{ x, y },
x ∧ y := inf{ x, y }.
Pak
x x x x
∨ x = x, ∨ y = y ∨ x, ∨ (y ∨ z) = (x ∨ y) ∨ z, ∨ (y ∧ x) = x,
x x x x
∧ x = x, ∧ y = y ∧ x, ∧ (y ∧ z) = (x ∧ y) ∧ z, ∧ (y ∨ x) = x
(∗)
pro libovoln´a x, y, z ∈ M . Dukaz. ˚ Asociativita: Cviˇcen´ı. N´avod: Ukaˇzte, zˇ e x ∨ (y ∨ z) = sup{ x, y, z } = (x ∨ y) ∨ z . Zbytek: Cviˇcen´ı. Cviˇcen´ı. Dokaˇzte, zˇ e x1 ∨ x2 ∨ · · · ∨ xn = sup{ x1 , x2 , . . . , xn }. (Vlevo nez´aleˇz´ı na uz´avorkov´an´ı, protoˇze operace je asociativn´ı.)
Definice. Algebraick´a struktura (M, ∧, ∨) se dvˇema bin´arn´ımi operacemi ∧ a ∨ se naz´yv´a svaz, jestliˇze jsou splnˇeny podm´ınky (∗). Bin´arn´ı operace ∧ se naz´yv´a pr˚usek, bin´arn´ı operace ∨ se naz´yv´a spojen´ı. Uk´azali jsme, zˇ e kaˇzd´a svazovˇe uspoˇra´ dan´a mnoˇzina je svaz. Plat´ı vˇsak i obr´acenˇe, zˇ e kaˇzd´y svaz je svazovˇe uspoˇra´ dan´a mnoˇzina. 4
8. Uspoˇra´ d´an´ı a svazy
Cviˇcen´ı. A) Bud’ (M, ∧, ∨) svaz. Pak plat´ı: (1) Poloˇzme x ≤∧ y pr´avˇe kdyˇz x ∧ y = x. Pak je ≤∧ uspoˇra´ d´an´ı na mnoˇzinˇe M. (2) Poloˇzme x ≤∨ y pr´avˇe kdyˇz x ∨ y = y. Pak je ≤∨ uspoˇra´ d´an´ı na mnoˇzinˇe M. (3) Uspoˇra´ d´an´ı ≤∧ je shodn´e s uspoˇra´ d´an´ım ≤∨ a je svazov´e, pˇriˇcemˇz sup{x, y} = x ∨ y,
inf{x, y} = x ∧ y.
B) Bud’ (M, ∧, ∨) svaz. Ukaˇzte, zˇ e (M, ∨, ∧) je tak´e svaz; naz´yv´a se du´aln´ı svaz. Ovˇeˇrte, zˇ e du´aln´ı svaz m´a du´aln´ı uspoˇra´ d´an´ı.
Nad´ale budeme pouˇz´ıvat term´ın svaz i pro svazovˇe uspoˇra´ dan´e mnoˇziny. Svazy budeme ch´apat i jako algebraick´e struktury i jako uspoˇra´ dan´e mnoˇziny souˇcasnˇe. V´ıme totiˇz, zˇ e uspoˇra´ d´an´ı jednoznaˇcnˇe urˇcuje algebraickou strukturu a algebraick´a struktura zase jednoznaˇcnˇe urˇcuje uspoˇra´ d´an´ı. Cviˇcen´ı. S kaˇzd´ym svazem jsou spojeny dvˇe pologrupy (M, ∧) a (M, ∨). A) Dokaˇzte, zˇ e n´asleduj´ıc´ı v´yroky o svazu (M, ∧, ∨) jsou ekvivalentn´ı: (1) M m´a nejvˇetˇs´ı prvek e; (2) (M, ∧, e) je monoid. B) Zformulujte a dokaˇzte ,,du´aln´ı“ v´ysledek o monoidu (M, ∨, e). Cviˇcen´ı. Ukaˇzte, zˇ e pologrupa A = { ♥, ♠, ♦, ♣ } s operac´ı ,, “ zadanou tabulkou ♥ ♠ ♦ ♣
♥ ♥ ♥ ♥ ♥
♠ ♥ ♠ ♥ ♠
♦ ♥ ♥ ♦ ♦
♣ ♥ ♠ ♦ ♣
je pologrupou (A, ) nˇekter´eho svazu (A, , ). Nakreslete diagram tohoto svazu a vysvˇetlete, jak jej lze pouˇz´ıt k d˚ukazu asociativity operace ,, “.
Pˇri poˇc´ıt´an´ı ve svazech m˚uzˇ eme pouˇz´ıt n´asleduj´ıc´ı uˇziteˇcn´e implikace: Tvrzen´ı. Pro kaˇzd´e tˇri prvky x, a, b svazu L plat´ı (i) jestliˇze a ≤ b, pak a ∧ x ≤ b ∧ x ; (ii) jestliˇze a ≤ b, pak a ∨ x ≤ b ∨ x ; (iii) jestliˇze x ≤ a , x ≤ b, pak x ≤ a ∧ b; (iv) jestliˇze x ≥ a , x ≥ b, pak x ≥ a ∨ b. Dukaz. ˚ (i) Necht’ a ≤ b, pak a ∧ b = a , naˇceˇz (a ∧ x) ∧ (b ∧ x) = a ∧ b ∧ x = a ∧ x ; odtud tvrzen´ı. (ii) cviˇcen´ı; (iii) a (iv) plynou ihned z definice infima a suprema (cviˇcen´ı). Je-li (L , ∧, ∨) svaz, pak je (L , ∨, ∧) tak´e svaz. Identity (∗) definuj´ıc´ı svaz jsou totiˇz symetrick´e vzhledem k vz´ajemn´e z´amˇenˇe ∧ a ∨. Naz´yv´a se du´aln´ı svaz ke svazu L a budeme jej znaˇcit L ∗ . St´av´a se, zˇ e podmnoˇzina A svazu M obsahuje i vˇsechna suprema a infima vˇsech dvojic sv´ych prvk˚u, a je potom sama svaz. Definice. Podsvaz svazu (M, ∧, ∨) je podmnoˇzina A ⊂ M takov´a, zˇ e pro kaˇzd´e x, y ∈ A plat´ı x ∧ y ∈ A a x ∨ y ∈ A. 5
8. Uspoˇra´ d´an´ı a svazy
Pˇr´ıklad. Svaz M a dva jeho podsvazy A a B:
M ⊇
A=
B=
a
Cviˇcen´ı. (1) Kaˇzd´a podmnoˇzina ˇretˇezce je podsvaz. (2) Kaˇzd´a podmnoˇzina svazu, kter´a je ˇretˇezcem, je podsvaz.
Nicm´enˇe, podmnoˇzina A m˚uzˇ e b´yt svazem vzhledem k indukovan´emu uspoˇra´ d´an´ı, aniˇz by byla podsvazem: Pˇr´ıklad. Svaz M a jeho podmnoˇzina A, kter´a je svazem, ale nen´ı podsvazem. x ∨A y M x
x ∨M y y
A ⊇
y
x
Supremum x ∨ A y v A je r˚uzn´e od suprema x ∨ M y v M!
Definice. Bud’te (X, ∧, ∨), (Y, ∧, ∨) svazy. Zobrazen´ı f : L → R se naz´yv´a homomorfismus svaz˚u, jestliˇze f (a ∧ b) = f (a) ∧ f (b) a f (a ∨ b) = f (a) ∨ f (b) pro kaˇzd´e a, b ∈ X . Tvrzen´ı. Kaˇzd´y homomorfismus svaz˚u je izotonn´ı zobrazen´ı. Dukaz. ˚ Bud’te (X, ∧, ∨), (Y, ∧, ∨) svazy, bud’ f : X → Y homomorfismus. Necht’ a, b ∈ X a necht’ a ≤ b, takˇze a ∧ b = a , naˇceˇz f (a) ∧ f (b) = f (a ∧ b) = f (a), a proto f (a) ≤ f (b), coˇz se mˇelo dok´azat. Izotonn´ı zobrazen´ı svaz˚u vˇsak nemus´ı b´yt homomorfismus: Pˇr´ıklad. Zobrazen´ı f je izotonn´ı zobrazen´ı svaz˚u, je-li A x
x∨y B
y x∧y
Toto zobrazen´ı nen´ı homomorfismus svaz˚u, protoˇze f (x) ∨ f (y) = f (y) = f (x ∨ y)
6
8. Uspoˇra´ d´an´ı a svazy
Cviˇcen´ı. Bud’ f : A → B zobrazen´ı svazu (A, ∧, ∨) do svazu (B, ∧, ∨). Dokaˇzte, zˇ e n´asleduj´ıc´ı v´yroky jsou ekvivalentn´ı: 1◦ f je izomorfismus uspoˇra´ dan´ych mnoˇzin; 2◦ f je izomorfismus svaz˚u.
´ Upln´ e svazy Definice. Bud’ L svaz, ˇrekneme, zˇ e L je u´ pln´y, m´a-li kaˇzd´a podmnoˇzina v L supremum i infimum. Pˇr´ıklad. (1) Kaˇzd´y koneˇcn´y svaz je u´ pln´y a plat´ı sup{ x1 , . . . , xn } = x1 ∨ . . . ∨ xn , inf{ x1 , . . . , xn } = x1 ∧ . . . ∧ xn . (2) Svaz (P(M), ⊆) je u´ pln´y. Infima jsou pr˚uniky, suprema jsou sjednocen´ı. (3) Svaz (N, ≤) nen´ı u´ pln´y. Sch´az´ı napˇr´ıklad supremum cel´e mnoˇziny N.
Kaˇzd´y u´ pln´y svaz L m´a nejvˇetˇs´ı prvek sup L i nejmenˇs´ı prvek inf L . Vˇeta. Bud’ L uspoˇra´ dan´a mnoˇzina, jej´ızˇ kaˇzd´a podmnoˇzina m´a infimum. Pak L je u´ pln´y svaz. Dukaz. ˚ Bud’ X ⊆ L . Oznaˇcme Y mnoˇzinu vˇsech horn´ıch z´avor mnoˇziny X . Poloˇzme s = inf Y a dokaˇzme, zˇ e s = sup X . Nejprve dokaˇzme, zˇ e s je horn´ı z´avora mnoˇziny X . Bud’ tedy x ∈ X libovoln´e. Pro kaˇzd´y prvek y ∈ Y pak m´ame y ≥ x , protoˇze y je horn´ı z´avora mnoˇziny X . To ale znamen´a, zˇ e x je doln´ı z´avora mnoˇziny Y . Odtud x ≤ s , protoˇze s je nejvˇetˇs´ı doln´ı z´avora mnoˇziny Y . Pˇredchoz´ı v´ysledek znamen´a, zˇ e s ∈ Y . Protoˇze nav´ıc s = inf Y , je s nejmenˇs´ı prvek mnoˇziny Y , a tedy nejmenˇs´ı horn´ı z´avora mnoˇziny X , coˇz se mˇelo dok´azat. Cviˇcen´ı. Dokaˇzte, zˇ e inf ∅ je nejvˇetˇs´ı prvek v X . Mezi pˇredpoklady vˇety proto je i pˇredpoklad, zˇ e X m´a nejvˇetˇs´ı prvek. Napˇr´ıklad (N, ≤) nen´ı u´ pln´y svaz, pˇrestoˇze kaˇzd´a nepr´azdn´a podmnoˇzina m´a infimum.
Poslednˇe uveden´a vˇeta poskytuje cenn´y zp˚usob d˚ukazu, zˇ e nˇekter´a uspoˇra´ dan´a mnoˇzina je svaz. Pˇr´ıklad. Bud’ A grupa, oznaˇcme P(A) mnoˇzinu vˇsech podgrup grupy A. Pak je (P(A), ⊆) u´ pln´y svaz. Snadno se totiˇz uk´azˇ e, zˇ e pro libovoln´e podgrupy Ai , i ∈ I , je i∈I Ai zase podgrupa (cviˇcen´ı), kter´a je souˇcasnˇe infimem inf{ Ai }i∈I (cviˇcen´ı). Podle pˇredchoz´ı vˇety je potom (P(A), ⊆) u´ pln´y svaz. Proto existuje i supremum sup{ Ai }i∈I a je pr˚unikem vˇsech podgrup, kter´e obsahuj´ı vˇsechny podgrupy Ai . Pˇr´ıklad je zformulov´an pro grupy, ale jeho analogie plat´ı i pro pologrupy, monoidy a v podstatˇe jak´ekoliv algebraick´e struktury. Probl´em k rˇ eˇsen´ı. Oznaˇcme E(A) mnoˇzinu vˇsech relac´ı ekvivalence na A. Protoˇze E(A) ⊆ P(A2 ), vznik´a na E(A) indukovan´e uspoˇra´ d´an´ı. Dokaˇzte, zˇ e E(A) je u´ pln´y svaz.
3. Distributivn´ı svazy ˇ Definice. Rekneme, zˇ e svaz (M, ∧, ∨) je distributivn´ı, plat´ı-li pro kaˇzd´e tˇri prvky x, y, z ∈ M distributivn´ı z´akony (i) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z); (ii) x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). 7
