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).