1. Množiny Pojem množiny je základním pojmem matematiky. Množina je určena svými prvky, t.j., množinou rozumíme souhrn prvků. Teorii množin vybudoval německý matematik G.Cantor v roce 1872. Výše uvedené vymezení pojmu množiny není přesnou definicí. Vede také k rozporům neboť jsou "souhrny", které za množiny považovat nemůžeme. Později uvidíme, že nemůžeme vytvořit "množinu" všech množin. Nejjednodušší příklad takové zakázané "množiny" nalezl B.Rüssel v roce 1900. Je to souhrn M = {x\x (£ x} všech množin x, které neobsahují sebe jako prvek. Totiž, pokud by M byla množina, můžeme si položit otázku, zda M G M. Pokud ano, pak, podle definice M platí M (j M. Pokud ne, pak, opět podle definice M, platí M G M. V obou případech dostáváme spor. Řešení problému definice pojmu množiny podává axiomatická teorie množin. My budeme pracovat v tzv. naivní teorii množin, t.j., na základě výše uvedené nepřesné "definice". Budeme však opatrní v jejím používání: ne všechny souhrny budeme považovat za množiny. Zároveň si naznačíme, jak vypadá axiomatická teorie množin. Základní (a vlastně jedinou) vlastností množin je, že mají prvky. Píšeme a G A, což znamená, že a je prvkem množiny A. Malá a velká písmena používáme pro názornost; ve skutečnosti v teorii množin není nic jiného než množiny, t.j., i a je množina. Fakt, že množina je určena svými prvky je vyjádřen následujícím axiomem (který je prvním axiomem axiomatické teorie množin): Axiom extensionality: Dvě množiny jsou stejné, právě když mají stejné prvky. Pomocí predikátové logiky (v jazyce s jediným binárním relačním symbolem G, což je jazyk axiomatické teorie množin) se tento axiom zapíše následovně: (Wx,y)(x =i/0 (Vz)(z ĚiflzĚ y)) Pro množiny A} B píšeme A C B & říkáme, že množina A je podmnožina množiny B} jestliže libovolný prvek množiny A je prvkem množiny B. Zřejmě platí AC A ACB&BCC^ACC A=B^ACBaBCA Jsou-li A} B množiny, můžeme z nich utvořit nové množiny A U B = {x\x G A nebo x G B} A n B = {x\x e A a x e B} A- B = {x\x G A a x £ B} které postupně nazýváme sjednocení, průnik a rozdíl množin A a B. Existuje množina, která se vyznačuje tím, že nemá žádné prvky. Nazývá se prázdná a označuje se 0. Pro libovolnou množinu A platí 0C A. Typeset by Aj\y[S-T]^K. 1 2 Množiny A} B se nazývají disjunktní, jestliže A D B = 0. Platí následující pravidla, která se postupně nazývají komutativní, asociativní, idempotentní a distributivní zákony: AUB = BUA AHB = BC\A AU(BUC) = (AUB)UC Ar\(Br\C) = (Ar\B)nC AUA = A AC\A = A AU(Br\C) = (AUB)r\(AuC) Ar\(BuC) = (Ar\B)u(Ar\ C). Je-li A podmnožinou množiny M, pak rozdíl M — A se nazývá doplněk (nebo také komplement podmnožiny A. Značíme jej A'. Platí následující pravidla, která se postupně nazývají zákony jednotky, negace a de Morgana: AUM = M ADM = A AU0 = A An0 = 0 AUÄ = M A n A' = 0 M' = 0 0' = M A" = A (A n B)' = ÄUB' (AUB)' = Ä HB'. Obecněji, platí A - (B U C) = [A - B) n [A - C) 3 A - (B n C) = (A - B) U (A - C). Máme-li množiny A}B} můžeme utvořit novou množinu {A}B}} která má za prvky právě A a B. Tento způsob tvorby množin se nazývá axiom dvojice. Jeho pomocí můžeme z prázdné množiny 0 vytvořit nové množiny, např. {0}, {{0}}, {0,{0}}, atd. Tímto způsobem můžeme definovat přirozená čísla: 0 = 0, 1 = {0}, 2 = {0,{0}},3 = {0,{0},{0,{0}}},atd. Vždy n = {0,1, • • • ,n-l}. Tedy přirozená čísla jsou množiny. Rovněž můžeme utvořit množinu všech nezáporných celých čísel cu = {0,l,2,--- ,n,---}. Nazýváme to axiom nekonečna. Pro libovolnou množinu A a libovolnou "množinovou vlastnost" •■)' = U 4 Uspořádaná dvojice (a, 6) se definuje jako množina (a, b) = {{a},{a,6}}. Tato definice je v duchu teorie množin: vše je množina, tedy i uspořádaná dvojice. Snadno se ověří, že platí (a, b) = (c, d) a = c a b = d. Kartézský součin množin A} B nyní definujeme jako A x B = {(a,b)\a G A,b G B}. Platí (AU B) x C = (A x C) U (B x C) C x (A U B) = (C x A) U (C x B) (AHB) x C = (A x C) n (B x C) C x (AHB) = (C x A) n (C x B). Tato pravidla lze rozšířit i na nekonečná sjednocení a průniky: (\jAi)xC=\J(AixC) i£l i£l (f]Ai)xC=f](AixC) i£l i£l (a podobně z druhé strany). Všimněme si, že pro A ^ B platí A x B ŕ B x A Podobně (AxB)xC ^Ax(B xC). Je-li A množina, můžeme utvořit množinu V (A) = {X\X C A} všech podmnožin množiny A. Nazýváme to axiom množiny podmnožin. 5 Dosud jsme se seznámili s následujícími axiomy teorie množin: axiom exten-sionality, axiom prázdné množiny, axiom vyčlenění, axiom dvojice, axiom sjednocení, axiom množiny podmnožin a axiom nekonečna. První udává, kdy jsou dvě množiny stejné, další popisují "povolené" způsoby tvorby množin. K úplné Zermelo-Fraenkelově teorii množin (což je štandartní axiomatika teorie množin, označuje se ZF) nám chybí již jen dva dosti technické axiomy: axiom regularity a axiom nahrazení. (První z nich říká, že všechny množiny "vzniknou" z prázdné množiny.) Např. kartézský součin A x B vznikne vyčleněním z množiny V (V (A U B)); totiž uspořádané dvojice (a, b) jsou prvky této množiny. Ideální teorie množin by kromě axiomu extensionality obsahovala pouze axiom říkající, že pro libovolnou množinovou vlastnost B množiny A do množiny B je předpis přiřazující každému prvku množiny A prvek množiny B. Tato definice není, z hlediska teorie množin, přesná neboť obsahuje nedefinovaný pojem "předpis". Přesnou definici si uvedeme v příští kapitole. Zobrazení / : A —y B se nazývá prosté (nebo také injektivní), jestliže platí f(ai) = f(a2) => a1 = a2. Nazývá se zobrazení množiny A na množinu B (nebo také surjektivní), jestliže pro libovolné b £ B existuje a £ A tak, že f (a) = b. Zobrazení, které je současně prosté i na se nazývá bijektivní (nebo také bijekce). Množiny A} B se nazývají isomorfní, jestliže existuje bijekce A —> B. Značíme A = B. Buď / : A —> B bijektivní zobrazení. Položme /_ (b) = a právě když f (a) = b. Pak /_1 : B —y A je zobrazení, které nazýváme inverzní k /. Zřejmě to je rovněž bijektivní zobrazení a platí Předpis idA(a) = a definuje zobrazení id a '■ A —> A} které se nazývá identické (nebo rovněž identita) na A. Je to zřejmě bijekce a platí (id a) 1 = id a- 6 Obecněji, je-li A C _£?, pak zobrazení inkluze i : A —> B je definováno předpisem z(a) = a pro a £ A Buďte fiA—t-B&giB—t-C zobrazení. Pak předpis (g o f)(a) = g(f(a)) definuje zobrazení g o f : A —> C. Tento postup se nazývá skládání zobrazení a g o f se nazývá složené zobrazení. Platí následující pravidla (h : C —y D je další zobrazení): ho (go f) = (hog) of f o id a = f idBo f = f f o f'1 = idB f'1 o f = id a- Jedná se o asociativní zákon, vlastnost jednotky a vlastnost inverzního zobrazení. V posledním pravidle je samozřejmě / bijekce. Navíc, inverzní zobrazení je touto vlastností určeno jednoznačně. To znamená, že / o g = idB a go f = idA ^ g = /_1 • Symbolem B označíme množinu všech zobrazení A —> B. Pro libovolnou množinu A existuje právě jedno zobrazení 0 —y A. Nazývá se prázdne zobrazení a označuje se o a- Tedy A = {o a} je jednoprvková množina. Zřejmě (A , o) je monoid. Tento monoid není obecně komutativní. Například, označíme-li symbolem ka : A —> A konstantní zobrazení s hodnotou a, t.j. ka(x) = a pro všechna x G A, pak platí ka o k\) = ka a k}) o ka = kj,. Bijektivní zobrazení množiny A —y A se nazývá permutace množiny A. Symbolem S (A) označíme množinu všech permutací množiny A. Pak (S(A)} o) je grupa. Tato grupa opět není obecně komutativní. Nazývá se symetrická grupa. Zobrazení pí : i x 5 -> A p2 : Ax B ^ B daná předpisem pi(a}b) = a p2(a}b) = b se nazývají projekce. Věta 2.1. Pro libovolné množiny A} B} C platí následující pravidla: (1) (A x Bf 9ěAcxBc (2) (ABf ^ABxC (3) ABUC = ABxAc. V (3) musí množiny B} C být disjunktní. Důkaz. (1) Bijekce F : (A x B) —y A x B je dána předpisem F(f) = (piof,p2of), 7 kde pi : A x B ^ A a p2 : A x B ^ B jsou projekce. (2) Bijekce F : (AB)C -> ABxC je dána předpisem F(f)(b,c)=f(c)(b) kde / : C -► A5. (3) Jsou-li i?, C disjunktní, pak bijekce i71 : A —> A X A je dána předpisem F(f) = (fi,f2) kde /i je zúžení / : ß U C na 5 (t.j-, /i(&) = /(&)) a /2 je zúžení / na C. D Kartézský součin můžeme pomocí pojmu zobrazení popsat následovně: Ax5-{/:{l,2}^iU B\f(l) G A, /(2) G 5}. To nás vede k následující definici kartézského součinu libovolného (i nekonečného) systému množin Ai, i G 7, kde 7 je množina: JJ Ai = {/ : 7 -» (J Ai\f(i) G Ai pro libovolné z G 7}. i£l i£l Projekce Pi : JI Ai -^ A' jsou definovány předpisem Pi(f) = f (i)- Pro libovolnou podmnožinu 7? množiny A definujeme charakteristickou funkci Xb '■ A —y 2 této podmnožiny předpisem (zde 2 = {0, 1}) Xß(ö) = löa£ß. Zobrazení 7*1 : "P(A) —> 2 , F(B) = \B je zřejmě bijekce. Tedy V(A) ^ 2A. Je-li / : A —> 7? zobrazení, pak množina /(A) = {/(a)\a G A} se nazývá obraz množiny A v zobrazení /. Libovolné zobrazení / : A —> B lze zapsat jako složení zobrazení na a prostého zobrazení f:A^ f (A) -+ B. Definice. Řekneme, že množiny A, B mají stejnou mohutnost, jestliže A = B. Jedná se pouze o jiný název pro skutečnost, že množiny A, B jsou isomorfní. Množina A se nazývá konečná, pokud má stejnou mohutnost jako některá z množin n = {0, 1,. . . , n — 1}, kde nGw. 8 Příklady 2.2. (1) Dvě konečné množiny mají stejnou mohutnost, právě když mají stejný počet prvků. (2) Množiny Z a 2Z mají stejnou mohutnost neboť zobrazení / : Z —y 2Z, f(x) = 2x je bijekce. Tedy vlastní podmnožina nekonečné množiny může mít stejný počet prvků jako celá množina. (3) Množiny w, NaZ mají stejnou mohutnost. Stačí uvažovat bijekce / : u —>■ N a g : u —>■ Z dané předpisy f (x) = x + 1 g(2n) = n g(2n + 1) = -(n + 1). (4) Ukážeme, že množina Q racionálních čísel má stejnou mohutnost jako u. Podobně jak pro Z stačí ukázat, že množina Q"1" kladných racionálních čísel má stejnou mohutnost jako u. Napíšeme tato čísla jako vykráčené zlomky do řádků. Do prvního řádku dáme všechny vykráčené zlomky s čitatelem 1, do druhého řádku všechny vykráčené zlomky s čitatelem 2, atd. Vznikne čtvercová tabulka, která má spočetně mnoho řádků a spočetně mnoho sloupců. Vypíšeme-li její prvky po diagonálách (t.j., 1, ^ , 2, 3 ,. . .), seřadíme kladná racionální čísla do posloupnosti. Tedy Q+ má stejnou mohutnost jako u. 2.3 Cantorova věta. Množiny X aV(X) nikdy nemají stejnou mohutnost. Důkaz. Buď / : X —y V(X) zobrazení. Položme Y = {x £ X\x (£ f(x)}. Předpokládejme, že existuje z £ X tak, že f (z) = Y. Pak platí což je spor. D Množina, která má stejnou mohutnost jako u se nazývá spočetná. Nekonečná množina, která není spočetná se nazývá nespočetná. V předchozím příkladu jsme viděli, že N, Z a Q jsou spočetné množiny. Věta 2.4. Podmnožina spočetné množiny je buď konečná neho spočetná. Důkaz. Buď X nekonečná podmnožina u. Uvažme zobrazení / : u —>■ X takové, že f(n) je nejmenší prvek v X — {/(O),. . . , f(n — 1)}. Poněvadž / je zřejmě bijektivní zobrazení, množina X je spočetná. D Věta 2.5. Buď f : u —>■ X zobrazení. Pak f (co) je konečná neho spočetná množina. Důkaz. Definujme zobrazení g : f (to) —y u tak, že g (x) je nejmenší prvek v f~1(x). Pak g je prosté, takže tvrzení plyne z 2.4. D Věta 2.6. Množina IR je nespočetná. Důkaz. Definujme zobrazení / : 2W —y IR desetinným rozvojem f(h) = 0}h(0)h(l)h(2)... kde h : u —>■ 2. Poněvadž / je prosté zobrazení, z 2.3. a 2.4. plyne, že množina IR není spočetná. D Otázka, zda libovolná nekonečná podmnožina v IR je buď spočetná nebo mohutnosti stejné jako IR, je nerozhodnutelná. 9 3. Relace Definice. (Binární) relaci R (mezi množinami A, B) definujeme jako podmnožinu RC Ax B. Obecně, můžeme definovat n-ární relaci jako podmnožinu R C A\ X ■ ■ ■ X An pro n = 1, 2, • • • . Například unární relace je podmnožina R C. A. Zobrazení / : A —y B je odpovídá jako relaci Rf C A x B s vlastností, že pro libovolné a G A existuje právě jedno b G B tak, že (a, b) G Rf. Tím je podána slibovaná "množinová" definice pojmu zobrazení. Příslušná relace R f je vlastně graf zobrazení /. Radu pojmů o zobrazeních, můžeme zobecnit na relace (relace je vlastně částečné, vícehodnotové zobrazení). Např. definiční obor relace R C A x B je {a G A\ existuje b G B tak, že (a, b) G R} a obor hodnot je {b G B\ existuje a G A tak,že (a, b) G R}. Skládání relací RCAxB&SCBxCse definuje předpisem S o R = {(a, c)\ existuje b G B tak, že (a, b) G -R, (6, c) G S"} Platí 5oJ?axC. Dále (pro T C C x D) T o (S o R) = (T o S) o R idß o R = R = R o id a- Inverzní relace i?-1 k relaci R G A x B se definuje jako R-1 ={(b,a)\(a,b) e R}. Platí R'1 C B x A. Zřejmě Rf-i = R]1. Definice. Pokud i? C A x A, pak říkáme, že R je relace na množině A. Relace R na množině A se nazývá: (1) reflexivní, pokud id a C R (t.j., pokud pro libovolné a G A platí (a,a) G R) (2) symetrická, pokud i?-1 = i? (t.j., pokud (a, 6) G i? implikuje (6, a) G i?) (3) tranzitivní, pokud R o R C R (t.j., pokud (a, 6) G i? a (6, c) G -R, pak (a,c) G -R. Relace R na množině A se nazývá relace ekvivalence, pokud je současně reflexivní, symetrická i tranzitivní. Buď / : A —> B zobrazení. Pak relace Jf = {(ai,a2)\/(ai) = f(a2)} je relace ekvivalence na množině A. Nazývá se jádro zobrazení /. Ukážeme, že libovolná relace ekvivalence je jádrem nějakého zobrazení. Buď R relace ekvivalence na množině A. Pro a G A položíme Ra = {beA\(a,b) G i?}. Ra se nazývá třída relace ekvivalence R určená prvkem a. 10 Lemma 3.1. Buď R relace ekvivalence na množině A a a}b G A. Pak platí (1) a G Ra (2) Ra=Rb^ (a, b)čR (3) Ra n Rb jí B zobrazení. Pak A\Jf - f (A). Důkaz. Definujme zobrazení g : A\Jj —y f (A) vztahem (1) g((Jf)a) = f(a). Poněvadž (Jf)a! = (Jf)a2 <$ (01,02) £ Jf <$ f(0.1) = f(a2) g je bijekce. D Poznámka 3.4. Předpis (1) z předchozího důkazu definuje prosté zobrazení g : A\Jf —y B. Platí / = pjf o (/, takže libovolné zobrazení / lze rozložit na složení zobrazení na pjf následovaného prostým zobrazením g . Různá zobrazení mohou mít stejné jádro. Např., zobrazení / je prosté, právě když J f = id a- 11 Definice. Rozklad TZ množiny A je množina TZ C V (A) neprázdných podmnožin množiny A splňující (1){JTZ = A (2) Xi n X2 = 0 pro libovolná XUX2 G ft,Xi ^ X2. Pro libovolnou relaci ekvivalence i? na množině A je A\i? rozklad množiny A. Ukážeme, že rozklady přesně odpovídají relacím ekvivalence. Věta 3.4. Bud TZ rozklad množiny A. Položme R-ji = {(a, 6)\ existuje X G TZ tak, že a, b G X}. Pak R-ji je relace ekvivalence na A a platí TZ = A\Rn Důkaz. Uvažujme zobrazení r : A —y TZ takové, že a G r(a). Zřejmě R-ji = Jr, takže R-ji je relace ekvivalence. Vztah TZ = A\R-ji je zřejmý. D Právě popsaná korespondence mezi rozklady a relacemi ekvivalence na množině A je vzájemně jednoznačná: TZ = A\Riz a R = R(a\r)- Viděli jsme, že nezáporná celá čísla lze sestrojit pomocí množin, včetně (Peanovy) aritmetiky. Ukážeme, že totéž platí i pro celá a racionální čísla (v příští kapitole to provedeme i pro reálná čísla). Konstrukce celých čísel: Definujme na množině u x u relaci ~ vztahem (a, b) ~ (c, d) <^ a + d = c + b. Jedná se o relaci ekvivalence; reflexivita a symetrie jsou zřejmé, tranzitivita se ověří následovně: z (a, b) ~ (c, d) ~ (e, /) plyne a-\- d = c-\-b,c-\- f = e-\-d, t.j., postupně a + ■ (a + c, & + ad = cb. Podobně, jak výše se ověří, že se jedná o relaci ekvivalence. Položíme Q = (Z x Z*)\ ~ . Třídu ekvivalence prvku (a, b) opět značíme symbolem (a, b) (tato třída nyní hraje roli zlomku j). Položíme (a, b) + (c, d) = (ad + 6c, 6 a = 6. Definice. Relace i? na množině A, která je reflexivní, antisymetricka a tranzitivní se nazývá uspořádání. Řekneme, že (A, <) je uspořádaná množina, jestliže < je relace uspořádání na A. Uspořádaná množina (A, <) se nazývá lineárně uspořádaná (nebo také řetězec), jestliže pro libovolná a, 6 G A platí buď a < b nebo b < a. V uspořádané množině (A, <) symbolem a < b rozumíme a < 6, a ^ 6. 13 Příklady. (1) N, Z, Q, IR jsou lineárně uspořádané množiny (vzhledem k uspořádání podle velikosti). (2) Pro libovolnou množinu A je = uspořádání na A. Vzniklá uspořádaná množina se nazývá protiřetězec (samozřejmě se nejedná o lineární uspořádání, má-li A aspoň dva prvky). (3) Často můžeme uspořádanou množinu (A, <) znázornit graficky. Prvky množiny A nakreslíme jako body a úsečkou spojíme sousední prvky. Tím rozumíme prvky a, & G A takové, že a < 6, přičemž neexistuje c G A takové, že a < c < b. Píšeme a -< b. Body a, & G A takové, že a -< b přitom kreslíme tak, že a je níže než b. Tyto obrázky se nazývají Hasseovy diagramy. (4) Pro libovolnou množinu X je ("P(X),C) uspořádaná množina, která není lineárně uspořádaná (pokud A má aspoň dva prvky). V dalším budeme uspořádanou množinu většinou stručně označovat pouze symbolem A. Prvky a, & G A se nazývají nesrovnatelné', pokud neplatí ani a < b ani b < a. Značíme je a || b. Nejmenší prvek uspořádané množiny A je prvek a takový, že pro libovolné x G A platí a < x. Minimální prvek a je definován tím, že neexistuje prvek x G A tak, že x < a. Nejmenší prvek je, pokud existuje, jediný a je zároveň minimální. Minimálních prvků může být víc a nemusí být nejmenší (např. v protiřetězci). Analogicky definujeme největší prvek a maximální prvek. Je-li (A, <) uspořádaná množina, pak (A, >) je rovněž uspořádaná množina; nazývá se duálně uspořádaná. Označujeme-ji Aop. Největší (maximální) prvek uspořádané množiny A je vlastně nejmenší (minimální) prvek duálně uspořádané množiny Aop. Takové pojmy nazýváme duální. Podobně k libovolnému tvrzení o uspořádaných množinách existuje duální tvrzení (a platí-li výchozí tvrzení pro libovolnou uspořádanou množinu, pak duální tvrzení platí rovněž pro libovolnou uspořádanou množinu). Např., uspořádaná množina obsahuje nejvýše jeden největší prvek. Relace, která je reflexivní a tranzitivní se nazývá přeuspořádání. Předuspořádaná množina je dvojice (A, C), kde C je předuspořádání na množině A. Příklady předuspořádaných množin, které nejsou uspořádané, jsou (1) (Z, |), kde | je relace dělitelnosti. (2)(Formp} C), kde Formp označuje množinu všech formulí výrokové logiky jazyka P a A\ZB <& \=A^B. Věta 4.1. Buď (A} C) předuspořádaná množina. Pro a}b G A klademe a~6<^aC&a zároveň b C a. Pak ~ je relace ekvivalence na A. Položíme-li pro a, & G A\ ~ a < b <^ a C 6, pak (A\ ~, <) je uspořádaná množina. Důkaz. Snadno se ověří, že ~ je relace ekvivalence na A. Definice relace < na faktorové množině je korektní (t.j., nezávisí na volbě reprezentantů) neboť Ol ~ «2 , b\ ~ &2 , «1 E b\ <^ Ü2 C &2 • 14 Reflexivita a tranzitivita relace < okamžitě plyne z reflexivity a tranzitivity výchozí relace C. Zbývá ověřit, že < je antisymetrická. Avšak D Aplikujeme-li Větu 4.1. na předuspořádanou množinu (Z, |), platí a ~ & <^ a = b nebo a = —b. Tedy indukovaná uspořádaná množina je vlastně totéž jako (Z+, |). V případě předuspořádané množiny (Formp} C) platí Definice. Buďte A} B uspořádané množiny a / : A —y B zobrazení. Řekneme, že / je isotonní, pokud platí oi < a2 => f(ai) < f(a2). Jsou-li A} B uspořádané množiny a / : A —y B bijektivní zobrazení takové, že / i /_1 jsou isotonní, pak říkáme, že f je isomorfismus. Uspořádané množiny A, B se v tom případě nazývají isomorfní a značíme A = B. Definice. Buď A uspořádaná množina a X C A. Řekneme, že prvek a G A je horní závora podmnožiny X, jestliže platí x < a pro libovolné x G X. Řekneme, že a je supremum podmnožiny X, jestliže je horní závorou X a pro libovolnou horní závoru b množiny X platí a < b. Tedy supremum X je nejmenší horní závora X. Označujeme ho supX. Duálně se definuje dolní závora podmnožiny X a infimum podmnožiny X (t.j., největší dolní závora X). Značíme jej infX. Uvědomme si, že sup0 je nejmenší prvek uspořádané množiny A (pokud existuje) a inf0 je největší prvek A. V uspořádané množině (V(A), C) platí supAf = \JX infVť = f)X. Věta 4.2. Buď A uspořádaná množina, v níž libovolná podmnožina má supremum. Pak libovolná podmnožina v A má infímum. Důkaz. Nechť X C A. Buď X~ množina dolních závor X v A. Ukážeme, že platí infX = supX-. Zřejmě platí, že infX, jestliže existuje, je supX-. Je třeba ukázat, že supX- je infX. K tomu stačí ukázat, že supX- G X~. Avšak pro libovolná iflai/Ěl" platí y < x} takže supAT- < x. Tedy supAT- G X~. D 15 Definice. Uspořádaná množina, jejíž libovolná podmnožina má supremum i infimum se nazývá úplný svaz. Duální věta k Větě 2. říká, že pokud libovolná podmnožina uspořádané množiny A má infimum, pak A je úplný svaz. Doplňme, že uspořádaná množina A se nazývá svaz, pokud libovolná její neprázdná konečná podmnožina má supremum i infimum (což je totéž jako požadavek, že libovolná dvouprvková podmnožina má supremum a infimum). Věta 4.3. (Tarski) Buď A úplný svaz a f : A —y A isotonní zobrazení. Pak f má pevný bod, t.j., existuje a G A s vlastností f (a) = a. Důkaz. Položme M = {x\x < f(x)}. Pro libovolný prvek x G M platí f (x) G M. Skutečně, z x G M plyne x < f (x), tedy f (x) < f (f (x)) a proto i f (x) G M. Položme a = supM. Tedy pro libovolné x G M platí x < f (x), tedy f (x) < f (a), takže x < f (x) < f (a). Tedy f (a) je horní závora podmnožiny M. Poněvadž a je supremum M, máme a < f (a). Tedy a G M a již jsme ověřili, že to znamená f (a) G M. Tedy f (a) < a, jelikož a je supremum M. Dokázali jsme, že platí f (a) = a. Tedy a je hledaný pevný bod. D Pevný bod sestrojený v předešlém důkazu je zřejmě největším pevným bodem zobrazení /. Duálně, mf{x\f(x) < x} je nejmenším pevným bodem /. Ukážeme, že za zesílených předpokladů lze pevný bod získat "konstruktivně". Řekneme, že zobrazení / : A —> B úplných svazů zachovává suprema, jestliže pro libovolnou podmnožinu X £ A platí f(supX) = supf(X). Takové zobrazení je vždy isotonní: a < b => b = sup{a,&} => f (b) = sup{/(a),/(6)} => f (a) < f (b). Poznamenejme, že pro libovolné izotonní zobrazení / : A —> B platí sup/(X) < /(supX). Věta 4.4. Buď A úplný svaz a f : A —y A zobrazení, které zachovává suprema. Pak f má pevný bod. Důkaz. Buď a® nejmenší prvek v A, jenž existuje neboť A je úplný svaz. Pro libovolné n = 0, 1, 2,. . . položíme an_|_i = f(an). Pak pro a = sup{an\n = 1,2,...} platí f(a) = f(sup{an\n G u;}) = sup{/(an)\n G co} = sup{an_|_i\n G co} = a. Tedy a je pevný bod /. D 16 Poznámka 4.5. Právě sestrojený pevný bod je zřejmě nejmenším pevným bodem /. Ve Větě 4.4. by stačilo předpokládat, že / zachovává suprema řetězců. Význam tohoto obecnějšího tvrzení je vidět z následujícího příkladu. Příklad 4.6. Buď X množina a V(X x X) množina všech podmnožin množiny X X X (t.j., relací na množině X) uspořádaná inkluzí. Buď R G V (X x X) relace na X a A podmnožina uspořádané množiny V(X X X) tvořená všemi relacemi obsahujícími R A = {SeV(X xX)\RCS}. Definujme zobrazení / : A —y A předpisem f(S) = susos. Snadno se ověří, že / zachovává suprema řetězců. Nejmenší pevný bod zobrazení / (sestrojený v důkaze věty 4.4) je nejmenší tranzitivní relace na množině X obsahující relaci R. Nazývá se tranzitivní obal relace R. Poznamenejme, že / nezachovává všechna suprema. Buď A uspořádaná množina, a, & G A. Budeme označovat a V b = sup{a, &} a a A b = inf{a,&}. Často také budeme značit \J X = supX a f\ X = infX. Připomeňme, že uspořádaná množina A se nazývá svaz, pokud pro libovolné prvky a, & G A existují a V b i a A b. Lemma 4.7. Buď A svaz, a,b,c G A. Pak platí a V (6 A c) < (a V 6) A (a V c) Důkaz. Nechť a,b,c G A. Platí a < (a V i), a < (aV c), b A c < b < (a V b) a b A c < c < (a V c). Tedy platí a V (6 A c) < (a V 6) a a V (6 A c) < (a V c). Odsud plyne tvrzení lemmatu. D Rovnost v 4.5 obecně neplatí. Svazy, v nichž tato rovnost platí, se nazývají distributivní. Podobně jak v 4.5 se ukáže, že pro libovolnou množinu I platí a A \Z&i > \/(a Abi). i£l i£l Dokonce, pro libovolné množiny 7, J8-, i G 7 platí (i) A V «o-^ V Aaw) iei je Ji feFiei kde 771 je množina všech zobrazení / : 7 —y [J Ji takových, že f (i) G Ji pro libovolné iei i e i. Důkaz je následující: pro libovolné / G F a libovolné i G 7 platí l\aif(i) < ai7(i) < y aü-iei jej,- 17 Tedy pro libovolné / G F platí Aa«7(o ^ A V aii- iei ieijeJi Odsud však již plyne dokazovaná nerovnost (1). Konstrukce reálnych čísel: V teorii množin již umíme sestrojit racionální čísla. Nyní ukážeme, jak lze sestrojit čísla reálná. Především však musíme definovat uspořádání na množinách Z a Q. V Z položíme (a, b) < (c,d) <£> a + d < c + b (odpovídá to tomu, že a — b < c — d). V Q (a, b) < (c, d), 6, d > 0 <^ ad < c& (odpovídá to tomu, že a&-1 < cd-1). Rez v množině Q racionálních čísel definujeme jako dvojici (X, Y) neprázdných podmnožin množiny Q splňující (1) XC\Y = 0 (2)lUľ = Q (3) x G X, y G F => x < y. Rezy v Q jsou jednoho z následujících tří typů: (a) mezera: X neobsahuje největší prvek a Y neobsahuje nejmenší prvek (b) dedekindovský řez 1. druhu: X obsahuje největší prvek a Y neobsahuje nejmenší prvek (b) dedekindovský řez 2.druhu: X neobsahuje největší prvek a Y obsahuje nejmenší prvek. (Čtvrtá možnost, že X obsahuje největší prvek a Y obsahuje nejmenší prvek (takový řez by se nazýval skok) nemůže v Q nastat.) Nyní IR definujeme jako množinu všech řezů, které jsou buď mezery nebo dedekin-dovské řezy 1.druhu. (Přitom mezery odpovídají iracionálním číslům a dedekin-dovské řezy 1.druhu číslům racionálním.) Uspořádání a aritmetické operace definujeme pro reálná čísla následovně: (X,Y) < (X',Y') öICI' (X,Y) + (X',Y') = ( ,Y + Y') (X,Y)-(X',Y') = ( ,Y-Y'). Zde X + Y = {x + y\x G X, y G Y} X -Y = {x-y\x G X, y G Y}. Platí sup(Xi,^) = (|JXi,f|^) 18 5. Kombinatorika Buď S konečná množina. Variace definujeme jako uspořádané výběry prvků množiny S a kombinace jako neuspořádané výběry. Má-li množina S n prvků, mluvíme o variacích (kombinacích) n prvků. Má-li příslušný výběr k prvků, mluvíme o variacích (kombinacích) k-té třídy. Variace i kombinace mohou být jak bez opakování, tak s opakováním. Variace k-té třídy z n prvků jsou právě zobrazení k-prvkové množiny X do n-prvkové množiny S. Z 4.1. (3) ihned plyne, že počet variací s opakováním k-té třídy z n prvků je n . Variace (tím se rozumí bez opakování) k-té třídy z n prvků jsou právě prostá zobrazení X —y S. Věta 5.1. Počet variací k-té třídy z n prvků je roven (n^k), (kde k < n). Důkaz. Indukcí vzhledem ke k. Variace s\ . . . s^-i dává právě n — k + 1 variací s\ . . . Sk-i-Sk- Tedy počet variací k-té třídy je n(n — 1) ... (n — k + 1). D Bijektivní zobrazení S —> S jsou právě permutace množiny S. Z 5.1. ihned plyne, že počet permutací n-prvkové množiny je nn. Kombinace k-té třídy z n prvků jsou právě k-prvkové podmnožiny množiny o n prvcích. Věta 5.2. Pro k < n je počet kombinací k-té třídy z n prvků roven n\ {n-k)\k\ Důkaz. Každá kombinace k-té třídy určuje k\ variací. Tvrzení tedy plyne z 5.1. D Čísla n\ ni kj {n-k)\k\ se nazývají kombinační. Mají následující vlastnosti; lze je odvodit přímo z definice nebo pomocí binomického rozvoje. (i) (3 = L-k) n (2) E ffl = 2" n (3) Ľ(-i)*a)=o n (4) Ľ(-l)**ffi=0 (9) H1) = «) + G-i)...... (vztah (4) odvodíme derivováním binomického rozvoje (l-\-x)n podle x a dosazením x = -1). Věta 5.3. Počet kombinací k-té třídy z n prvků s opakováním je roven n + k — 1 k Důkaz. Buď si . . . s k kombinace s opakováním k-té třídy vybraná z množiny Son prvcích. Doplňme ji všemi prvky množiny S. Tedy pro S = {a, 6, c, d.e} a kombinaci 19 s opakovaním bbd dostaneme abbbcdde. Navzájem různé prvky oddělíme svislou čarou. V našem příkladě dostaneme a16661c|cřcř| e. V obecném případě dostaneme n + k prvků rozdělených n — 1 čarami. Poněvadž počet možných míst pro svislé čáry je n + k — 1, počet možností je ( _7 ) = \ k~ )• To je však právě počet kombinací s opakováním. D Mějme nyní n-prvkovou množinu S a vlastnosti P\,. . . , P&. Buď n i počet prvků množiny S s vlastností Pí a obecněji n^...^ počet prvků množiny S s vlastnostmi Pi,. . . ,Pr. Nechť n(0) označuje počet prvků množiny S, které nemají žádnou z vlastností Pz-. Věta 5.4. (princip inkluze a exkluze). n(0) = n - ^rii + ^ nilÍ2----------h (-1)* ^ nil,,,i3------\- {-l)kni,,,k i «1<«2 il<-"<ís Důkaz. Prvek, který nemá žádnou z uvažovaných vlastností se počítá jednou ve sčítanci nav dalších sčítancích se neobjeví. Prvek, který má právě vlastnost Pj se objeví jednou ve sčítanci n a jednou ve druhém sčítanci J^ nz-, takže jeho příspěvek i k pravé straně je 0. Stačí, když ukážeme, že totéž nastane pro pro libovolný prvek mající právě vlastnosti Pj1,. . . , Pjr. Takový prvek přispívá jedničkou do každého součtu ii<--- (a, b) G R. Prvky množiny G se nazývají vrcholy grafu a prvky množiny E hrany grafu. Stupeň s (a) vrcholu a grafu (Cr, R) definujeme jako počet vrcholů b takových, že (a, b) G R. Věta 6.1. Y, s(a) = \R\- a£G Důkaz. Je zřejmý. Důsledek 6.2. V libovolném grafu je počet uzlů lichého stupně vždy sudý. Důkaz. Plyne z 6.1 neboť \R\ = 2\E\ je sudé číslo. D Cesta v grafu se definuje jako posloupnost ai, 02,. . . , an navzájem různých vrcholů taková, že (a8-, az'+i) G R pro z = l,...,n — 1. Říkáme, že tato cesta spojuje vrcholy a\ a an. Pokud nepředpokládáme, že vrcholy a8-, i = l,...,n — 1 jsou navzájem různé, říkáme, že máme definován sled v grafu. Graf se nazývá souvislý, jestliže libovolné dva navzájem různé vrcholy lze v něm spojit cestou. Kružnice v grafu (G}R) je posloupnost ai, 02,. . . , an, an_|_i = a\ vrcholů taková, že 01,02,. . . , an jsou navzájem různé, n > 2 a (a8-, aj+i) G R pro i = 1,. . . , n. Strom je souvislý graf bez kružnic. 21 Věta 6.3. Libovolný strom (Cr, R) mající aspoň dva vrcholy obsahuje aspoň dva vrcholy stupně 1. Důkaz. Buď nejdelší cesta v (G,R). Pak s(ai) = s(an) = 1 neboť v opačném případě by cesta šla prodloužit. D Věta 6.4. Souvislý graf (Cr, R) je strom, právě když \G\ = \E\ + 1. Důkaz. Buď (G}R) strom. Rovnost |Cr| = \E\ + 1 dokážeme indukcí. Pro |Cr| = 1 tvrzení platí. Předpokládejme, že platí pro každý graf o n vrcholech a uvažujme graf (G}R) o n + 1 vrcholech. Podle 6.3 G obsahuje vrchol v stupně 1. Pak graf (G1 = G — {v}} R = R Pi (G' x G')) je strom. Podle indukčního předpokladu platí I Cr'I = I .E'I + 1. Avšak |Cr| = I Cr'I + 1 a \E\ = \E'\ + 1, takže tvrzení platí i pro graf Opačnou implikaci rovněž dokážeme indukcí. Tvrzení platí pro |Cr| = 1 a předpokládejme, že platí pro všechny grafy o n vrcholech. Buď (Cr, R) graf o n-\-1 vrcholech takový, že |Cr| = \E\ + 1. Pokud G obsahuje vrchol stupně 1, jeho odebráním opět dostaneme graf (G'}R) splňující rovnost \G'\ = \E'\ + 1. Podle indukčního předpokladu je tento graf strom, takže stromem je i výchozí graf (Cr, R). Pokud G neobsahuje vrchol stupně 1, pak platí 2\E\ = \R\ = Y^ s(a) > 2|G| = 2|E| + 2, což není možné. D Kostra grafu (G}R) je strom (G}R) takový, že R C R. Věta 6.5. Libovolný souvislý graf obsahuje kostru. Důkaz. Udáme algoritmus nalezení kostry v souvislém grafu (Cr, E) (pro jeho zadání je výhodnější popsat graf pomocí vrcholů a hran). Postupně volíme hrany e tak, že vzniklý graf neobsahuje kružnici. Postup se zastaví, pokud hranu en_|_i již nelze přidat. Ukážeme, že vzniklý graf (Cr, Ei), E\ = {ei,...,en} je strom, t.j., je hledanou kostrou. Podle konstrukce, tento graf neobsahuje kružnici. Musíme ukázat, že je souvislý. Předpokládejme, že tomu tak není, t.j., existují vrcholy a, b G G, které nelze spojit cestou v (Cr, E\). Existuje cesta a = ai,. . . , a^ = b v (Cr, E). Buď i nejmenší číslo i = 1,. . . , k takové, že a, a8- lze spojit cestou v (Cr, E\) (nebo i = 1) a a, aj+i nelze spojit cestou v (Cr, E\). Pak E\ U {a8-, az'+i} neobsahuje kružnici, což není možné. D Podgraf grafu (G}R) definujeme jako graf (G'}R) takový, že G C G' a R C R. Pokud R = R Pi (Cr' x Cr'), pak podgraf (G'}R) se nazývá úplný a značíme jej stručně Cr'. Komponenta grafu (G, R) se definuje jako největší souvislý podgraf (Cr', R) grafu (G, R). Zřejmě se musí jednat o úplný podgraf. Věta 6.6. Dvě různé komponenty grafu (G}R) jsou disjunktní. Důkaz. Tvrzení plyne ze skutečnosti, pokud Cri a G2 jsou úplné souvislé podgrafy grafu (Cr, R) a Gi D G2 ^ 0, pak podgraf Cri U G2 je souvislý. 22 Důsledek 6.7. Komponenty grafu (G,R) tvoří rozklad množiny vrcholů G. Důkaz. Plyne z 6.6. a skutečnosti, že libovolný vrchol grafu patří do nějaké komponenty. Vrchol v souvislého grafu (Cr, R) se nazývá artikulace, pokud úplný podgraf G — {v} je nesouvislý. Hrana {u, v} souvislého grafu (Cr, R) se nazývá most, pokud graf (Cr, E — {u, v}) je nesouvislý. Graf se nazývá eulerovský pokud stupeň libovolného jeho vrcholu je sudé kladné číslo. Sled a\,. . . , an v grafu se nazývá tah, pokud pro libovolnou hranu e grafu existuje nejvýše jedna dvojice az',az'_|_i taková, že {az-, az'_|_i} = e. Tah se nazývá uzavřený, pokud a\ = an. Řekneme, že graf lze sestrojit jedním tahem, pokud v něm existuje tah, v němž se libovolná hrana vyskytuje právě jednou. Věta 6.8. Graf lze sestrojit jedním tahem, právě když je souvislý a eulerovský. Důkaz. Jestliže graf lze setrojit jedním tahem, pak musí být souvislý. Navíc nemůže obsahovat vrchol lichého stupně neboť tah do daného vrcholu vstupuje přesně tolikrát, kolikrát z něho vystupuje. Tedy graf je eulerovský. Naopak, buď (Cr, R) souvislý eulerovský graf. Zvolme vrchol v £ G. Poněvadž graf je souvislý, existuje hrana {v, w}. Je-li tato hrana most, pak jejím odstraněním dostaneme nesouvislý graf (Cr, E — {v, w}), jehož komponenta obsahující v obsahuje právě jeden uzel lichého stupně. To odporuje 6.2. Tedy {v,w} není most, takže vrcholy v a w jsou spojeny cestou v grafu (G,E — {v,w}). Tedy vrchol v leží na kružnici grafu (G,R). Sestrojená kružnice tvoří uzavřený tah začínající a končící ve vrcholu v. Buď T nejdelší uzavřený tah grafu (G,R) začínající a končící ve vrcholu v. Buď (G',E') podgraf grafu (Cr, R) složený ze všech hran grafu (Cr, R) nepatřících do tahu T a všech uzlů, na nich ležících. Zřejmě (G',E') je eulerovský graf. Poněvadž graf (Cr, R) je souvislý, existuje vrchol u patřící do G' i do T. Poněvadž jsme dokázali, že v eulerovském grafu leží libovolný vrchol na kružnici, existuje kružnice grafu (C, E') obsahující vrchol u. Přidáním této kružnice k tahu T dostáváme delší tah, což není možné. Tedy Cr' = 0, čímž je důkaz ukončen. D Graf se nazývá rovinný, jestliže jej lze nakreslit v rovině tak, že hrany se nepro-tínají (pouze se dotýkají ve vrcholech).