Úvod do teorie množin a logiky 2

Ostravská univerzita v Ostravě Přírodovědecká fakulta

Úvod do teorie množin a logiky 2 Verze ke dni 10. 12. 2008

David Bartl

2006

Obsah 1 První setkání s pojmem množiny

5

2 Další základní predikáty teorie množin: inkluze a ostrá inkluze

13

3 Základní množinové operace

19

4 Neuspořádaná dvojice. Uspořádaná dvojice

25

5 Další operace s množinami a další predikáty teorie množin

29

6 Další pojmy: kartézský součin a projekce, množina zobrazení mezi dvěma množinami, poznámka k potenční množině 41 7 Vlastnosti relací. Relace částečného uspořádání

47

8 Relace lineárního uspořádání

55

9 Husté uspořádání. Dobré uspořádání

57

10 Částečné uspořádání – další pojmy

59

11 Relace ekvivalence

65

12 Poznámka o kvaziuspořádání

73

13 Mohutnost množin

75

Použitá literatura

81

Řešení cvičení

83

Dodatek A: Obsah přednášek z UTELO

97

Dodatek B: Cvičení ze základů teorie množin

101

Vysvětlivky k používaným symbolům

105

3

4

OBSAH

Kapitola 1

První setkání s pojmem množiny Začněme intuitivním zavedením pojmu „množinaÿ. Množinou (v intuitivním smyslu) rozumíme shrnutí určitých objektů (čísel, bodů, útvarů v rovině, předmětů našeho nazírání, . . . ) – o těchto objektech hovoříme jako o prvcích (tj. elementech) – do jediného většího celku-množiny, který je obsahuje. Množina je dostatečně určena, jestliže o každém objektu (číslu, bodu, . . . ) jsme schopni říci, zda do dané množiny patří, nebo ne. Dále „platíÿ, že každý prvek může být v množině obsažen jen (tzn. nejvýše) jednou. Jinými slovy, žádný prvek v množině nemůže být obsažen dvakrát (nebo třikrát apod.). Právě uvedené tři odstavce možná vypadají velice odborně, jako skutečné matematické definice. Ale není tomu tak. Pojem množiny tímto popisem příliš objasněn není. Pokusili jsme se sice zavést pojem množiny, ale nepodařilo se nám to bez toho, že bychom k tomu použili další, dosud neobjasněné pojmy, jako „shrnutíÿ nebo „objektÿ. Skutečný matematik se proto okamžitě začne ptát: „Co je to shrnutí‘ ?ÿ „Co je to objekt‘ ?ÿ („Co je to číslo‘ ?ÿ) ’ ’ ’ Čtenář nyní možná očekává, že autor skript tyto pojmy za chvíli vysvětlí. Nebo že autor ví o nějakém jiném řešení naznačeného problému (jak pojem množiny zavést) a řešení časem prozradí. Bohužel, není tomu tak. Pojem množiny je jeden ze základních matematických pojmů, který nelze definovat. Není možné jej definovat, aniž bychom se odvolali na některý jiný, dosud nezavedený pojem. Situace je taková, že pojem množiny se nám nepodaří si vzájemně vysvětlit, aniž bychom už dopředu alespoň nějakou představu o pojmu množiny měli. (Není nutné vědět, že se tomuto pojmu říká zrovna „množinaÿ, ale je potřeba už předem tento pojem znát.) Je proto nutné se odvolat na vlastní intuici – to jsme ostatně naznačovali už na samém začátku této kapitoly. Jestliže tedy čtenář první tři odstavce této kapitoly přečetl a bez nesnází jim porozuměl, je to zřejmě z důvodu, že již nějakou vlastní intuitivní představu o pojmu množiny měl (ať už ze školy základní nebo střední nebo i odjinud). Historická poznámka. Samotný pojem množina je poměrně mladý. Až do 19. století se v matematice nepoužíval. (Ačkoliv matematici samozřejmě i předtím pracovali se souhrny objektů. Ve své intuitivní podobě tedy pojem množiny 5

6

KAPITOLA 1. PRVNÍ SETKÁNÍ S POJMEM MNOŽINY

byl v matematice přítomen i dříve.) V českém jazyce se slovo „množinaÿ po prvé objevilo roku 1884 v článku českého matematika Matyáše Lercha (1860–1922). Slovo „množinaÿ je v našem jazyce patrně odvozeno od slova „množstvíÿ. — — — Již jsme si uvedli, že množina je dostatečně určena, pokud o každém objektu (prvku) jsme schopni říci, zda do dané množiny patří, nebo ne. Množinu nejsnáze určíme, když všechny její prvky vyjmenujeme. Seznam prvků množiny uvádíme ve složených závorkách. Například {„aÿ, „bÿ, „cÿ} je množina obsahující tři písmena „aÿ, „bÿ a „cÿ. (Správný matematik se opět zeptá: „Co je to písmeno?ÿ) Jiným příkladem je množina {10, 11, 12, . . . , 98, 99} neboli množina všech přirozených čísel od 10 do 99. Pro zkrácení zápisu lze použít tři tečky. (Čtenář jejich použití vidí v příkladu.) Jsou tyto množiny dostatečně určeny? Jsme o každém objektu schopni říci, zda do dané množiny patří, či nikoliv? Ano. Zkusme si klást následující otázky: Je číslo 10 prvkem množiny {10, 11, 12, . . . , 98, 99} ? Odbočka. Abychom množinu {10, 11, 12, . . . , 98, 99} nemuseli neustále opisovat, proveďme následující označení. Položme A = {10, 11, 12, . . . , 98, 99} . Od této chvíle bude znak A mít stejný význam jako množina všech přirozených čísel od 10 do 99. Znak A tuto množinu bude označovat. (Čtenář se tak kromě použití tří teček naučil další dovednost: označovat množiny.) Konec odbočky. Vraťme se k naší otázce. Odpověď je ano, číslo 10 je prvkem množiny A. Lze též říkat, že číslo 10 patří do množiny A nebo že číslo 10 náleží množině A. Stručně píšeme, že 10 ∈ A . Znak „∈ÿ – „náležíÿ – je odvozen od slova „elementÿ (prvek). (Slovo element pochází z latiny, kde znamenalo prvek, živel, počátek.) A proč platí 10 ∈ A ? Protože číslo 10 je uvedeno v seznamu prvků množiny A – viz výše. Jiná otázka: je číslo 9 prvkem množiny A ? Ne. Píšeme 9∈ / A. Číslo 9 nepatří do množiny A, protože nebylo uvedeno v seznamu jejích prvků. A tak dále (pro ostatní přirozená čísla i pro jiné objekty). Vidíme, že množiny zavedené výčtem svých prvků jsou dobře určeny: o každém objektu jsme schopni říci, zda do takto zavedené množiny patří, nebo ne (podíváme se do seznamu). — — — Podívejme se na jiný příklad množiny zavedené výčtem. Položme A = {a, a} ,

7 kde a je nějaký prvek. Znak a je proměnná, která má pro tuto chvíli význam nějakého, blíže neurčeného prvku, označuje ten prvek. Proměnná a je pro tuto chvíli konstantní. Proměnná A oproti dřívější úvaze (kde označovala množinu celých čísel od 10 do 99) změnila svůj význam. Nyní označuje množinu {a, a}. Předpokládám, že čtenář se se zápisem (množinou) {a, a} ještě nesetkal a je překvapen. Čtenář si možná klade otázku, zda uvedený zápis považovat za množinu a zda je to vůbec dobře. Ověřme tedy, že A je množina a že je dobře určena. Zodpovíme tedy následující dvě otázky: Platí a ∈ A ? Ano. Prvek a je totiž uveden v seznamu prvků výše zavedené množiny A. (V seznamu je dokonce uveden dvakrát.) Nechť c je nějaký jiný prvek, c 6= a. Platí c ∈ A ? Ne. Prvek c není uveden v seznamu prvků množiny A. (Kromě prvku a tam žádný jiný prvek uveden není.) Vidíme, že množina A je dobře určena: o každém objektu jsme schopni říci, zda do množiny A patří, nebo nepatří. Uvažujme nyní množinu B = {a} (prvek a je zde uveden pouze jednou). Platí a ∈ B ? Ano. Jestliže c je prvek různý od a (c 6= a), platí c ∈ B ? Ne. Výše uvedenými úvahami jsme dokázali svoje první (matematické) tvrzení: Množiny A = {a, a} i B = {a} mají stejné prvky. Co to znamená? Znamená to, že pro každý prvek c platí: c ∈ {a, a} právě tehdy, když c ∈ {a}. Důkaz. Budiž c nějaký prvek. Nyní jsou dvě možnosti: (a) buď c = a, (b) anebo c 6= a. A třetí možnost není! (Tertium non datur!) Ad (a). Když c = a, pak prvky c i a jsou totožné (obě proměnné c i a označují jeden a tentýž prvek). A již víme, že a ∈ A i a ∈ B. Ad (b). Když c 6= a, pak jak už víme, c ∈ / A ani c ∈ / B. Uvažujeme-li obě možnosti dohromady (a více možností není), dostáváme, že c ∈ A právě tehdy, když c ∈ B, q. e. d. Tři poznámky k důkazu. (1) Čtenáře asi udivilo, proč jsme v důkazu zdůraznili takovou „samozřejmostÿ, že třetí možnost není. Možná se však najdou i takoví čtenáři, kteří už jsou obeznámeni s tzv. Russellovým paradoxem, na nějž Bertrand Russell1 narazil v roce 1902. Russellův paradox ve své době v ma1 Bertrand Russell (1872–1970) byl anglický matematik, později matematiku opustil a věnoval se filosofii a politice. Jeho cílem bylo vybudovat matematiku na čistě logickém základě. Proto přinejmenším od roku 1901 pracoval na monumentálním díle Principia Mathematica. Na díle pracoval společně s Alfredem Whiteheadem. První svazek tohoto díla vyšel v Cambridgi v roce 1925, druhý a třetí svazek v roce 1927. Původně byl v plánu ještě čtvrtý svazek, o geometrii, měl jej psát pouze Whitehead, ale nikdy nevyšel. Práce na tomto velkolepém díle představovala pro Russella obrovskou zátěž. Velmi vyčerpávající bylo, když se (dlouhou dobu marně) snažil vyřešit elementární paradoxy (např. nyní známý Russellův paradox aj.), na které při psaní díla narážel. Uvádí, že „duševní úsilí, které psaní tohoto díla vyžadovalo, nenapravitelně vyčerpalo jeho myšlenkovou kapacituÿ. Prohlásil doslova: „Ani jeden z nás [Russell ani Whitehead] by tuto knihu nedokázal napsat sám. I při společné práci a s ulehčením, jež nám přinesla vzájemná diskuse, bylo naše úsilí tak nesmírné, že jsme se nakonec oba od matematické logiky odvrátili s jakýmsi odporem.ÿ * Dílo Principia Mathematica je psáno převážně symbolickým jazykem a, jak už naznačeno, jeho rozsah je ohromující. Je proto ironií, že dnes je toto pojednání zajímave spíše jen z historického hlediska. Soudobí matematici toto dílo vlastně moc nečtou. Kdo ví, jaký osud tuto pozoruhodnou knihu čeká? (Kdo ví, jaký osud čeká ostatní matematické knihy??) Matematik Godfey Harold Hardy podává následující svědectví o rozhovoru, který vedl s Bertrandem

8


tematice způsobil hlubokou krizi.2 Jako jedno možné řešení této krize někteří matematici navrhovali odmítnout tzv. zákon vyloučeného třetího (latinsky „tertium non daturÿ), neboli zákon, že zde žádná třetí možnost není. My s tímto zákonem naopak souhlasíme a v důkazu jsou zvýrazněna místa, kde byl použit. (2) Na konci důkazu stojí latinská zkratka q. e. d., často psaná i velkými písmeny (Q. E. D.), za slova „quod erat demonstrandumÿ. Česky to znamená „což bylo dokázatiÿ. Odtud je i česká zkratka c. b. d. (jen malými písmeny) se stejným významem. Na konci každého důkazu totiž bývá velmi dobrým zvykem nějak naznačit, že důkaz skončil. Ukončení důkazu lze oznámit buď slovy (např. „a tímto je důkaz ukončenÿ) nebo zkratkou (c. b. d., q. e. d.). S velikou oblibou se k označení konce důkazu používá také čtvereček nebo . (3) Snad již jen pro úplnost dodejme, že slovo „adÿ je latinská předložka, která česky znamená „kÿ (ad (a) – česky k bodu (a)). — — — Dokázali jsme si (a byl to opravdu poctivý matematický důkaz – na rozdíl od spíše intuitivního začátku této kapitoly), že množiny A = {a, a} a B = {a} mají stejné prvky. Z toho vyplývá (?), že množiny A a B jsou si rovny (A = B). Proč zpochybňující otazníček? Přeci se opět zdá být přirozené, že „ jestliže dvě množiny mají stejné prvky, potom jsou si rovnyÿ. Ve skutečnosti toto tvrzení až tak samozřejmé není, jde o jeden z axiomů teorie množin (tzv. axiom extensionality3 ). A v místě zpochybňujícího otazníčku jsme použili právě uveRussellem: „Vzpomínám si, jak mi Bertrand Russell vyprávěl o hrozném snu. Zdálo se mu, že se nachází v univerzitní knihovně někdy kolem roku 2100. Kolem polic s knihami procházel knihovník s obrovským kbelíkem, bral jednu knihu po druhé, prohlížel si je a buď je dával zpátky na polici, nebo je házel do kbelíku. Nakonec přišel ke třem velkým svazkům, v nichž Russell poznal výtisk díla Principia Mathematica. Vzal jeden svazek, obrátil několik stránek a na chvíli se zdálo, že ho podivné symboly zmátly. Pak knihu zavřel, podržel ji v ruce a zaváhal. . . ÿ ** Russell se již k matematice nevrátil. Věnoval se filosofii a politice – byl rozhodným zastáncem pacifismu. Už za 1. světové války byl 6 měsíců vězněn za to, že z důvodů svědomí odmítl nastoupit vojenskou službu. Od 50. let 20. století se stále aktivněji zapojoval do celosvětového mírového hnutí proti jaderné válce. V roce 1950 byl Bertrand Russell oceněn Nobelovou cenou za literaturu. * John D. Barrow, Pí na nebesích, str. 122. Viz seznam literatury na konci těchto skript. ** John D. Barrow, Pí na nebesích, str. 123. 2 Pro zájemce popíšu, v čem Russellův paradox spočívá: Uvažujme množinu N (písmeno N psané německou frakturou) všech množin, které nejsou prvkem sama sebe. Neboli, nějaká množina X patří do množiny N (platí X ∈ N) právě tehdy, když množina X neobsahuje samu sebe (množina X splňuje vlastnost X ∈ / X). Máme tedy

N = {X ; X ∈ / X }. A nyní si položme otázku: Je množina N prvkem sama sebe? Platí N ∈ N ? Podívejme se na definici množiny N. Tato množina obsahuje právě ty množiny, které neobsahují sebe sama. Jestliže platí N ∈ / N (množina N neobsahuje sebe sama), potom množina N musí být prvkem množiny N (platí N ∈ N). Naopak, jestliže množina N obsahuje sama sebe (platí N ∈ N), potom N není obsaženo v N (platí N ∈ / N), protože množiny obsahující sebe sama v množině N nejsou přítomny. Shrnutí: N ∈ N právě tehdy, když N ∈ / N. Paradox. 3 Axiomem rozumíme tvrzení, které přijímáme jako pravdivé; pravdivost axiomu tedy nedokazujeme, nýbrž ji předpokládáme. Zmíněný axiom extensionality je následující tvrzení: Mají-li dvě množiny A a B stejné prvky (tzn., že pro každý prvek c platí c ∈ A právě tehdy,

9 dený axiom. Pokud s tímto axiomem souhlasíme (a my s ním souhlasit budeme), je naše vyvozování korektní. Proto odvozený závěr, že A = B, je správný. Z dlouhých úvah lze učinit stručné shrnutí: jestliže je nějaký prvek ve výčtu prvků nějké množiny uveden dvakrát (nebo i vícekrtát, např. {a, a}), je to totéž, jako kdyby daný prvek byl v seznamu uveden pouze jednou (např. {a}). — — — Přejděme k dalšímu příkladu. Buďte a a b nějaké dva prvky. Poznámka. Prvky a a b nemusejí být nutně dva různé prvky! Vztah a 6= b tedy může nebo nemusí platit. (Obdobně vztah a = b může nebo nemusí platit.) Řekl jsem totiž pouze „buďte a a b nějaké dva prvkyÿ. Neřekl jsem „buďte a a b dva různé prvkyÿ. Prosím proto čtenáře, aby si na tuto jemnost dával pozor a nenechal se zbytečně „nachytatÿ. Nechť tedy a a b jsou nějaké dva prvky. Obdobným způsobem se dokáže, že {a, b} = {b, a} . Důkaz. Zvolme libovolný prvek c. Jsou dvě možnosti: (a) buď platí c = a nebo c = b, (b) anebo platí c 6= a a současně c 6= b (a třetí možnost není). Ad (a). Když c = a nebo c = b, potom c ∈ {a, b} i c ∈ {b, a}. Prvek c je uveden v seznamu prvků obou množin. Ad (b). Pokud c 6= a a zároveň c 6= b, potom c ∈ / {a, b} ani c ∈ / {b, a}. Tentokrát se prvek c nenachází na seznamu prvků zádné z uvedených dvou množin. Tímto jsme ověřili, že množiny {a, b} i {b, a} mají tytéž prvky. Odtud vyplývá (ve skutečnosti opět užitím již zmíněného axiomu extensionality), že obě množiny jsou si rovny, {a, b} = {b, a}, c. b. d. Z právě dokázaného tvrzení (tj. tvrzení, že {a, b} = {b, a}) si můžeme odnést ponaučení, že nezáleží na pořadí, v jakém jsou prvky množiny vyjmenovány. (Připomínám též ponaučení, které jsme uvedli výše: jestliže nějaký prvek je uveden ve výčtu prvků nějaké množiny, potom je lhostejné, zda daný prvek je ve výčtu uveden dvakrát (třikrát, . . . ) nebo jenom jednou.) Kontrolní otázka: bude uvedený důkaz tvrzení, že {a, b} = {b, a}, „fungovatÿ i v případě, že prvky a a b jsou stejné (a = b)? [Ano. Ale proč?] — — — Uveďme si ještě jeden příklad množiny zavedené výčtem svých prvků. Podívejme se na množinu {} . Vidíme, že seznam je prázdný, uvedená množina neobsahuje žádný prvek. Jde o tzv. prázdnou množinu. Prázdnou množinu obvykle značíme znakem ∅. (Značení {} lze používat také, je však méně časté.) Platí tedy ∅ = {}. Zdá se mi být vhodné na tomto místě uvést jedno upozornění. Pozor, mnokdyž c ∈ B), potom množiny A a B jsou si rovny (tedy A = B). Axiom extensionality, který je jedním z axiomů teorie množin, jsme si tedy už uvedli. Ostatní axiomy teorie množin již v těchto skriptech neuvádím, neboť by to znamenalo překročit rámec „ jednoduchého úvodu do teorie množinÿ.

10


žina {∅} je zase další příklad množiny zavedené výčtem. Je to množina, která jako svůj jediný prvek obsahuje prázdnou množinu ∅. (Vidíme, že množiny mohou být prvky jiných množin.) Množina {∅} tedy obsahuje prvek (prázdnou množinu), a tudíž není prázdná, {∅} = 6 ∅. Nezaměňujte proto množinu {∅} s množinou prázdnou! — — — Na závěr této kapitoly uvedu dvě poznámky. První z nich se týká množiny všech přirozených čísel {1, 2, 3, 4, 5, . . .} , již čtenář jistě zná už ze (střední nebo základní) školy. Na právě uvedené množině je zajímavé, že její prvky není možné všechny vyjmenovat. O každém daném objektu (prvku) jsme však schopni – při nejmenším „intuitivněÿ – říci, zda je, anebo není přirozeným číslem. Odtud – s odvoláním na úvodní část této kapitoly – plyne, že množina všech přirozených čísel je dobře určena. To v důsledku znamená, že v (intuitivní) teorii množin lze pracovat i s množinami, které není možné určit výčtem svých prvků. (Poznámka. V teorii množin se množina přirozených čísel zavádí formálním postupem, při kterém se na intuici nemusíme spoléhat. Tento postup je ale nad rámec těchto skript, proto jej zde neuvádím; vystačíme jen s intuitivním pochopením množiny přirozených čísel.) — — — Druhá poznámka se týká konvencí, které se při označování prvků množin většinou používají. Obyčejné prvky množin obvykle označujeme malými písmeny: a, b, c, . . . , x, y, z. A podobně. Matematické proměnné (jako např. x, y, z) v textu tradičně vyznačujeme kurzívou (písmo skloněné a poněkud odlišné kresby). Množiny prvků pak obyčejně značíme velkými písmeny: A, B, C, . . . Potřebujeme-li pracovat se soubory množin (říkáme též množiny množin, kolekce množin, systémy množin apod.), označujeme je s oblibou německou frakturou: A, B, C, . . . , X, Y, Z. Německé fraktuře se lidově (ne zcela správně ovšem!) říká též švabach. Protože předpokládám, že čtenář s německou frakturou není obeznámen, uvádím ji zde celou (s výjimkou písmen přehlasovaných, německého ostrého ß a několika slitků): ABCDEFGHIJKLMNOPQRSTUVWXYZ, a b c d e f g h i j k l m n o p q r s t u v w x y z . Případně lze systémy množin označovat písmem kaligrafickým (písmo ozdobně provedené; různá kaligrafická písma se mírou svojí ozdobnosti samozřejmě mohou lišit): A, B, C, . . . , X , Y, Z. Již poměrně vzácně je potřeba v matematice pracovat se systémy systémů množin. Obecně platí, že čím větší je systém množin, tím kroucenější (tím ozdobnější, případně tím gotičtější apod.) písmo pro jeho označení použijeme. — — —

11 Cvičení 1.1. Jsou dány prvky a, b, c. Uvažujme následující množiny: A = {a, b, a} , B = {a, b, c} , C = {b, a, b} , D = {c, a, a, b} , E = {} , F = ∅, M = {A, B, C} , N = {C, D, A} , O = {∅} , P = {F } . Které z uvedených množin jsou si rovny? (Rozmýšlejte pozorně!)

12


Kapitola 2

Další základní predikáty teorie množin: inkluze a ostrá inkluze Čtenář již ze základní školy jistě zná binární predikát rovnosti „=ÿ vyjadřující, že dva objekty jsou totožné, tj., že jde o jeden a týž objekt. Kromě toho čtenář musí znát také binární predikát náležení „∈ÿ vyjadřující, že jeden objekt (prvek) náleží jinému objektu (množině). Zatímco predikát rovnosti je univerzálním predikátem, neboť jeho použití se v matematice neomezuje jen na oblast teorie množin, používání predikátu náležení je zcela charakteristické (v podstatě) výlučně pro teorii množin. Pomocí predikátu náležení „∈ÿ, který jsme připomněli v předcházející kapitole, nyní zavedeme další základní predikáty teorie množin. Půjde o binární predikáty inkluze „⊆ÿ a ostré inkluze „⊂ÿ. Definice 2.1. (Inkluze a ostrá inkluze.) Říkáme, že množina A je podmnožinou množiny B a píšeme A ⊆ B právě tehdy, když každý prvek x množiny A je obsažen v množině B. Formálně máme A ⊆ B ⇐⇒ ∀x ∈ A: x ∈ B ⇐⇒ ∀x: x ∈ A ⇒ x ∈ B . Dále říkáme, že množina A je vlastní podmnožinou množiny B a píšeme A ⊂ B právě tehdy, když množina A je podmnožinou množiny B a množiny A a B jsou různé. Formálně máme A ⊂ B ⇐⇒ A ⊆ B ∧ A 6= B . Graficky lze pojem podmnožiny ilustrovat následujícím obrázkem: '$

A &% B Poznámka 2.1. Čtenář zřejmě ze střední školy zná zápisy typu ∀x ∈ A: ϕ(x) resp. ∃x ∈ A: ϕ(x), kde A je množina a ϕ(x) je formule. Uvedené zápisy čteme „pro každý prvek x množiny A platí ϕ(x)ÿ resp. „existuje prvek x množiny A 13

14

KAPITOLA 2. . . . INKLUZE A OSTRÁ INKLUZE

takový, že (resp. pro který) platí ϕ(x)ÿ. S jedním příkladem takového zápisu jsme se právě setkali ve výše uvedené definici: ∀x ∈ A: x ∈ B, takže ϕ(x) je zde formule „x ∈ Bÿ. Předpokládám však, že se zápisem typu ∀x: ϕ(x) resp. ∃x: ϕ(x), kde x je proměnná a ϕ(x) je formule, se čtenář – až na výše uvedenou definici – dosud nesetkal. Na čtení uvedených zápisů však není nic neobvyklého, čteme je „pro každý prvek x platí ϕ(x)ÿ resp. „existuje prvek x takový, že (resp. pro který) platí ϕ(x)ÿ. Uveďme ještě, že když A je množina, pak zápis zápis

∀x ∈ A: ϕ(x) ∃x ∈ A: ϕ(x)

je zkratka za je zkratka za

∀x: x ∈ A ⇒ ϕ(x) , ∃x: x ∈ A ∧ ϕ(x) .

Prosím čtenáře, aby uvedeným zkratkám věnoval trochu pozornosti a pokusil se nad jejich významem chvíli zamyslet. Poznámka 2.2. Když už jsme zaběhli do uvádění zkratek, rozmyslete si ještě, že x∈ /A znamená, resp. je zkratka za ¬(x ∈ A) , x 6= y znamená, resp. je zkratka za ¬(x = y) . První zkratka znamená, že „x není prvkem množiny Aÿ, druhá zkratka znamená, že „x se nerovná / je různé od yÿ. Poznámka 2.3. Předpokládá se sice, že čtenář je ze střední školy obeznámen se základními logickými spojkami a zpaměti zná i tabulky jejich pravdivostních hodnot, přesto je zde připomenu: ¬

negace

z latinského negatio = popření, čti „ne-ÿ, jiná značení: p¯, p0 .

∧

konjunkce

z latinského coniunctio = spojení, čti „aÿ, „a současněÿ, „a zároveňÿ, příp. „iÿ, jiné značení: & .

∨

disjunkce alternativa

z latinského disiunctio = rozpojení, rozloučení z latinského alternare = uvažovat jedno po druhém, čti „neboÿ, „aneboÿ.

⇒

implikace

z latinského implicare = připoutat, čti „ jestliže. . . , potom. . . ÿ, „-li. . . , pak. . . ÿ, „pokud. . . ÿ, „když. . . ÿ, jiné značení: → .

⇔

ekvivalence

z latinského aequivalens = stejně hodnotný, čti „právě tehdy, když. . . ÿ, „tehdy a jen tehdy, když. . . ÿ, „právě když. . . ÿ, jiná značení: ↔ , ≡ .

Tabulky pravdivostních hodnot jsou následující:

15 A 0 0 1 1

B 0 1 0 1

¬A 1 1 0 0

¬B 1 0 1 0

A∧B 0 0 0 1

A∨B 0 1 1 1

A⇒B 1 1 0 1

A⇔B 1 0 0 1

Poznámka 2.4. Nyní se vraťme k první definici, kde jsme zavedli pojem podmnožiny resp. vlastní podmnožiny a rozhodli se jej označovat „⊆ÿ resp. „⊂ÿ. Někteří autoři používají jiné značení, podmnožinu (nikoliv vlastní) označují symbolem „⊂ÿ. Zápisem A ⊂ B tito autoři vyjadřují, že ∀x ∈ A: x ∈ B. S pojmem vlastní podmnožiny tito autoři nepracují. My budeme symboly „⊆ÿ a „⊂ÿ používat ve významu podle výše uvedené definice.

Následující věta plyne přímo z definice inkluze.

Věta 2.1. Každá množina A obsahuje alespoň dvě podmnožiny, totiž ∅ a A. Formálně máme

∅⊆A

a

A ⊆ A.

Jelikož množiny ∅ a A jsou podmnožinami každé množiny A, nazýváme je triviálními podmnožinami množiny A.

Cvičení 2.1. Odůvodněte platnost výše uvedené věty.

Také následující věta se snadno odvodí pomocí definice inkluze a axiomu extensionality.

16

KAPITOLA 2. . . . INKLUZE A OSTRÁ INKLUZE

Věta 2.2. Dvě množiny A a B jsou si rovny právě tehdy, když jsou ve vzájemné inkluzi. Formálně: A = B ⇐⇒ A ⊆ B ∧ B ⊆ A . Poznámka 2.5. Nyní uvedená věta se často používá při důkazech rovnosti dvou množin. Předpokládejme, že jsou dány nějaké dvě množiny A a B a že máme dokázat rovnost obou množin. Máme tedy dokázat, že A = B. Důkaz provedeme tak, že postupně dokážeme inkluze A ⊆ B a B ⊆ A. Inkluze A ⊆ B se dokáže podle definice: Zvolíme libovolný prvek x ∈ A a nějakým způsobem dokážeme, že z faktu x ∈ A vyplývá x ∈ B. Jinou možností je dokázat, že z faktu x ∈ / B vyplývá x ∈ / A. V případě inkluze B ⊆ A se postupuje zcela obdobně. Cvičení 2.2. Odůvodněte platnost naposledy uvedené věty. Již jsme viděli, že každá množina A obsahuje alespoň dvě tzv. triviální podmnožiny, totiž prázdnou množinu a sama sebe, tedy ∅ a A. Souhrn všech podmnožin množiny A pak vytváří tzv. potenční množinu množiny A, kterou zavádíme v následující definici. Definice 2.2. (Potenční množina.) Potenční množinu množiny A označíme P(A) a rozumíme jí množinu všech podmnožin množiny A. Formálně máme P(A) = { X ; X ⊆ A } . Poznamenejme, že potenční množina množiny A se někdy značí také jen P (A) nebo 2A . Platí tedy P (A) = 2A = P(A). Poznámka 2.6. V předcházející kapitole jsme množiny vymezovali výčtem jejich prvků. V naposledy uvedené definici potenční množiny se ale setkáváme s množinou vymezenou jiným způsobem, totiž pomocí charakteristické vlastnosti jejích prvků. Množiny vymezené tímto způsobem lze zapsat pomocí cantorovského1 schématu x ; ϕ(x) , kde ϕ(x) je formule. Je to množina všech prvků x, které vyhovují podmínce ϕ(x). Poznamenejme, že má-li být existence množiny x ; ϕ(x) zaručena, formuli ϕ(x) nelze volit zcela libovolně, je nutné ji volit s ohledem na všeobecně přijímané axiomy teorie množin. Jak jsem však již při jedné příležitosti uvedl, vyjmenování těchto axiomů by překročilo rámec těchto skript. Ukažme si na příkladě, jak vypadá potenční množina prázdné množiny a potenční množina jedno- až tříprvkové množiny. Příklad 2.1. P {} = ∅ , P {a} = ∅, {a} , P {a, b} = ∅, {a}, {b}, {a, b} , P {a, b, c} = ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} . 1 Georg Cantor (1845–1918) byl německý matematik. Je to právě on, kdo je považován za zakladatele moderní teorie množin. Jako vůbec první se odvážil soustavně pracovat s aktuálně nekonečnými množinami a popsal jejich vlasnosti.

17 Cvičení 2.3. Kolik prvků má potenční množina P(A), jestliže množina A má n prvků (n = 0, 1, 2, 3, . . . )? Dokážete svoji odpověď odůvodnit? Potenční množinu je možné částečně uspořádat inkluzí. (Pojem částečného uspořádání zavedu v těchto skriptech v sedmé kapitole.) Například mezi prvky potenční množiny P {a} platí vztah ∅ ⊆ {a}, mezi prvky potenční množiny P {a, b} platí mj. vztahy ∅ ⊆ {a}, ∅ ⊆ {b}, {a} ⊆ {a, b}, {b} ⊆ {a, b} apod. Částečné uspořádání množin lze přehledně znázornit pomocí tzv. Hasseových diagramů. Znázorňujeme-li částečné uspořádání potenční množiny Hasseovým diagramem, používáme několik jednoduchých zásad: Podmnožiny se stejným počtem prvků zapisujeme do stejného řádku. Podmnožiny s větším počtem prvků zapisujeme do vyšších řádků, podmnožiny s menším počtem prvků do nižších řádků. Je-li jedna podmnožina obsažena v druhé podmnožině, nakreslíme mezi nimi spojnici. Spojnice kreslíme pouze mezi sousedními řádky. Podívejme se, jak částečná uspořádání některých potenčních množin z předcházejícího příkladu vypadají. Příklad 2.2. P {} :

∅

P {a} :

{a}

∅

P {a, b} :

{a, b} @ @ {b}

{a} @ @

P {a, b, c} :

∅

{a, b, c} H H HH H {a, b} {a, c} {b, c} H H HH HH HH HH {a} {b} {c} H H HH H ∅

Poznámka 2.7. Podíváte-li se blíže na Hasseův diagram tříprvkové množiny, zjistíte, že připomíná krychli. Vskutku: Hasseův diagram jednoprvkové množiny připomíná úsečku, což je jednorozměrná krychle, a Hasseův diagram dvouprvkové množiny připomíná čtverec, což je dvojrozměrná krychle. Rozšíření této úvahy již nechávám na čtenáři.

18

KAPITOLA 2. . . . INKLUZE A OSTRÁ INKLUZE — — —

Cvičení 2.4. Uvažujme systém množin M = {a, b}, {b, c}, {c, d}, {a, b, c}, {b, c, d} , kde a, b, c, d jsou navzájem různé prvky. Uspořádejte množinu M inkluzí, tj., rozhodněte, zda platí {a, b} ⊆ {b, c} anebo {b, c} ⊆ {a, b}, . . . , zda platí {a, b} ⊆ {a, b, c} anebo {a, b, c} ⊆ {a, b} atd. (Prozkoumejte všechny možnosti.) Nakreslete také Hasseův diagram vzniklého uspořádání.

Kapitola 3

Základní množinové operace Mějme zadány dvě množiny A a B. Pak pomocí základních množinových operací – které uvedeme za chvíli – z těchto dvou množin můžeme získat další množinu. Základními množinovými operacemi jsou sjednocení, jež označujeme znakem „∪ÿ, dále průnik, který označujeme znakem „∩ÿ, a rozdíl, k jehož označení používáme znak „\ÿ. Uvedené operace nyní definujeme. (Poznamenejme, že všechny uvedené operace jsou binární – mají dva operandy.) Definice 3.1. (Sjednocení.) Sjednocením dvou množin A a B je množina A ∪ B = {x ; x ∈ A ∨ x ∈ B }. Sjednocení A ∪ B množin A a B je tedy množina právě všech prvků x takových, že x náleží množině A nebo množině B (případně náleží oběma množinám současně). Graficky můžeme sjednocení A ∪ B dvou množin A a B znázornit následovně: '$ '$

B

&% A&% Kromě zápisu A ∪ B se sjednocení množin A a B někdy značí také A + B. (Uvedené značení A + B ale není příliš vhodné.) Definice 3.2. (Průnik.) Průnikem dvou množin A a B je množina A ∩ B = {x ; x ∈ A ∧ x ∈ B }. Průnik A ∩ B množin A a B je tedy množina právě všech prvků x, které náleží oběma množinám A i B současně. Graficky můžeme průnik A ∩ B dvou množin A a B znázornit následovně: '$ '$

&% A&% B Průnik dvou množin A a B se kromě zápisu A∩ ∩ B značí také A·· B nebo zkráceně jen AB. (Značení A · B ani AB nejsou moc vhodná.)

19

20

KAPITOLA 3. ZÁKLADNÍ MNOŽINOVÉ OPERACE

Definice 3.3. (Rozdíl.) Rozdílem dvou množin A a B je množina A \ B = {x ; x ∈ A ∧ x ∈ / B }. Slovy lze říci, že rozdíl A \ B množin A a B je množina obsahující právě ty prvky x, které leží v množině A a neleží v množině B. Graficky lze rozdíl A \ B dvou množin A a B znázornit následovně: '$ '$

&% A&% B Také rozdíl A \ B dvou množin A a B se někdy značí A − ˙ B popř. A − B. (Značení A − B není příliš vhodné.) Cvičení 3.1. Nechť A, B a C jsou množiny. Nahlédněte, že platí 1. A ∩ B = B ∩ A , 2. (A ∩ B) ∩ C = A ∩ (B ∩ C) , 3. A \ B ⊆ A , 4. A ∩ B ⊆ A , 5. A ∩ B ⊆ B . Cvičení 3.2. Nechť A, B a C jsou množiny. Platí také následující vztahy? 1. A \ B = B \ A ? 2. (A \ B) \ C = A \ (B \ C) ? 3. A \ B ⊆ B ? S rozdílem množin těsně souvisí pojem doplňku, který uvedeme v následující poznámce. Poznámka 3.1. (Doplněk.) Nechť A a C jsou dvě množiny (a předpokládejme, že množina A je obsažena v množině C, tedy A ⊆ C). Pak doplňkem množiny A v množině C rozumíme množinu A0C = C \ A

resp.

AC = C \ A .

Zápisy A0C a AC jsou dvě možná označení doplňku množiny A v množině C. Vidíme, že nejde o nic jiného než o rozdíl množin C a A. Doplněk množiny A můžeme označit také A0 nebo A, je-li z okolního kontextu zřejmé, v jaké množině doplněk množiny A uvažujeme. Graficky můžeme doplněk množiny A v množině C znázornit následujícím diagramem:

A

C

21 Poznamenejme, že doplněk (komplement) množiny A je vždy třeba uvažovat v nějaké množině. Pokud tak neučiníme, dostaneme A0 = { x ; x ∈ / A }, což není množina, ale pouze tzv. třída1 . Dosažené poznatky nyní stručně shrneme v následující poznámce. Poznámka 3.2. Podle výše uvedených tří definic máme A ∪ B = {x ; x ∈ A ∨ x ∈ B }, A ∩ B = {x ; x ∈ A ∧ x ∈ B }, A \ B = {x ; x ∈ A ∧ x ∈ / B }, kde A a B jsou množiny. To jinými slovy znamená, že pro libovolný prvek x platí x ∈ A ∪ B platí x ∈ A ∩ B platí x ∈ A \ B

právě tehdy, když právě tehdy, když právě tehdy, když

x ∈ A nebo x ∈ B, x ∈ A a současně x ∈ B, x ∈ A a současně x ∈ / B.

Právě uvedené tři vztahy budou užitečné při důkazech rovnosti množin provedených tzv. metodou neurčitého prvku, opírající se o axiom extensionality.

— — — V další části této kapitoly se zaměříme na základní vlastnosti výše uvedených operací s množinami. Z dřívějška možná znáte některé základní tautologie výrokové logiky, kterými jsou: De Morganova2 pravidla ¬(A ∨ B) ⇐⇒ (¬A ∧ ¬B) , ¬(A ∧ B) ⇐⇒ (¬A ∨ ¬B) . Zákon dvojí negace ¬¬A ⇐⇒ A . A distributivní zákony A ∧ (B ∨ C) ⇐⇒ (A ∧ B) ∨ (A ∧ C) , A ∨ (B ∧ C) ⇐⇒ (A ∨ B) ∧ (A ∨ C) . Znaky A, B a C ve všech výše uvedených tautologiích označují výrokové proměnné. 1 Pojem třídy je v teorii množin obecnější než pojem množiny. Lze říci, že každá množina je zároveň třídou; některé třídy však nejsou množinami. Vymezovat pojem třídy by přesáhlo rámec těchto skript. Při budování teorie množin se lze navíc – s trochou důvtipu – bez pojmu třídy docela dobře obejít. Pojem třídy proto blíže nezavádím. 2 Augustus de Morgan (čti mórgen) (1806–1871) – britský logik a matematik 19. století, průkopník a systematizátor moderní formální logiky a jejího propojení s algebrou. Po objevení de Morganových pravidel se mnoho dalších matematiků pokoušelo najít obdobné formulky, aby po nich také mohly být pojmenovány. Všeobecně známými však zůstala pouze de Morganova pravidla.

22


Uvedené tautologie mají svoje protějšky také v jazyce teorie množin. Obecně lze říci, že logické spojce „∧ÿ odpovídá množinová operace „∩ÿ, logické spojce „∨ÿ odpovídá množinová operace „∪ÿ, logické spojce „¬ÿ odpovídá doplněk množiny „0 ÿ (v nějaké další množině), logické spojce „⇒ÿ odpovídá predikát „⊆ÿ, logické spojce „⇔ÿ odpovídá predikát „=ÿ. Nyní si ukážeme, jak protějšky výše uvedených tautologií vypadají v jazyce teorie množin. Než tak učiníme, připomeňme, že zápis

x∈ / A je ekvivalentní zápisu ¬(x ∈ A)

(∗)

pro libovolný prvek x a libovolnou množinu A. Tvrzení 3.1. (De Morganova pravidla.) Nechť A, B a C jsou množiny. Potom platí: C \ (A ∩ B) = (C \ A) ∪ (C \ B) , C \ (A ∪ B) = (C \ A) ∩ (C \ B) . Důkaz. Ukážeme platnost prvního vztahu. Důkaz provedeme metodou neurčitého prvku: ukážeme, že pro libovolný prvek x platí x ∈ C \ (A ∩ B) právě tehdy, když x ∈ (C \ A) ∪ (C \ B); rovnost obou množin pak plyne pomocí axiomu extensionality. Postupným užitím definice rozdílu množin, vztahu (∗), definice průniku množin, de Morganova pravidla (z výrokové logiky), distributivity, definice rozdílu a sjednocení množin totiž máme: x ∈ C \ (A ∩ B) ⇐⇒ x ∈ C ∧ x ∈ / (A ∩ B) ⇐⇒ ⇐⇒ x ∈ C ∧ ¬ x ∈ (A ∩ B) ⇐⇒ ⇐⇒ x ∈ C ∧ ¬(x ∈ A ∧ x ∈ B) ⇐⇒ ⇐⇒ x ∈ C ∧ (x ∈ /A ∨ x∈ / B) ⇐⇒ ⇐⇒ (x ∈ C ∧ x ∈ / A) ∨ (x ∈ C ∧ x ∈ / B) ⇐⇒ ⇐⇒ x ∈ (C \ A) ∨ x ∈ (C \ B) ⇐⇒ ⇐⇒ x ∈ (C \ A) ∪ (C \ B) . Druhý vztah se dokáže obdobně.

Poznámka 3.3. První vztah z posledního tvrzení 3.1. lze znázornit následujícím diagramem: '$

C

'$

'$

&% &% A&% B

23 Cvičení 3.3. Samostatně dokažte druhé de Morganovo pravidlo z tvrzení 3.1. (metodou neurčitého prvku) a znázorněte jej obrázkem. Následující tvrzení obsahuje vztah odpovídající zákonu dvojí negace. Tvrzení 3.2. Pro dvě množiny A a C platí vztah C \ (C \ A) = A ∩ C . Důkaz. Důkaz provedeme metodou neurčitého prvku. Ukážeme, že pro každý prvek x platí x ∈ C \ (C \ A) právě tehdy, když x ∈ A ∩ C. Podle definice rozdílu množin, vztahu (∗), de Morganova pravidla (z výrokové logiky), distributivity (z výrokové logiky) a definice průniku množin máme: x ∈ C \ (C \ A) ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x∈C ∧ x∈ / (C \ A) ⇐⇒ x ∈ C ∧ ¬(x ∈ C ∧ x ∈ / A) ⇐⇒ x ∈ C ∧ (x ∈ / C ∨ x ∈ A) ⇐⇒ (x ∈ C ∧ x ∈ / C) ∨ (x ∈ C ∧ x ∈ A) ⇐⇒ x ∈ C ∧ x ∈ A ⇐⇒ x∈A∩C.

Tím je důkaz proveden.

Zbývá ukázat, jak v teorii množin vypadají distributivní zákony. Tvrzení 3.3. (Distributivní zákony.) Nechť A, B a C jsou množiny. Potom platí: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) , A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) . Důkaz. Pro libovolný prvek x platí: x ∈ A ∩ (B ∪ C) ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x ∈ A ∧ x ∈ (B ∪ C) ⇐⇒ x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⇐⇒ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⇐⇒ x ∈ (A ∩ B) ∨ x ∈ (A ∩ C) ⇐⇒ x ∈ (A ∩ B) ∪ (A ∩ C) .

Druhý vztah se dokáže obdobně.

Cvičení 3.4. Dokažte druhý distributivní zákon z předcházejícího tvrzení.

— — — Nakonec v této kapitole zavedeme pojem disjunktních3 množin.

24


Definice 3.4. (Disjunktní množiny.) Dvě množiny A a B jsou disjunktní právě tehdy, když mají prázdný průnik, tj. A ∩ B = ∅. Graficky můžeme disjunktní množiny znázornit následujícím obrázkem: '$ '$

B &% A&% — — —

Cvičení 3.5. Nechť A a B jsou dvě množiny. Nahlédněte (především nakreslením obrázků), že platí: 1. A \ B = (A ∪ B) \ B = A \ (A ∩ B) , 2. A \ (A \ B) = A ∩ B . Cvičení 3.6. Nechť A, B a C jsou množiny. Odůvodněte formálně (metodou neurčitého prvku) platnost následujících vztahů: 1. (B ∪ C) ∩ A = (B ∩ A) ∪ (C ∩ A) , 2. (B ∪ C) \ A = (B \ A) ∪ (C \ A) . Cvičení 3.7. Nechť A, B a C jsou množiny. Znázorněte graficky následující vztahy a dokažte je formálně. 1. (A \ B) \ C = A \ (B ∪ C) , 2. A \ (B \ C) = (A \ B) ∪ (A ∩ C) . Poznámka 3.4. Čtenářově pozornosti doporučuji také dodatek B těchto skript, ve kterém je přehledně vyjmenována celá řada dalších vztahů.

3 Nechceme-li používat cizích slov, můžeme říci, že množiny disjunktní jsou množiny rozpojené či rozloučené. Odvozeno z latinského disiunctio = rozpojení, rozloučení.

Kapitola 4

Neuspořádaná dvojice. Uspořádaná dvojice Začneme neuspořádanou dvojicí. Definice 4.1. (Neuspořádaná dvojice.) Neuspořádanou dvojicí prvků a a b rozumíme množinu {a, b} . V první kapitole těchto skript jsme poměrně důkladně dokazovali, že {a, b} = = {b, a}. Nezáleží tedy na pořadí prvků ve dvojici {a, b}. Odtud název „neuspořádaná dvojiceÿ. Pokud jsou prvky a a b od sebe různé, platí a 6= b, potom množina {a, b} je dvouprvková. Platí-li však a = b, potom množina {a, b} je samozřejmě jednoprvková. (Pokud je čtenář překvapen, připomínám, že nikde nebyl řečen předpoklad, že prvky a a b mají být od sebe různé. Případ a = b tedy není vyloučen.) Chtěli bychom však zavést pojem uspořádané dvojice, pro kterou jsou charakteristické dvě věci: (1) sestává ze dvou prvků (je to dvojice) a (2) záleží na pořadí, v jakém jsou prvky uvedeny (je to uspořádaná dvojice). Následující definici uspořádané dvojice poprvé použil polský matematik Kazimierz Kuratowski1 v roce 1921, stejnou definici později navrhnul také americký matematik Norbert Wiener2 . Definice 4.2. (Uspořádaná dvojice.) Uspořádanou dvojicí prvků a a b (v uvedeném pořadí) rozumíme množinu [a, b] = {a}, {a, b} . Vidíme, že pojem uspořádané dvojice je vyjádřen pouze za použití prostředků teorie množin. Uspořádaná dvojice je určitá množina, která jako své prvky obsahuje množiny: množina {a, b} určuje, ze kterých prvků daná uspořádaná dvojice sestává, a množina {a} určuje, který prvek je první. 1 Kazimierz

Kuratowski (1896–1980) – polský matematik. Významně přispěl k rozvoji množinové topologie. Věnoval se také deskriptivní teorii množin a teorii reálných funkcí. 2 Norbert Wiener (1894–1964) – americký matematik, je ale znám především jako zakladatel kybernetiky. Pracoval též v oblastech matematické analýzy, teorie pravděpodobnosti, matematické statistiky a v oblasti výpočetní techniky.

25

26

KAPITOLA 4. USPOŘÁDANÁ A NEUSPOŘÁDANÁ DVOJICE

Poznámka 4.1. Kromě zápisu [a, b], který jsme v těchto skriptech zavedli, se uspořádané dvojice značí také zápisem ha, bi nebo (a, b). Následující věta dokládá, že zavedený pojem uspořádané dvojice je ve shodě s výše uvedenými intuitivními požadavky a že jeho zavedení pomocí prostředků teorie množin bylo úspěšné. Věta 4.1. Pro libovolné čtyři prvky a, b, c, d platí [a, b] = [c, d]

právě tehdy, když

a = c a b = d.

Důkaz. Důkaz ekvivalence rozdělíme na dvě části, na důkaz implikace „⇐ÿ a implikace „⇒ÿ. Implikace „⇐ÿ je ovšem triviální. Dokážeme proto pouze implikaci „⇒ÿ. V důkazu implikace „⇒ÿ rozlišíme dva případy: buď a = b, anebo a 6= b. Když a = b, pak platí [a, b] = {a}, {a, b} = {a}, {a, a} = {a}, {a} = {a} . Protože podle předpokladu máme [a, b] = [c, d], množiny [a, b] = {a} i [c, d] = = {c}, {c, d} musejí mít stejné prvky. Odtud plyne {a} = {c} a {a} = {c, d}. Je tedy a = c = d. Protože a = b, máme a = b = c = d. Tím je implikace „⇒ÿ v případě a = b dokázána. Nyní předpokládejme, že a 6= b. Potom nutně platí, že také c 6= d. (Kdyby c = d, pak by platilo a = b. Stačí použít předchozí část důkazu, přičemž se zamění označení prvků a, b a c, d.) Víme tedy, že [a, b] = [c, d] neboli {a}, {a, b} = {c}, {c, d} . Obě množiny musejí mít stejné prvky. Platí tedy {a} ∈ {c}, {c, d} . Odtud plyne, že buď {a} = {c} ,

anebo {a} = {c, d} .

První možnost dává a = c. Druhá možnost dává a = c = d. To ovšem není možné, neboť c 6= d. Platí s výsledkem a = c. tedy první možnost Dále z předpokladu {a}, {a, b} = {c}, {c, d} plyne, že {a, b} ∈ {c}, {c, d} . Odtud buď {a, b} = {c} ,

anebo {a, b} = {c, d} .

První možnost dává a = b = c, což není možné, neboť a 6= b. Nastává tedy druhá možnost, kde {a, b} = {c, d}. Protože už jsme dokázali, že a = c, dostáváme b = d. Opět jsme dokázali, že a = c a b = d, čímž je důkaz implikace „⇒ÿ zcela završen. — — — Na závěr této kapitoly zavedeme pojem uspořádané trojice, uspořádané čtveřice atd.

27 Definice 4.3. (Uspořádaná trojice, uspořádaná čtveřice, uspořádaná n-tice.) Uspořádanou trojicí prvků a, b a c rozumíme uspořádanou dvojici [a, b, c] = a, [b, c] . Obdobně uspořádanou čtveřicí prvků a, b, c, d rozumíme uspořádanou dvojici [a, b, c, d] = a, [b, c, d] , přičemž [b, c, d] = b, [c, d] . Obecně uspořádanou n-ticí prvků a1 , a2 , . . . , an rozumíme uspořádanou dvojici [a1 , a2 , . . . , a2 ] = a1 , [a2 , . . . , an ] , kde [a2 , . . . , an ] je uspořádaná (n − 1)-tice. Vidíme, že pojem uspořádané trojice vychází z již výše zavedeného pojmu uspořádané dvojice. Vskutku: a, [b, c] je uspořádaná dvojice, prvek a je její první složka a [b, c] (sama uspořádaná dvojice!) je jejídruhá složka. Stejně tak uspořádaná čtveřice [a, b, c, d] je uspořádaná dvojice a, [b, c, d] , v jejíž druhé složce je využit dříve zavedený pojem uspořádané trojice. Poznámka 4.2. Uspořádanou trojici prvků a, b, c resp. uspořádanou n-tici prvků a , a , . . . , a jsme zavedli jako uspořádanou dvojici a, [b, c] resp. 1 2 n a , [a , . . . , a ] . Alternativně jsme ji mohli zavést jako uspořádanou dvojici n 1 2 [a, b], c resp. [a1 , . . . , an−1 ], an , což se někdy činí. — — —

Poznámka 4.3. Mohlo by se zdát, že když uspořádaná dvojice prvků a, b je zavedena jako množina {a}, {a, b} , tak obdobně uspořádanou trojici prvků a, b, c by mohlo být možné alternativně zavést jako množinu {a}, {a, b}, {a, b, c} . Není ale tomu tak. Uspořádanou trojici naznačeným způsobem není možné zavést. Lze totiž nalézt prvky a, b, c, d, e, f takové, že {a}, {a, b}, {a, b, c} = {d}, {d, e}, {d, e, f } , přičemž a 6= d nebo b 6= e nebo c 6= f . Cvičení 4.1. (Dobrovolně.) Pokuste se nalézt prvky a, b, c, d, e, f tak, aby platila rovnost {a}, {a, b}, {a, b, c} = {d}, {d, e}, {d, e, f } , ale neplatilo, že a=d

a b=e a c=f.

[Návod: Je-li b = c, může být e 6= f ?]

28

KAPITOLA 4. USPOŘÁDANÁ A NEUSPOŘÁDANÁ DVOJICE

Kapitola 5

Další operace s množinami a další predikáty teorie množin V této kapitole uvedeme celou sérii definic důležitých pojmů (operací a predikátů) teorie množin. Začneme pojmem (operací) kartézského1 součinu. Definice 5.1. (Kartézský součin.) Kartézský součin množin A a B je množina A × B = [a, b] ; a ∈ A, b ∈ B . Obecně, kartézský součin n množin A1 , A2 , . . . , An je množina A1 × A2 × · · · × An =

[a1 , a2 , . . . , an ] ; a1 ∈ A1 , a2 ∈ A2 , . . . , an ∈ An .

Jsou-li si množiny A1 , A2 , . . . , An navzájem rovny – jsou rovny nějaké společné množině A, tedy A1 = A2 = · · · = An = A – potom kartézský součin A1 × A2 × × · · · × An můžeme značit také An : A × A × · · · × A = An . | {z } n

Kartézský součin dvou množin A a B můžeme graficky znázornit následovně: 1 Slovo kartézský je odvozeno od latinského slova Cartesius, což je latinské příjmení francouzského učence Reného Descartesa. René Descartes (1596–1650), plným latinským jménem Renatus Cartesius, byl francouzský filosof, matematik, fyzik a přírodovědec. Byl také voják, na počátku 30leté války (1618–1648) byl důstojníkem francouzské armády. Jde o všeobecně významnou osobnost. Ve svojí filosofii požaduje jasnost a zřetelnost každé teze, rozčlenění složitého na jednoduché, postup od známého k neznámému a úplnost článků logické dedukce. Velký důraz klade na prověřování poznání rozumem. Mj. je autorem známého výroku „myslím, tedy jsemÿ (latinsky „cogito, ergo sumÿ). V matematice zavedl pojem funkce, proměnné veličiny a pravoúhlé (dnes pojmenované po něm jako kartézské) souřadnice. Jako první studoval geometrické křivky ve vztahu k jejich algebraickému vyjádření a stal se tak zakladatelem analytické geometrie.

29

30

KAPITOLA 5. DALŠÍ OPERACE A PREDIKÁTY

A

B

nebo

A B

Poznámka 5.1. V první kapitole jsme množiny vymezovali pomocí výčtu jejich prvků. Ve druhékapitole jsme setkali s vymezením množiny pomocí cantorov ského schématu x ; ϕ(x) , kde ϕ(x) je vhodná formule. V naposledy uvedené definici kartézského součinu se setkáváme s vymezením množiny generovnáním tak, že prvky jiné množiny (popř. jiných množin) dosazujeme do dané operace. Takto vymezené množiny zapisujeme mirimanovským2 schématem O(x) ; x ∈ A resp. resp. obecně

O(x, y) ; x ∈ A, y ∈ B

O(x1 , x2 , . . . , xn ) ; x1 ∈ A1 , x2 ∈ A2 , . . . , xn ∈ An ,

kde O je jednočetná (tj. unární) resp. dvojčetná (tj. binární) resp. n-četná (tj. n-ární) operace a A, B, A1 , A2 , . . . , An jsou množiny. V prvním případě jde o množinu obrazů operace O aplikované na množinu A. Obdobně ve druhém resp. třetím případě jde o množinu prvků získaných tak, že do operace O dosadíme všechny možné prvky množin A a B resp. množin A1 , A2 , . . . , An . Ve výše uvedené definici kartézského součinu A× ×B = [a, b]; a ∈ A, b ∈ B je operace O určena předpisem O(a, b) = [a, b] = {a}, {a, b} pro libovolné dva prvky a a b. Operace O tedy ze dvou prvků a, b vytvoří uspořádanou dvojici [a, b]. V obecné definici A × A × · · · × A = [a1 , a2 , . . . , an ] ; a1 ∈ 1 2 n ∈ A1 , a2 ∈ A2 , . . . , an ∈ An je operace O dána předpisem O(a1 , a2 , . . . , an ) = = [a1 , a2 , . . . , an ] pro libovolné prvky a1 , a2 , . . . , an . Poznamenejme, možná překvapivě, že mirimanovské schéma lze převést na cantorovské schéma. Například množina O(x) ; x ∈ A je totožná s množinou

y ; ∃x ∈ A: y = O(x) . Formule ϕ(y) ze schématu y ; ϕ(y) , kde jsme jen přejmenovali proměnnou x na y, je zde ∃x ∈ A: y = O(x) . V případě vícečetné operace O bychom postupovali zcela obdobně. Poznámka 5.2. Z definice uspořádané trojice [a, b, c] = a, [b, c] plyne, že kartézský součin tří množin A, B, C je množina A × B × C = a, b, c ; a ∈ A, b ∈ B, c ∈ C = = a, [b, c] ; a ∈ A, b ∈ B, c ∈ C . 2 Mirimanov – ruský emigrant – své výsledky publikoval už v roce 1917. Jeho práce však byly tehdy úplně zapomenuty.

31 Vždy tedy platí rovnost A × B × C = A × (B × C), přičemž obecně platí A × (B × C) 6= (A × B) × C . Vidíme, že kartézský součin není asociativní. Obdobnou poznámku by bylo možné napsat i pro kartézský součin čtyř nebo více množin. Cvičení 5.1. Dokažte, že pro libovolné čtyři množiny A, B, C, D platí následující vztahy: 1. (A ∪ B) × (C ∪ D) = (A × C) ∪ (A × D) ∪ (B × C) ∪ (B × D) , 2. (A ∩ B) × (C ∩ D) = (A × C) ∩ (A × D) ∩ (B × C) ∩ (B × D) . Poznámka 5.3. Některé další vztahy lze nalézt v dodatku B těchto skript. Jako další zavedeme pojem (predikát) relace. Definice 5.2. (Relace.) Množina A je relace a píšeme Rel(A) právě tehdy, když všechny její prvky jsou uspořádané dvojice. To je právě tehdy, když ∀z ∈ A ∃x, y: z = [x, y] . Poznámka 5.4. Ekvivalentně lze říci, že množina A je relace, Rel(A), právě tehdy, když ∃Y, X: A ⊆ Y × X . Vyjádřeno slovy, existují dvě množiny Y a X takové, že A je podmnožinou kartézského součinu Y × X. To lze graficky načrtnout následovně: Y

A X

Poznámka 5.5. Relace obvykle značíme písmeny R, S apod. Jde-li o relace uspořádání, k jejich označení používáme také znaky ≤, < apod. Jestliže R je relace a x a y jsou dva prvky takové, že [x, y] ∈ R, píšeme rovněž xRy. Jinými slovy zápis xRy je zkratka za [x, y] ∈ R . Ostatně jsme již dávno zvyklí psát např. 3 ≤ 7, 2 < 5 atd. Poznámka 5.6. Relace modeluje vztah mezi prvky pomocí prostředků teorie množin: z dvojic prvků, mezi nimiž platí studovaný vztah, se vytvoří uspořádané dvojice; z těchto uspořádaných dvojic se pak vytvoří množina (relace). Možná by bylo užitečné zmínit, jaký je mezi relací a predikátem rozdíl. Predikáty popisují vlastnosti všech množin (a prvků), tj. vlastnosti všech individuí Universa teorie množin. Kdežto relace A je sama množinou, a tedy jedním z individuí Universa teorie množin. Kromě toho relace A dokáže popsat vztah jen mezi některými prvky resp. individui Universa teorie množin: popisuje vztah

32


pouze mezi těmi prvky, které jsou součástí uspořádaných dvojic, z nichž daná relace sestává. Zopakujme, že ve výše uvedené definici jsme zavedli unární predikát Rel(A) – množina A je množinou uspořádaných dvojic. Obdobně bychom mohli zavést také unární predikát Rel3 (A) – množina A je množinou uspořádaných trojic. Apod. Nyní zavedeme operaci skládání množin resp. relací. Definice 5.3. (Skládání množin resp. relací.) Složením množin resp. relací R a S rozumíme množinu R ◦ S = [x, z] ; ∃y: [x, y] ∈ R ∧ [y, z] ∈ S . Jinými slovy lze říci, že prvky x a z jsou ve složené relaci R ◦ S, tedy x(R ◦ S)z, právě tehdy, když existuje „přechodovýÿ prvek y takový, že xRy a ySz. Mějme nyní dvě funkce F a G. Zvolme prvek x z definičního oboru funkce G a spočítejme y = G(x). Předpokládejme, že prvek y leží v definičním oboru funkce F , takže můžeme spočítat z = F (y) = F G(x) . Je-li možné tyto výpočty provést pro každý prvek x definičního oboru funkce G, dostáváme funkci složenou – funkci složenou z funkce F (jakožto vnější funkce) a z funkce G (jakožto vnitřní funkce). Čtenář je už jistě ze střední školy nebo i odjinud obeznámen se vztahem (F ◦ G)(x) = F G(x) , (∗) který je „definicíÿ složené funkce. Po této úvaze přikročíme k zavedení pojmu (predikátu) funkce. Zavedeme také operace definičního oboru3 a oboru hodnot. Jejich označení vychází z anglických názvů, které rovněž uvádíme. K zavedeným pojmům pak uvedeme několik poznámek. Definice 5.4. (Funkce.) Množina A je funkce a píšeme Fnc(A) právě tehdy, když Rel(A) ∧ ∀x, y, z: [y, x] ∈ A ∧ [z, x] ∈ A ⇒ y = z . Definice 5.5. (Definiční obor – domain.) Definičním oborem množiny resp. funkce A rozumíme množinu Dom(A) = { x ; ∃y: [y, x] ∈ A } . Definice 5.6. (Obor hodnot – range.) Oborem hodnot množiny resp. funkce A rozumíme množinu Rng(A) = { y ; ∃x: [y, x] ∈ A } . Poznámka 5.7. Slovy můžeme říci, že množina A je funkce právě tehdy, když ke každému prvku x z jejího definičního oboru Dom(A) existuje právě jeden prvek y z jejího oboru hodnot Rng(A) takový, že [y, x] ∈ A. Vskutku: kdyby 3 Termín „oborÿ má tak trochu historický nádech. Dříve se totiž používal namísto termínu „množinaÿ. Ostatně ještě dnes se můžeme setkat se slovními obraty „řešte rovnici v oboru reálných číselÿ, „pracujeme v komplexním oboruÿ apod.

33 existovaly dva takové prvky y a z, aby platilo [y, x] ∈ A a [z, x] ∈ A, potom oba tyto prvky už se rovnají, y = z. Poslední tři definice znázorníme pomocí následujícího obrázku – na kterém je načrtnuta funkce A, její definiční obor Dom(A) i obor hodnot Rng(A), navíc jsou zakresleny také souřadnice jednoho jejího bodu [y, x] ∈ A: Y A Rng(A) [y,x] y ( ( x Dom(A)

X

Poznámka 5.8. Funkce obvykle značíme písmeny F , G, H apod. Je-li Fnc(F ), potom ke každému x ∈ Dom(F ) existuje právě jeden prvek y takový, že [y, x] ∈ ∈ F neboli yF x. Tento jednoznačně určený prvek y značíme F (x); platí tedy rovnost y = F (x) . Poznamenejme, že zápis yF x můžeme použít, protože funkce F je současně relace. Často se také používá zápis F : A → B, který vyjadřuje, že F je funkce s definičním oborem A a oborem hodnot v množině B. To znamená, že zápis

F:A → B

je zkratka za Fnc(F ) ∧ Dom(F ) = A ∧ Rng(F ) ⊆ B .

Slovy říkáme, že funkce F zobrazuje množinu A do množiny B. Platí-li navíc, že Rng(F ) = B, potom říkáme, že funkce F zobrazuje množinu A na množinu B. (Zde je důležité si povšimnout použití předložek do a na.) Poznámka 5.9. Čtenář se jistě ptá, proč je definiční obor funkce tvořen druhými složkami uspořádaných dvojic, zatímco obor hodnot je tvořen prvními složkami těchto dvojic. Jen zdánlivě by bylo „přirozenějšíÿ provést tuto volbu obráceně. Naše rozhodnutí však plyne uspořádané trojice (resp. n-tice). Na z definice příklad uspořádaná trojice z, [x, y] může vyjadřovat, že nějaká funkce dvou proměnných v bodě [x, y] nabývá hodnoty z. Další důvod vychází z definice skládání (množin resp. relací resp. funkcí). Jak jsme již výše uvedli, složenou funkci „definujemeÿ vztahem (F ◦ G)(x) = = F G(x) , tj., (F ◦ G)(x) = F (y), kde y = G(x). Podle definice skládání ovšem pro dva prvky z a x platí [z, x] ∈ F ◦ G právě tehdy, když existuje prvek y takový, že [z, y] ∈ F a [y, x] ∈ G. Vidíme, že je naopak velice přirozené, aby obraz prvku (funkční hodnota y = G(x), obor hodnot) byl první složkou uspořádané dvojice a vzor (definiční obor) byl až druhou složkou uspořádané dvojice. Pokud bychom chtěli, aby obor hodnot byl druhou a definiční obor první složkou uspořádané dvojice, museli bychom (kromě způsobu zavedení uspořádané n-tice) pozměnit definici operace skládání funkcí, totiž vztah (∗) – pro dvě funkce F a G takové, že Rng(F ) ⊆ Dom(G) bychom definovali (F ◦ G)(x) = G F (x) . Poznámka 5.10. Funkce modeluje pojem zobrazení (a operace) pomocí prostředků teorie množin: ze vzorů a jejich obrazů vytvoříme uspořádané dvojice; z nich pak utvoříme množinu (funkci).

34


Objasněme, jaký je rozdíl mezi operací a funkcí. V těchto skriptech jsme zavedli a ještě zavedeme několik (množinových) operací. (Například sjednocení ∪, průnik ∩, skládání ◦ apod. jsou binární operace. Jako unární operace jsme si zatím uvedli definiční obor Dom a obor hodnot Rng, níže zavedeme inverzi −1 .) Pro operace tohoto druhu je typické, že jsou definovány pro každé individuum Universa teorie množin, tj., lze do nich dosadit libovolné množiny. Avšak funkce F je sama množinou, tedy individuem Universa teorie množin. Druhý rozdíl spočívá v tom, že funkce F dokáže přiřadit obraz pouze některým prvkům resp. individuím Universa teorie množin: může jej přiřadit pouze těm prvkům, které leží v jejím definičním oboru Dom(F ). Nyní zaveďme pojem (operaci) inverze. Definice 5.7. (Inverze množiny resp. relace resp. funkce.) Inverzí množiny resp. relace resp. funkce A rozumíme množinu A−1 = [x, y] ; [y, x] ∈ A . Složky uspořádaných dvojic, které byly v množině A, jsou zaměněny. Čtenář své dosavadní znalosti může vyzkoušet na následujícím tvrzení, které je velice lehké a shrnuje základní vlastnosti, jež bezprostředně plynou z dosud uvedených definic. Tvrzení 5.1. Nechť A je libovolná množina. Potom platí: 1. Rel(A) ⇐⇒ A ⊆ Rng(A) × Dom(A) , 2. Rel(A) ⇐⇒ A = (A−1 )−1 , 3. Rel(A−1 ) . Slovy první tvrzení říká, že množina A je relací právě tehdy, když je podmnožinou kartézského součinu Rng(A) × Dom(A), což podle druhého tvrzení nastává právě tehdy, když A = (A−1 )−1 . Podle třetího tvrzení, ať už množina A je zvolena jakkoliv, množina A−1 je vždy relace. Cvičení 5.2. Pokuste se odůvodnit platnost uvedených tvrzení. Z naposledy uvedeného tvrzení vyplývá, že inverze F −1 funkce F je vždy relace. Není však zaručeno, že inverze funkce je opět funkcí. Tak se dostáváme k pojmu (predikátu) vzájemně jednoznačné funkce. Definice 5.8. (Vzájemně jednoznačná funkce.) Funkce F je vzájemně jednoznačná a píšeme Fnc−1 (F ) právě tehdy, když Fnc(F ) ∧ Fnc(F −1 ) . Poznámka 5.11. Vzájemně jednoznačné funkce se nazývají také invertibilní – lze je invertovat, tzn., že jejich inverze je také funkce.

35 Zavádíme rovněž pojem prosté funkce. Říkáme, že funkce F je prostá právě tehdy, když Fnc(F ) ∧ ∀x, y ∈ Dom(F ): x 6= y ⇒ F (x) 6= F (y) . Není těžké nahlédnout, že funkce F je prostá právě tehdy, když je vzájemně jednoznačná. Cvičení 5.3. (Dobrovolně.) Pokuste se odůvodnit platnost následujících dvou tvrzení: 1. Funkce F je prostá právě tehdy, když je vzájemně jednoznačná. 2. Jestliže funkce F : A → B zobrazuje množinu A na množinu B a je prostá, potom k ní inverzní funkce F −1 : B → A zobrazuje množinu B na množinu A a je rovněž prostá. Poznámka 5.12. Pro větší názornost uveďme několik obrázků. Nejprve nakreslíme obrázek relace R a k ní opačné relace R−1 . R−1

Y X

R

X

Y

Následující obrázky ukazují inverzi funkce F , která není vzájemně jednoznačná (resp. prostá). Výsledkem je relace F −1 , která není funkcí. F −1 X L Y

Y a F X

Nyní ukážeme inverzi prosté (tj. vzájemně jednoznačné) funkce F . Výsledek F −1 je funkce – funkce inverzní k F . Y

X

( F ( X

F −1

Y — — —

Závěrem této kapitoly se podíváme na dva pojmy (operace), kterými jsou zúžení a obraz množiny. Definice 5.9. (Zúžení množiny resp. relace resp. funkce.) Zúžením množiny resp. relace resp. funkce F na množinu A rozumíme F A = z ∈ F ; ∃y, x: z = [y, x] ∧ x ∈ A

36


neboli, přehledněji zapsáno, F A=

[y, x] ∈ F ; x ∈ A .

Zúžení množiny F na množinu A je tedy množina všech uspořádaných dvojic, které patří do množiny F a současně jejich druhá složka patří do množiny A. Graficky lze zúžení množiny F na množinu A znázornit následujícím obrázkem – na kterém je vyznačen také jeden z bodů splňujících podmínku [y, x] ∈ F a x ∈ A, tudíž i [y, x] ∈ F A: Y F F A ( ( [y,x] x A

X

Zavedená operace zúžení se kromě zde uvedeného zápisu F A značí také F | A nebo F |A . Namísto zúžení lze říkat také parcializace. Jestliže F je funkce, Fnc(F ), potom F A je zúžená (parciální) funkce, která vznikla zúžením (omezením, restrikcí) definičního oboru Dom(F ) zadané funkce F na množinu A. Čtenář se může pokusit o nahlédnutí platnosti následujícího tvrzení. Tvrzení 5.2. Pro každé dvě množiny F a A platí vztah F A = F ∩ Rng(F ) × A . Cvičení 5.4. (Dobrovolně.) Nahlédněte platnost uvedeného tvrzení. Případně jej dokažte formálně. Definice 5.10. (Obraz množiny.) Obrazem množiny A přes množinu resp. relaci resp. funkci F rozumíme F 00 A = y ; ∃x ∈ A: [y, x] ∈ F . Volněji můžeme slovy říci, že jednotlivé prvky x množiny A „vstupujíÿ do množiny F , kde si „najdouÿ odpovídající uspořádanou dvojici [y, x] a vystupují jako prvky y, které tvoří obraz F 00 A. To lze graficky znázornit následujícím obrázkem – kde je vyznačen i jeden z bodů splňujících podmínku [y, x] ∈ F a x ∈ A, takže y ∈ F 00 A: Y F [y,x] F 00A y ( ( x A

X

Jestliže F je funkce, Fnc(F ), potom zde zavedený obraz F 00 A množiny A přes funkci F se často značí také F (A) popřípadě též F [A]. Čtenáři přenechávám k nahlédnutí následující snadné tvrzení. Tvrzení 5.3. Pro každé dvě množiny F a A platí vztah F 00 A = Rng(F A) .

37 Cvičení 5.5. (Dobrovolně.) Jako v předcházejícím případě, pokuste se nahlédnout platnost uvedného tvrzení. Případně jej dokažte formálně. Poznámka 5.13. (Obraz prvku a obraz a vzor množiny.) Nechť množina F je funkce, Fnc(F ). Již víme, že ke každému prvku x ∈ Dom(F ) existuje právě jeden prvek y takový, že [y, x] ∈ F . Tento jednoznačně určený prvek nazýváme obrazem prvku x (daným funkcí F ) a značíme jej F (x), jak už jsme uvedli. Jestliže A je libovolná množina, potom její obraz přes funkci F značíme také F (A) nebo F [A]. Není těžké si uvědomit, že F 00 A = F (A) = y ; ∃x ∈ A: [y, x] ∈ F , tj. obraz množiny A přes funkci F , je roven F (A) = F (x) ; x ∈ A . Rovněž už víme, že inverze F −1 funkce F obecně není funkcí. (Inverze F −1 je funkcí právě tehdy, když funkce F je vzájemně jednoznačná resp. prostá.) Přesto však, když A je libovolná množina, můžeme určit její obraz F −10000A přes množinu-relaci F −1 . Tento obraz F −1 00A, pokud F je funkce, opět značíme F −1 (A) popř. F −1 [A] a nazýváme jej vzorem množiny A (daným funkcí F ). Graficky lze vzor množiny vyjádřit následovně – vzhledem k tomu, že funkce F na obrázku není prostá, a vzhledem k volbě množiny A, její vzor F −1 (A) je jakoby „rozdělenÿ na dvě části: Y F A ( a( F −1 (A)

X

— — —

Cvičení 5.6. Najdětě příklad tří množin A, B, C, pro které platí nerovnost A × (B × C) 6= (A × B) × C . Cvičení 5.7. (Dobrovolně.) Může rovnost A × (B × C) = (A × B) × C někdy platit? Dokážete najít takový příklad tří množin A, B, C, pro které uvedená rovnost platí? Následující cvičení je sice dobrovolné, přesto však čtenáře prosím, aby se na něj alespoň podíval. Cvičení 5.8. (Dobrovolně.) Nechť A a B jsou libovolné dvě množiny. Potom platí: 1. Rel(A × B) , 2. Rel(A ◦ B) , 3. Rel(A−1 ) , 4. Rel(A B) .

38


Dokažte (resp. nahlédněte) platnost uvedených tvrzení. Cvičení 5.9. (Dobrovolně.) Nahlédněte, že když A je libovolná množina, potom platí: 1. Dom(A) = Rng(A−1 ) , 2. Rng(A) = Dom(A−1 ) . Případně uvedené rovnosti dokažte formálně. — — — Následuje několik příkladů k procvičení operací s množinami probraných v této kapitole. Cvičení 5.10. Jsou dány množiny A = {α, β, γ} a B = {a, b, c}, kde α, β, γ a a, b, c jsou navzájem různé prvky. Co je kartézským součinem A × B ? Cvičení 5.11. Co je 1. inverzí A−1 , 2. definičním oborem Dom(A), 3. oborem hodnot Rng(A) množiny A, když (a) A = [α, a], [α, b], [α, c], d, e , (b) A = [α, a], [α, b], [β, a], d, e , (c) A = [α, a], [β, a], [γ, c], a, b , (d) A = [α, b], [β, a], [γ, c], β, γ ? Zde α, β, γ a a, b, c jsou navzájem různé prvky. Dále předpokládáme, že žádný z prvků a, b, d, e, β, γ není uspořádanou dvojicí, tj., neexistují žádné prvky x a y pro které by platilo a = [x, y] nebo b = [x, y] nebo d = [x, y] nebo e = [x, y] nebo β = [x, y] nebo γ = [x, y]. Cvičení 5.12. Co je 1. zúžením F A množiny F na množinu A, 2. obrazem F 00 A množiny A přes množinu F , jestliže (a) F = [α, a], [β, b], [γ, c] , A = {a, b}, (b) F = [α, a], [β, b], [γ, c] , A = {b, c, d, e},

39 (c) F = [γ, c], [δ, d], [ε, e] , A = {b, c, d, e} ? Cvičení 5.13. Co je výsledkem složení R ◦ S dvou množin (a) R = [α, a], [α, b], [α, c], [α, d], [β, b], [β, c], [β, d], [γ, c], [γ, d], [δ, d] , S = [a, A], [a, B], [a, C], [b, B], [b, C], [c, C] , (b) R = [α, a], [α, b], [α, c], [β, b], [β, c], [γ, c] , S = [a, A], [b, A], [b, B], [c, A], [c, B], [c, C], [d, A], [d, B], [d, D] , (c) R = [α, a], [β, a], [β, b], [γ, a], [γ, b], [γ, c] , S = [a, A], [b, A], [b, B], [c, A], [c, B], [c, C] ? — — — Na závěr uvádím ještě několik teoretických cvičení. Mezi nimi si zaslouží pozornost zejména vztahy ze cvičení 5.15. a 5.17. a z poznámky 5.14. Cvičení 5.14. (Dobrovolně.) Nechť R a S jsou dvě množiny. Je vcelku jasné, že platí inkluze Rng(R ◦ S) ⊆ Rng(R) a Dom(R ◦ S) ⊆ Dom(S). Rozmyslete si však, že 1. jestliže Dom(R) ⊆ Rng(S), potom Rng(R ◦ S) = Rng(R), 2. jestliže Rng(S) ⊆ Dom(R), potom Dom(R ◦ S) = Dom(S). Cvičení 5.15. (Dobrovolně.) Ukažte, že pro libovolné množiny R, S, T platí 1. (R ◦ S)−1 = S −1 ◦ R−1 , 2. (R ◦ S) ◦ T = R ◦ (S ◦ T ). Povšimněte si, že v prvním vztahu dochází „k záměně pořadíÿ množin resp. relací R a S ! Cvičení 5.16. (Dobrovolně.) Nechť F , A, B jsou libovolné množiny. Rozmyslete si, že platí 1. F 00 (A ∪ B) = (F 00 A) ∪ (F 00 B), 2. F 00 (A ∩ B) ⊆ (F 00 A) ∩ (F 00 B), 3. F 00 (A \ B) ⊇ (F 00 A) \ (F 00 B). Poznámka 5.14. Z předchozího cvičení plyne, že pro libovolnou funkci F , tedy Fnc(F ), a libovolné dvě množiny A a B platí vztahy 1. F (A ∪ B) = F (A) ∪ F (B), 2. F (A ∩ B) ⊆ F (A) ∩ F (B), 3. F (A \ B) ⊇ F (A) \ F (B).

40


Nakreslete si obrázky a rozmyslete si, za jakých okolností ve druhém a třetím vztahu nastane rovnost a kdy jsou inkluze ostré. (Jestliže funkce F je prostá, Fnc−1 (F ), potom ve druhém a třetím vztahu platí rovnosti.) Cvičení 5.17. (Dobrovolně.) Nechť F je funkce, Fnc(F ). Nahlédněte, že pak pro každé dvě množiny A a B platí vztahy 1. F −1 (A ∪ B) = F −1 (A) ∪ F −1 (B), 2. F −1 (A ∩ B) = F −1 (A) ∩ F −1 (B), 3. F −1 (A \ B) = F −1 (A) \ F −1 (B). Nakreslete si obrázky.

Kapitola 6

Další pojmy: kartézský součin a projekce, množina zobrazení mezi dvěma množinami, poznámka k potenční množině V této kapitole uvedeme několik doplňujících pojmů a poznámek. — — — Mějme dvě množiny A a B. Čtenáři již je dobře znám pojem kartézského součinu A × B. Kdykoliv ale pracujeme s kartézským součinem A × B, můžeme pracovat také se dvěma zobrazeními, která se nazývají projekce a která si nyní uvedeme. Zaveďme zobrazení pA : A × B → A předpisem pA : [a, b] 7→ a pro každé [a, b] ∈ A × B. Právě zavedenému zobrazení pA říkáme projekce (množiny A × B) na množinu A. Obdobně zavádíme zobrazení pB : A × B → B předpisem pB : [a, b] 7→ b pro všechna [a, b] ∈ A × B. Nyní zavedenému zobrazení pB říkáme projekce (množiny A × B) na množinu B. Poznámka 6.1. Čtenář se patrně ještě nesetkal se šipkou 7→. Její význam proto nyní objasním. Zápis pA : [a, b] 7→ a čteme: zobrazení pA uspořádané dvojici [a, b] 41

42

KAPITOLA 6. DALŠÍ POJMY. . .

přiřadí prvek a, tj. její první složku. Obdobně zápis pB : [a, b] 7→ b vyjadřuje, že zobrazení pB uspořádané dvojici [a, b] přiřadí prvek b, tedy její druhou složku. Obecně, máme-li zobrazení neboli funkci F : X → Y , pak zápis F : x 7→ y vyjadřuje přesně to, že F (x) = y. Uveďme ještě výslovně, co z výše uvedeného textu snad vyplynulo: O funkcích (tj. o množinách splňujících predikát Fnc zavedený v předcházející kapitole) často hovoříme jako o zobrazeních. Jestliže tedy F je funkce, Fnc(F ), pak o F můžeme hovořit jako o zobrazení. Čtenář se praxí sám naučí, kdy je vhodné používat pojem „funkceÿ a kdy je vhodné použít pojem „zobrazeníÿ. Obecně lze říci, že pojem funkce používáme výhradně v oblasti matematické analýzy pro zobrazení, jejichž definiční obor i obor hodnot leží v množině reálných čísel nebo uspořádaných n-tic reálných popř. komplexních čísel. Navíc pojem funkce používáme v oblasti teorie množin, když hovoříme o množinách, které jsou funkcemi, tj. o množinách splňujících predikát Fnc. V ostatních případech používáme pojem zobrazení. Poznámka 6.2. Samozřejmě, že zavedené projekce pA a pB jsou množiny jako každé jiné. V případě projekce pA máme o n a, [a, b] ; a ∈ A, b ∈ B . pA = Cvičení 6.1. Jak vypadá množina všech uspořádaných dvojic (resp. trojic) projekce pB ? Graficky můžeme pojem projekce znázornit pomocí následujícího obrázku: B b

pB

[b,a] pA

?

a

A

Poznámka 6.3. Máme-li kartézský součin A1 × A2 × · · · × An obecně n množin A1 , A2 , . . . , An , lze zavést projekce pA1 , pA2 , . . . , pAn předpisem pAi : [a1 , a2 , . . . . . . , an ] 7→ ai pro i = 1, 2, . . . , n. — — — Nyní se podíváme na množinu všech zobrazení mezi dvěma množinami. Budiž dány dvě množiny A a B. Pak můžeme sestavit také množinu { F ; F : A → B }, což je množina všech zobrazení s definičním oborem A a oborem hodnot v množině B. Uvedenou množinu značíme B A nebo (A → B).1 Platí tedy rovnost B A = (A → B) = { F ; F : A → B } neboli (A → B) = B A =

F ⊆ B × A ; Fnc(F ) ∧ Dom(F ) = A .

(∗)

Cvičení 6.2. Podívejte se na uvedený vztah (∗) a nahlédněte, že když F ∈ ∈ (A → B) = B A , potom Rng(F ) ⊆ B.

43 Cvičení 6.3. 1. Nechť A = {a, b} a B = {x, y, z}. (Předpokládejme, že prvky a, b a x, y, z jsou navzájem různé.) Kolik má množina B A = (A → B) prvků? 2. Nechť množina A má m prvků, nechť množina B má n prvků. (Zde m a n jsou dvě (konečná) nezáporná přirozená čísla. Můžeme mít například A = = {1, 2, . . . , m} a B = {1, 2, . . . , n}.) Kolik má množina B A = (A → B) prvků?

— — — Nakonec se vrátíme k potenční množině. Nechť A je množina. Jak už víme, její potenční množina P(A) = { X ; X ⊆ A } je množinou všech jejích podmnožin. Zvolme jednu takovou podmnožinu X ⊆ A libovolně. Nic nám nebrání této podmnožině X přiřadit zobrazení FX : A → {0, 1} určené následujícím předpisem pro libovolný prvek a ∈ A: 0 , jestliže a ∈ / X, FX (a) = 1 , jestliže a ∈ X . Čtenář si může rozmyslet, že pojímáme-li obor hodnot jako první a definiční obor jako druhou složku uspořádané dvojice, pak FX = {0} × (A \ X) ∪ {1} × X . Zavedené zobrazení FX nazýváme charakteristickou funkcí množiny X. Navíc je zřejmé, že charakteristická funkce FX je každé podmnožině X ⊆ A přiřazena jednoznačně: jsou-li X1 , X2 ⊆ A dvě různé podmnožiny, potom FX1 6= FX2 . Uvedeným postupem jsme každé podmnožině X ⊆ A přiřadili určité zobrazení FX : A → {0, 1}. Lze však postupovat i obráceným směrem: jestliže máme nějaké zobrazení F : A → {0, 1}, pak mu přiřadíme množinu XF = a ∈ A ; F (a) = 1 . Opět platí, že když F1 , F2 : A → {0, 1} jsou dvě různé funkce, potom přiřazené množiny XF1 a XF2 jsou také různé. Snadno též nahlédneme, že vycházíme-li z podmnožiny X ⊆ A, přiřadíme jí funkci FX , které zpátky přiřadíme množinu XFX , dostáváme původní množinu X, tedy X = XFX . Obdobně, vycházíme-li z funkce F : A → {0, 1}, které přiřadíme množinu XF a zpátky zobrazení FXF , dospíváme opět k původní funkci F , tedy F = FXF . Tímto dospíváme k závěru, že mezi potenční množinou P(A) zadané množiny A a množinou {0, 1}A všech zobrazení definovaných na množině A s oborem hodnot v množině {0, 1}, je vzájemně jednoznačný vztah. Tj., množiny X ∈ P(A) a zobrazení F ∈ {0, 1}A si vzájemně odpovídají. Připomeňme, že potenční množina P(A) se někdy značí také 2A . V podstatě tedy stejně jako množina {0, 1}A všech zobrazení s definičním oborem A a oborem hodnot v {0, 1}. Platí totiž 2 = {0, 1}, jak z následující poznámky vyplyne.

44


Poznámka 6.4. (Přirozená čísla.) V teorii množin se zavádí přirozená čísla následujícím postupem, který pochází od Johna von Neumanna2 : Přirozené číslo nula 0 je prázdná množina ∅. Přirozené číslo jedna 1 je množina obsahující prázdnou množinu, tj. nulu. Přirozené číslo dvě 2 je množina obsahující čísla nula a jedna. Obecně, nenulovým přirozeným číslem rozumíme množinu obsahující všechna předcházející přirozená čísla. (Přičemž výchozím přirozeným číslem, nulou, je prázdná množina.) Stručně řečeno, máme 0 = {} = ∅ , 1 = {0} = {∅} , 2 = {0, 1} = ∅, {∅} , 3 = {0, 1, 2} = ∅, {∅}, ∅, {∅} , .. . Pozorný čtenář si jistě všimne, že kromě vztahu 2 ∈ 3 platí také např. 2 ⊂ 3. Obecně platí, že libovolná dvě od sebe různá přirozená čísla m a n splňují vztah m < n právě tehdy, když m ∈ n, a to nastává právě tehdy, když m ⊂ ⊂ n. Tedy m ≤ n právě tehdy, když m ⊆ n. Uvádět přesnou definici množiny přirozených čísel by bylo nad rámec těchto skript, proto se spokojíme pouze s výše naznačenou stručnou zmínkou o přirozených číslech. Ať už však potenční množinu množiny A značíme P(A) nebo 2A , vždy je třeba mít na paměti, že potenční množina P(A) a množina zobrazení {0, 1}A jsou dvě odlišné množiny – množina X ⊆ A je jedna věc a její charakteristitcká funkce F : A → {0, 1} je jiná věc. Cvičení 6.4. Je dána množina A = {a, b, c, d}, kde a, b, c, d jsou čtyři navzájem různé prvky. 1. Napište charakteristickou funkci F : A → {0, 1} množiny X = {a, c, d}. 1. Která podmnožina X ⊆ A je určena charakteristickou funkcí F = [1, a], [0, b], [1, c], [0, d] ? — — — Touto kapitolou končí jedno ucelené téma, ve kterém jsme budovali základy teorie množin. (Tyto základy jsme budovali spíše intuitivním způsobem. Solidní, axiomatickou výstavbu teorie množin v těchto skriptech nebylo možné uvést, neboť by došlo k překročení rámce těchto skript.) Zmíněné téma zakončíme korespondenčním úkolem. Cvičení 6.5. (První korespondenční úkol.) Tento korespondenční úkol se1 Místo

označení (A → B) by možná bylo vhodnější používat označení {A → B}. von Neumann (1903–1957) – slavný americký matematik. Zabýval se funkcionální analýzou, matematickou logikou, matematickou fyzikou a teorií topologických grup. Věnoval se rovněž teorii pravděpodobnosti, matematickým metodám v ekonomii a numerické matematice. Spolu s Oskarem Morgensternem (1902–1977) je znám jako zakladatel teorie her. Pak se věnoval také kybernetice. John von Neumann je původem z Maďarska. Jeho otec byl velmi bohatý a titul von získal za to, že císaři půjčil peníze (resp. titul von si jednoduše koupil). Protože John von Neumann už od malička projevoval matematické nadání, jeho otec se rozhodl, že z něj vychová světového matematika. Platil mu tedy ty nejlepší učitele a vychoval z něho světoznámého matematika. 2 John

45 stává ze dvou částí. (Obě tyto části tvoří jeden, první korespondenční úkol.) 1. Ve třetí (a vlastně i v páté) kapitole byla uvedena řada vztahů, které operace s množinami splňují. Šlo například o de Morganova pravidla (tvrzení 3.1.), zákon dvojí negace (tvrzení 3.2.) apod. Uvedené vztahy jsme vždy dokazovali také formálně, s využitím axiomu exntensionality. Řada dalších vztahů je uvedena také v dodatku B těchto skript. Vašim úkolem je ze vztahů uvedených v dodatku B si jeden vztah vybrat a dokázat jej formálně. Vztah, který si vyberete, pochopitelně nesmí být dokázán v těchto skriptech (ať už jako tvrzení anebo vyřešen jako cvičení). To znamená, že v úvahu připadají vztahy 8, 10–14, 16, 160 , 18, 19 a 22 ze cvičení B.1., kterýkoliv ze vztahů ze cvičení B.2., cvičení B.4., oba vztahy ze cvičení B.5. a vztahy 3a, 3b a 4a, 4b ze cvičení B.6. Z vyjmenovaných vztahů si vyberte jeden, a ten dokažte. (Stačí jeden vztah. Není nutné řešit všechny, ani není nutné z každého cvičení vybírat jeden vztah.) 2. Jsou dány množiny F = [1, 1], [4, 2], [9, 3], [16, 4], [25, 5] , A = {3, 4, 5, 6, 7} , R = [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [3, 5] . Vyberte si jeden z následujících úkolů: 2a. určete obraz F 00 A množiny A přes funkci F , 2b. určete zúžení F A funkce F na množinu A, 2c. určete složení F ◦ R funkce F a relace R. (Opět, není nutné řešit všechny úkoly, stačí jen jeden z nich.)

46


Kapitola 7

Vlastnosti relací. Relace částečného uspořádání Čtenář již ví, že relace je množina uspořádaných dvojic. Tj., množina R je relace (Rel(R)) právě tehdy, když R obsahuje pouze uspořádané dvojice. Zavedeme pranepatrně odlišný pojem, kterým je relace na množině. Definice 7.1. (Relace na množině.) Nechť M je nějaká množina. Množina R je relace na množině M právě tehdy, když R ⊆ M × M . Poznámka 7.1. Snadno se nahlédne, že každá relace R je relací na množině M = Dom(R) ∪ Rng(R). Jaký je tedy mezi relací a relací na množině rozdíl? Vlastně jen minimální. Jestliže je napřed dána nějaká relace R, můžeme k ní dodatečně sestrojit množinu (M = Dom(R) ∪ Rng(R)), na které R je relací. V případě relací na množině je postup opačný: nejprve je dána nějaká množina M a teprve potom se zabýváme relacemi na této množině. To nám umožňuje zabývat se například jen relacemi na množině přirozených čísel N, relacemi na množině reálných čísel R apod. V této a dalších kapitolách těchto skript se budeme zabývat výhradně relacemi na nějaké předem zvolené množině M . Po tomto stručném úvodu můžeme přistoupit k zavedení pojmu částečného uspořádání. Definice 7.2. Nechť R je relace na množině M . Relace R je reflexivní právě tehdy, když ∀x ∈ M : xRx . Relace R je tranzitivní právě tehdy, když ∀x, y, z ∈ M : xRy ∧ yRz ⇒ xRz . Relace R je antisymetrická právě tehdy, když ∀x, y ∈ M : xRy ∧ yRx ⇒ x = y . Relace R, která je reflexivní, tranzitivní a antisymetrická, se nazývá relací (částečného) uspořádání.

47

48

KAPITOLA 7. RELACE ČÁSTEČNÉHO USPOŘÁDÁNÍ

Poznámka 7.2. Relaci R, která je jen reflexivní a tranzitivní, se říká kvaziuspořádání (někteří autoři používají také pojem preuspořádání). Uveďme několik příkladů částečného uspořádání. V teorii množin jako typický (a důležitý!) příklad relace částečného uspořádání slouží relace či spíše predikát inkluze „⊆ÿ. K tomu se vztahují první dva následující příklady. V algebře jako příklad relace částečného uspořádání slouží relace dělitelnosti „|ÿ, k tomu viz třetí následující příklad níže. Příklad 7.1. Nechť M je nějaký systém množin, tj. množina, jejíž prvky jsou množiny. (Populárně můžeme říci, že M je množina množin.) Pak relace inkluze „⊆ÿ je částečným uspořádáním množiny M. Opravdu: jsou-li A, B, C ∈ M libovolné množiny, potom (1) platí A ⊆ A, takže relace inkluze je reflexivní, (2) z A ⊆ B ⊆ C vyplývá A ⊆ C, což znamená, že relace inkluze je tranzitivní, a (3) jestliže A ⊆ B a B ⊆ A, potom A = B, což dokazuje, že relace inkluze je také antisymetrická. Tímto jsme ověřili všechny tři požadované vlastnosti (reflexivitu, tranzitivitu a antisymetrii), takže relace inkluze „⊆ÿ je relací částečného uspořádání na množině M. (Pro pečlivé čtenáře dodejme, že jsme se dopustili jisté nepřesnosti. Inkluze „⊆ÿ ve skutečnosti není relace, nýbrž predikát (zavedený definicí). Chceme-li tuto nepřesnost obejít, musíme výše uvedenou úvahu provést následovně: Nechť je dána množina M. Na množině M sestrojme relaci I (jako „inkluzeÿ), tj. podmnožinu kartézského součinu M × M, takto: Ať A, B ∈ M jsou dvě množiny z množiny M. Pak uspořádaná dvojice [A, B] patří do množiny I právě tehdy, když A ⊆ B. Můžeme tedy napsat, že I = [A, B] ∈ M ; A ⊆ B . A tato relace I množinu M částečně uspořádává. Jistě souhlasíte, že takto provedená úvaha je sice technicky přesná, ale spíše zamlžuje původní myšlenku. V dalším se proto budeme raději dopouštět drobné nepřesnosti v tom smyslu, že o inkluzi „⊆ÿ budeme hovořit jako o relaci, ačkoliv, jak jsme právě uvedli, ve skutečnosti jde o predikát a ne o relaci.) Příklad 7.2. Předcházející příklad trochu doplníme. Vlastně už ze druhé kapitoly víme, že potenční množinu P(A) libovolné množiny A lze částečně uspořádat inkluzí. Jde tedy o totéž jako v předcházejícím příkladě, jen pracujeme se speciální volbou množiny M: klademe M = P(A). Příklad 7.3. Uvažujme množinu všech přirozených čísel N = {1, 2, 3, . . .} a na ní uvažujme relaci dělitelnosti „|ÿ. Připomeňme, že přirozené číslo k dělí přirozené číslo n, píšeme k | n, právě tehdy, když existuje další přirozené číslo l takové, že n = lk = kl. (To znamená, že čísla k a l je nutné vzájemně vynásobit.) Formálně můžeme psát: ∀k, n ∈ N: k | n ⇔ ∃l ∈ N: n = lk . Snadno ověříme, že relace dělitelnosti „|ÿ je částečným uspořádáním množiny přirozených čísel N. Pro každá přirozená čísla a, b, c ∈ N totiž platí: (1) a | a, takže relace „|ÿ je reflexivní, (2) jestliže a | b a b | c, potom také a | c, což

49 znamená tranzitivitu, a (3) jestliže a | b a současně b | a, potom nutně a = b, takže relace „|ÿ je také antisymetrická. Tím jsme ověřili, že relace dělitelnosti „|ÿ je relací částečného uspořádání na množině N. (Poznamenejme, že v algebře je možné obdobným způsobem zkoumat také dělitelnost v monoidech. (Monoid je množina, na které je dána jedna binární asociativní operace; v množině navíc musí existovat konstanta, která je vůči dané binární operaci neutrálním prvkem.) Je výhodné pracovat s komutativními monoidy (daná operace musí být komutativní), protože jinak bychom museli zvlášť vyšetřovat dělitelnost zleva a dělitelnost zprava. (Jako příklad komutativního monoidu může posloužit právě výše uvažovaná množina přirozených čísel N s operací obyčejného násobení přirozených čísel a s konstantou 1, tj. přirozeným číslem jedna.) Získaná relace dělitelnosti na komutativním monoidu je v obecném případě pouze kvaziuspořádáním. Relace dělitelnosti je na komutativním monoidu relací částečného uspořádání právě tehdy, když daný monoid kromě neutrálního prvku už neobsahuje žádné další invertibilní prvky. Čtenář nemusí být smutný, pokud této doplňující poznámce neporozuměl, protože k jejímu pochopení už je třeba mít jisté znalosti algebry – přinejmenším znalost všech použitých pojmů. Avšak výše uvedený příklad dělitelnosti na množině přirozených čísel N by měl být srozumitelný každému.) Částečně uspořádané množiny můžeme znázornit pomocí tzv. Hasseových diagramů. Je-li dána nějaká částečně uspořádaná množina (M, ≤), postupujeme při jejím znázornění podle následujících pravidel: Každý prvek x ∈ M nakreslíme jako bod. Jestliže pro nějaké dva různé prvky x, y ∈ M platí vztah x ≤ y, bod odpovídající prvku y kreslíme výše než bod odpovídající prvku x. Jestliže pro dva různé prvky x, y ∈ M platí vztah x ≤ y a navíc neexistuje žádný prvek z ∈ M takový, aby x < z < y, potom body odpovídající prvkům x a y spojíme úsečkou. (Poslední pravidlo zaručuje, že když pro dva prvky x, y ∈ M platí x ≤ y, potom z bodu odpovídajícího prvku x „vede cestička vzhůruÿ k bodu odpovídajícímu prvku y.) Připomeňme, že Hasseovy diagramy potenčních množin částečně uspořádaných inkluzí jsme kreslili už ve druhé kapitole těchto skript. Nyní uvedeme další příklady Hasseových diagramů. Příklad 7.4. Na množině M = {a, b, c, d, e, f }, kde a, b, c, d, e, f jsou navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání, která splňuje následující vztahy: a ≤ b ≤ c ≤ e ≤ f a a ≤ b ≤ d ≤ e ≤ f . Pak uspořádání množiny M můžeme znázornit následujícím Hasseovým diagramem: f

e @ @ d

c @ @

b

a

50


Je jasné, že relace „≤ÿ je následující: „≤ÿ = [a, a], [a, b], [a, c], [a, d], [a, e], [a, f ], [b, b], [b, c], [b, d], [b, e], [b, f ], [c, c], [c, e], [c, f ], [d, d], [d, e], [d, f ], [e, e], [e, f ], [f, f ] . Poznámka 7.3. Povšimněte si pozorně, že v částečném uspořádání nemusejí být každé dva prvky porovnatelné! V předcházejícím příkladě jsou to prvky c a d, které nejsou vzájemně porovnatelné – neplatí ani c ≤ d ani d ≤ c. Vraťme se ještě k příkladu 2.2. Uvažujeme-li případ P {a, b} , pak množiny {a} a {b} nejsou vzájemně porovnatelné, protože neplatí ani {a} ⊆ {b} ani {a} ⊇ {b}. V případě P {a, b, c} množiny {a}, {b} a {c} nejsou vzájemně porovnatelné; ani {a, b}, {a, c} a {b, c} nejsou vzájemně porovnatelné; ani {a} a {b, c} nejsou vzájemně porovnatelné apod. V Hasseově diagramu je skutečnost, že dva prvky nejsou vzájemně porovnatelné, znázorněna tím, že tyto dva prvky nejsou žádným způsobem propojeny. Příklad 7.5. Na množině M = {a, b, c, d, e, f, g, h, i, j}, kde a, b, c, d, e, f , g, h, i, j jsou navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání splňující tyto vztahy: a ≤ b ≤ c ≤ f a a ≤ d ≤ e ≤ f a současně e ≤ f ≤ g ≤ j a e ≤ h ≤ i ≤ j. Pak uspořádání množiny M vypadá takto:

g

j " bb "

i

f h "" bb "" c e

b

d bb "" a

Cvičení 7.1. Jak vypadá relace „≤ÿ z předchozího příkladu? Cvičení 7.2. Na množině M = {a, b, c, d, e, f, g}, kde a, b, c, d, e, f , g jsou navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání splňující právě tyto vztahy: d ≤ b ≤ a a e ≤ b ≤ a a zároveň f ≤ c ≤ a a g ≤ c ≤ a. Znázorněte uspořádání množiny M pomocí Hasseova diagramu. Jak vypadá relace „≤ÿ? V souvislosti s částečným uspořádáním se často používají pojmy, které zavedeme v následující definici. Definice 7.3. Nechť (M, ≤) je částečně uspořádaná množina. (To znamená, že M je nějaká množina, na níž je dána nějaká relace částečného uspořádání, kterou jsme označili „≤ÿ. Takže „≤ÿ je podmnožinou kartézského součinu M × M a

51 splňuje vlastnosti reflexivity, tranzitivity a antisymetrie.) Dále nechť a ∈ M je jejím libovolným prvkem. Prvek a je nejmenším prvkem množiny M právě tehdy, když ∀x ∈ M : a ≤ x . Prvek a je minimálním prvkem množiny M právě tehdy, když žádný prvek x množiny M už není ostře menší než prvek a, tedy ∀x ∈ M : x ≤ a ⇒ x = a . Prvek a je maximálním prvkem množiny M právě tehdy, když žádný prvek x množiny M už není ostře větší než a, takže ∀x ∈ M : a ≤ x ⇒ a = x . Prvek a je největším prvkem množiny M právě tehdy, když ∀x ∈ M : x ≤ a . Poznámka 7.4. K definici nejmenšího a největšího prvku skoro není co dodat. Snad jen tolik, že nejmenšímu prvku říkáme také první prvek a že největšímu prvku říkáme také poslední prvek. Na definici minimálního a maximálního prvku se ale podíváme podrobněji. Čtenář nechť si promyslí, že každá z následujících formulí podává ekvivalentní definici minimálního prvku: ∀x ∈ M : ∀x ∈ M : ¬∃x ∈ M : ¬∃x ∈ M :

x 6= a ⇒ x 6≤ a , x ≤ a ⇒ x = a, x ≤ a ∧ x 6= a , x < a.

Zápis x 6≤ a v první formuli samozřejmě znamená ¬(x ≤ a). Zápis x < a ve čtvrté formuli je umožněn následující všeobecně přijímanou konvencí: pracujeme-li s relací částečného uspořádání a tato relace je označena znakem „≤ÿ, pak používaná konvence umožňuje zápis x 6= a ∧ x ≤ a napsat zkráceně x < a. V případě maximálního prvku můžeme postupovat obdobně. Každá z následujících formulí podává ekvivalentní definici maximálního prvku: ∀x ∈ M : x 6= a ⇒ x 6≥ a , ∀x ∈ M : x ≥ a ⇒ x = a , ¬∃x ∈ M : x ≥ a ∧ x 6= a , ve stručnosti @x ∈ M : x > a , což můžeme vyjádřit slovy: „neexistuje x ∈ M , které by bylo větší než aÿ. (Čtenář ať samostatně sestaví obdobné slovní vyjádření také pro případ minimálního prvku.) Ekvivalentní zápisy definice maximálního prvku byly umožněny několika samozřejmými konvencemi, na které nyní upozorníme. Zápis x ≥ a znamená

52


a ≤ x. (Na množině M máme pouze jednu relaci „≤ÿ. Nikoliv dvě (různé) relace „≥ÿ a „≤ÿ. Zápis x ≥ a je pouze syntaktická zkratka, resp. jen jiný zápis, za (snad trochu správnější) a ≤ x.) Ze zcela obdobných důvodů zápisy x 6≥ a a x > a znamenají po řadě a 6≤ x (což znamená ¬(a ≤ x)) a a < x (což znamená x 6= a ∧ x ≤ a). Již jen pro úplnost připomeňme, že negaci existenčního kvantifikátoru, tedy „neexistujeÿ, ¬∃ . . . , je možné zapsat také @ . . . Zápis ¬∃ . . . je ale z formálního hlediska správnější. Pojmy nejmenšího, minimálního, maximálního a největšího prvku nyní osvětlíme několika příklady. Příklad 7.6. Ze druhé kapitoly víme, že potenční množinu libovolné množiny lze částečně uspořádat inkluzí. Viz též příklad 7.2. Hasseovy diagramy některých potenčních množin uspořádaných inkluzí jsou uvedeny v příkladu 2.2. Máme-li libovolnou množinu A a její potenční množinu P(A) částečně uspořádáme inkluzí, potom v ní najdeme právě jeden nejmenší prvek, totiž prázdnou množinu ∅, a právě jeden největší prvek, totiž celou množinu A. Nejmenší prvek ∅ je současně minimální prvek a největší prvek A je současně maximální prvek. V příkladu 2.2. je největším prvkem množina ∅ (v případě P {} ) resp. {a} (v případěP {a} ) resp. {a, b} (v případě P {a, b} ) resp. {a, b, c} (v případě P {a, b, c} ). Nejmenším prvkem je prázdná množina ∅ (ve všech případech; tzn., že prázdná množina je v případě P {} nejmenším i největším prvkem zároveň). Příklad 7.7. Nechť A je množina obsahující alespoň dva různé prvky. Pro jednoduchost předpokládejme, že množina A je konečná. Počet prvků množiny A označme číslem n. (Víme, že n ≥ 2.) Položme M = P(A)\\{∅, A}. Systém M tedy obsahuje všechny podmnožiny množiny A s výjimkou prázdné množiny ∅ a celé množiny A. Systém M opět částečně uspořádáme inkluzí. Nyní v tomto systému nenajdeme ani jeden nejmenší a ani jeden největší prvek. (To znamená, že žádný z těchto prvků neexistuje.) Najdeme však několik, celkem n, minimálních a několik, opět n, maximálních prvků. Minimální prvky jsou všechny jednoprvkové podmnožiny množiny A. Maximální prvky jsou všechny (n − 1)-prvkové podmnožiny množiny A. Cvičení 7.3. Co by se v předcházejícím příkladu stalo, kdyby množina A byla prázdná nebo jen jednoprvková? Co se stane, když množina A bude nekonečná? Příklad 7.8. V systému množin M = {a, b}, {b, c}, {c, d}, {a, b, c}, {b, c, d} který je částečně uspořádán inkluzí, viz cvičení 2.4., máme dva maximální prvky, kterými jsou {a, b, c} a {b, c, d}, a tři minimální prvky, totiž {a, b}, {b, c}, {c, d}. V množině M není žádný nejmenší ani největší prvek. Příklad 7.9. Uvažujme množinu celých čísel Z = {. . . , −2, −1, 0, 1, 2, . . .} s klasickým uspořádáním „≤ÿ. Pak zde nenajdeme žádné minimální ani maximální prvky. (Takže není možné najít ani nejmenší nebo největší prvek – kdyby existovaly, byly by minimálními a maximálními prvky množiny Z.) Omezme se na množinu přirozených čísel N = {1, 2, 3, . . .} s klasickým uspořádáním „≤ÿ. Snadno nahlédneme, že nejmenším (a tudíž i minimálním) prvkem je číslo 1. Avšak maximální (a proto ani největší) prvek nenajdeme ani jeden.

53 Podané příklady osvětlily základní vlastnosti nejmenších, minimálních, maximálních a největších prvků. Nyní tyto vlastnosti uvedeme v podobě následujících dvou jednoduchých tvrzení. Tvrzení 7.1. Nechť (M, ≤) je částečně uspořádaná množina. Jestliže a ∈ M je nejmenším prvkem množiny M , potom a je také minimálním prvkem množiny M . Jestliže a ∈ M je největším prvkem množiny M , potom a je také maximálním prvkem množiny M . Důkaz. Dokážeme první část. Nechť a ∈ M je nejmenším prvkem množiny M . Podle definice víme, že pro každý prvek m ∈ M platí a ≤ m. Máme dokázat, že a je minimálním prvkem. Máme tedy dokázat, že když pro nějaký prvek m ∈ M platí m ≤ a, potom a = m. Předpokládejme tedy, že máme nějaký prvek m ∈ M , pro který platí m ≤ a. Současně ale víme, že také a ≤ m, viz výše. Antisymetrie dává, že a = m, což jsme měli dokázat. Druhá část tvrzení se dokáže obdobně.

Tvrzení 7.2. Nechť (M, ≤) je částečně uspořádaná množina. Potom platí, že množina M má nejvýše jeden nejmenší prvek a nejvýše jeden největší prvek. Důkaz. Opět dokážeme první část. Předpokládejme, že v množině M nalezneme dva minimální prvky a, b ∈ M . Pro každý prvek m ∈ M tedy platí a ≤ m. Současně pro každý prvek m ∈ M platí b ≤ m. Volbou prvku m = b a m = a dostáváme, že a ≤ b a b ≤ a. Antismetrie dává, že a = b. To znamená, že nejmenší prvek je nejvýše jeden. Druhá část tvrzení se dokáže obdobně.

Cvičení 7.4. Dokažte druhé části uvedených dvou tvrzení.

— — —

Cvičení 7.5. Na množině M = {a, b, c, d}, kde a, b, c, d jsou čtyři navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání splňující vztahy a ≤ b a c ≤ d. Znázorněte uspořádání množiny M pomocí Hasseova diagramu. Zapište relaci „≤ÿ jako množinu uspořádaných dvojic. Dále určete všechny nejmenší, minimální, maximální a největší prvky částečně uspořádané množiny M . Rovněž vyjmenujte všechny dvojice vzájemně neporovnatelných prvků množiny M . Cvičení 7.6. Nakreslete Hasseův diagram uspořádání množiny celých čísel Z a množiny přirozených čísel N. (Na množinách Z i N uvažujeme obvyklé uspořádání.) Určete také nejmenší, minimální, maximální a největší prvky obou množin.

54


Cvičení 7.7. (Dobrovolně.) Dokažte, že jednotlivé vlastnosti (axiomy) částečného uspořádání jsou na sobě navzájem nezávislé. Ukažte, že reflexivita nezávisí na tranzitivitě ani antisymetrii, že tranzitivita nezávisí na reflexivitě ani antisymetrii a že antisymetrie nezávisí na reflexivitě ani tranzitivitě. K tomu stačí najít příklad, resp. tři různé příklady, relace R na nějaké množině M , která 1. je tranzitivní a antisymetrická a není reflexivní, 2. je reflexivní a antisymetrická a není tranzitivní, 3. je reflexivní a tranzitivní a není antisymetrická. Cvičení 7.8. (Dobrovolně.) Nechť (M, ≤) je částečně uspořádaná množina. Na množině M definujme relaci „≤op ÿ (uspořádání opačné k uspořádání „≤ÿ) následovně: pro libovolné dva prvky x, y ∈ M platí x ≤op y právě tehdy, když y ≤ x. (Vlastně, využijeme-li operaci inverze množiny −1 , platí ≤op = ≤−1 .) Dokažte, že relace „≤op ÿ je také částečným uspořádáním množiny M . (Ověřte reflexivitu, tranzitivitu a antisymetrii. To vše je lehoučké a snadné.)

Kapitola 8

Relace lineárního uspořádání Již víme, že pokud R je relace částečného uspořádání na množině M , potom můžeme najít vzájemně neporovnatelné prvky. Například množiny {1} a {2, 3} – obě jsou prvky potenční množiny P {1, 2, 3} – relací (resp. predikátem) inkluze „⊆ÿ nejsou vzájemně porovnatelné. Kromě porovnatelnosti a neporovnatelnosti zavedeme v následující definici i některé další pojmy. Definice 8.1. Na množině M budiž dána relace R. O dvou (různých) prvcích x, y ∈ M řekneme, že jsou v relaci R navzájem neporovnatelné právě tehdy, když neplatí ani xRy ani yRx. (Tedy ¬xRy∧ ∧ ¬yRx.) Dva (různé) prvky x, y ∈ M jsou porovnatelné právě tehdy, když xRy nebo yRx. (Tedy xRy ∨ yRx.) Relace R, ve které každé dva prvky jsou porovnatelné, je úplná nebo též totální. Relace R, v níž každé dva různé prvky jsou porovnatelné, se nazývá trichotomická. To znamená, že relace R na množině M je úplná právě tehdy, když ∀x, y ∈ M : xRy ∨ yRx . Relace R na množině M je trichotomická právě tehdy, když ∀x, y ∈ M : xRy ∨ x = y ∨ yRx . Poznámka 8.1. Není těžké si uvědomit, že když je relace úplná, potom je i trichotomická. Na druhou stranu, jestliže relace je trichotomická a na pomoc si vezmeme ještě reflexivitu, dostáváme úplnou relaci. Nadto, jestliže je relace úplná, potom je i reflexivní. Odvodili jsme následující závěr: Relace R na množině M je úplná právě tehdy, když je trichotomická a reflexivní. Nyní již přistupme k definici lineárního uspořádání. Definice 8.2. Relace R na množině M , která je relací částečného uspořádání (je tedy reflexivní, tranzitivní a antisymetrická) a je navíc trichotomická (takže každé dva prvky jsou porovnatelné), je relací lineárního uspořádání. (Lineární uspořádání se někdy nazývá také úplné nebo totální uspořádání.) 55

56

KAPITOLA 8. RELACE LINEÁRNÍHO USPOŘÁDÁNÍ Nyní uvedeme několik příkladů.

Příklad 8.1. Potenční množina prázdné množiny, P(∅) = {∅}, a potenční množina jednoprvkové množiny, P {a} = ∅, {a} , jsou relací resp. predikátem inkluze „⊆ÿ uspořádány lineárně. Jakmile však množina A obsahuje alespoň dva (různé) prvky, takže {a, b} ⊆ ⊆ A, kde a a b jsou dva různé prvky, potom její potenční množina P(A) je částečně uspořádána inkluzí, ale toto uspořádání už není lineární. Viz též příklad 2.2. Příklad 8.2. Množina přirozených čísel N, množina celých čísel Z, množina racionálních čísel Q i množina všech reálných čísel R je relací standardního uspořádání „≤ÿ lineárně uspořádána. Jako příklad lineárního uspořádání může posloužit také lexikografické uspořádání. S lexikografickým uspořádáním se setkáváme v poněkud specializovanějších oblastech matematiky. Je proto možné, že čtenář pojem lexikografického uspořádání hned tak potřebovat nebude. Na druhou stranu, s lexikografickým uspořádáním se setkáváme také zcela běžně, a to i v každodenním životě – stačí uvážit příklad abecedního uspořádání slov (ve slovníku, encyklopedii, rejstříku, seznamu studentů apod.). Příklad 8.3. (Lexikografické uspořádání.) Množinu M = R2 všech uspořádaných dvojic reálných čísel uspořádáme lexikograficky. Relaci lexikografického uspořádání označíme „ÿ. Zvolme dvě uspořádané dvojice [x, y], [x0 , y 0 ] ∈ R2 . Vztah [x, y] [x0 , y 0 ] platí právě tehdy, když x < x0 nebo x = x0 a y ≤ y 0 . Právě zavedené lexikografické uspořádání „ÿ je lineárním uspořádáním množiny M = R2 . Obdobným způsobem je možné uspořádat také množinu M = R3 . Pro [x, y, z], [x0 , y 0 , z 0 ] ∈ R3 máme [x, y, z] [x0 , y 0 , z 0 ] právě tehdy, když x < x0 nebo x = x0 a y < y 0 nebo x = x0 a y = y 0 a z ≤ z 0 . Obdobně by šlo uspořádat také množinu R4 atd. Lze však jít ještě dále. V podstatě lze říci, že máme-li n lineárně uspořádaných množin M1 , . . . , Mn , potom na jejich kartézském součinu M1 × · · ·× × Mn můžeme zavést lexikografické uspořádání. Následně můžeme říci, že lineární uspořádání množiny reálných čísel M1 = R = R1 je speciálním případem lexikografického uspořádání pro speciální případ, kdy n = 1. Cvičení 8.1. (Dobrovolně.) Ověřte, že lexikografické uspořádání má všechny vlastnosti lineárního uspořádání – je reflexivní, tranzitivní, antisymetrické a úplné (každé dva prvky jsou porovnatelné). — — —

Cvičení 8.2. Na množině M = {a, b, c, d}, kde a, b, c, d jsou čtyři navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání splňující vztahy a ≤ b a c ≤ d. (Množina M a relace „≤ÿ je stejná jako ve cvičení 7.5. ) Je množina M uspořádána lineárně?

Kapitola 9

Husté uspořádání. Dobré uspořádání Začneme pojmem hustého uspořádání. Definice 9.1. (Husté uspořádání.) Nechť R je relace na množině M . Relace R je relací hustého uspořádání právě tehdy, když R je relací (částečného) uspořádání a navíc splňuje podmínku ∀x, y ∈ M : (xRy ∧ x 6= y) =⇒ ∃z ∈ M : xRz ∧ x 6= z ∧ z 6= y ∧ zRy . To znamená, že mezi každými dvěma různými prvky x a y najdeme ještě třetí prvek z. Z podané definice snadno plyne následující tvrzení. Tvrzení 9.1. Hustě uspořádaná množina, která má alespoň dva různé a navzájem porovnatelné prvky, už je nekonečná. Intuitivně by uvedené tvrzení mělo být naprosto zřejmé. (Vskutku: mezi dvěma prvky najdeme prostřední prvek, mezi prvním a prostředním najdeme další prvek atd.) Přesný důkaz vynecháváme. Například proto, že nemáme zaveden pojem nekonečné množiny – formální definice pojmu nekonečné množiny by už byla nad rámec těchto skript. Čtenář se tedy musí spokojit jen s intuitivním porozuměním, případně pojem nekonečné množiny může vyhledat v literatuře. Uveďme dva příklady. Příklad 9.1. Množina přirozených čísel N ani množina celých čísel Z relací „≤ÿ nejsou hustě uspořádány. Příklad 9.2. Množina racionálních čísel Q i množina reálných čísel R jsou relací „≤ÿ hustě uspořádány. Ale daleko větší význam v teorii množin má pojem dobrého uspořádání. Definice 9.2. (Dobré uspořádání.) Nechť R je relace na množině M . Množina M je relací R dobře uspořádána právě tehdy, když relace R je reflexivní, 57

58

KAPITOLA 9. USPOŘÁDÁNÍ HUSTÉ A DOBRÉ

tranzitivní, antisymetrická, každé dva prvky množiny M je možné porovnat (takže R je relací lineárního uspořádání na M ) a platí, že každá neprázdná podmnožina množiny M má nejmenší prvek, ∀A ⊆ M, A 6= ∅, ∃a ∈ A ∀x ∈ A: aRx . Opět uveďme několik příkladů: Příklad 9.3. Množina přirozených čísel N je dobře uspořádána. Příklad 9.4. Množina celých čísel Z relací „≤ÿ není dobře uspořádána. Příklad 9.5. Ani množina všech nezáporných racionálních čísel Q+ 0 není dobře uspořádána. Ani racionální ani reálná čísla, Q ani R, nejsou dobře uspořádána. Všechny v tomto příkladě vyjmenované množiny jsou totiž hustě uspořádány. A snadno se nahlédne, že hustě uspořádaná množina s alespoň dvěma prvky nemůže být dobře uspořádaná. Cvičení 9.1. (Dobrovolně.) Nechť (M, ≤) je hustě uspořádaná množina. Předpokládejme, že množina M obsahuje alespoň dva různé a vzájemně porovnatelné prvky. Dokažte, že množina M relací „≤ÿ není dobře uspořádána. — — —

Cvičení 9.2. Na množině M = {a, b, c, d}, kde a, b, c, d jsou čtyři navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání splňující vztahy a ≤ b a c ≤ d. (Množina M a relace „≤ÿ je stejná jako ve cvičení 7.5.) Je množina M uspořádána hustě? Je množina M uspořádána dobře? Cvičení 9.3. Na množině M = h0, 2i – uzavřený interval reálných čísel od 0 do 2 – uvažujme obvyklé uspořádání „≤ÿ. Je množina M hustě uspořádána? Je množina M dobře uspořádána? Cvičení 9.4. Na množině M = {a, b, c, d}, kde a, b, c, d jsou čtyři navzájem různé prvky, je dána relace „≤ÿ lineárního uspořádání tak, že platí a ≤ b ≤ c ≤ ≤ d. Je množina M hustě uspořádána? Je množina M dobře uspořádána?

Kapitola 10

Částečné uspořádání – další pojmy V této kapitole uvedeme některé (trochu) pokročilejší pojmy, se kterými se v souvislosti s částečným uspořádáním můžeme setkat. Čtenář už možná slyšel o pojmech suprema a infima. Je zajímavé, že tyto pojmy lze zavést už v částečně uspořádané množině. Definice 10.1. Nechť (M, ≤) je částečně uspořádaná množina. Uvažujme nějakou její podmnožinu A ⊆ M . Prvek u ∈ M je horní závorou množiny A právě tehdy, když ∀a ∈ A: a ≤ u . Prvek l ∈ M je dolní závorou množiny A právě tehdy, když ∀a ∈ A: l ≤ a . Jako U nyní označme množinu všech horních závor množiny A. Může se stát, že tato množina U má nejmenší prvek. A tento nejmenší prvek (tj. nejmenší z množiny horních závor) nazveme supremem množiny A. To znamená, že prvek s ∈ M je supremem množiny A právě tehdy, když ∀a ∈ A: a ≤ s (je horní závorou) a současně ∀u ∈ M : (∀a ∈ A: a ≤ u) ⇒ s ≤ u (každá jiná horní závora je větší). Infimum zavedeme obdobně. Takže jako L označme množinu všech dolních závor množiny A. Má-li tato množina největší prvek, nazveme jej infimem množiny A. To znamená, že prvek i ∈ M je infimem množiny A právě tehdy, když ∀a ∈ A: i ≤ a (je dolní závorou) a současně ∀l ∈ M : (∀a ∈ A: l ≤ a) ⇒ l ≤ i (každá jiná dolní závora je menší). Předpokládáme-li, že množina M je uspořádána lineárně a že supremum a infimum zvolené podmnožiny A ⊆ M existuje, můžeme právě definované pojmy znázornit následujícím obrázkem: 59

60

KAPITOLA 10. ČÁSTEČNÉ USPOŘÁDÁNÍ – DALŠÍ POJMY M:

U s A i L

Poznámka 10.1. Dodejme, že některé podmnožiny nemusí mít horní závoru (nemusejí být shora omezené). K tomu stačí uvážit příklad množiny všech přirozených čísel M = N a jako její podmnožinu vzít například ji samotnou, A = N. (Případně jako podmnožinu A vzít množinu všech jejích sudých čísel apod.) Vidíme, že množina A v množině přirozených čísel N není shora omezená. Aby nevznikal dojem, že když máme nějakou (částečně) uspořádanou množinu M a vezmeme A = M , potom množina A v množině M není shora omezená, uvažme příklad M = h1, 2i. Za množinu M jsme zvolili uzavřený interval všech reálných čísel od 1 do 2. Položíme-li A = M , potom množina A je v M samozřejmě omezena shora. Horní závorou je číslo 2. Nechť (M, ≤) je částečně uspořádaná množina a nechť A je její podmnožina. Omezenost množiny A shora (tzn., že množina A má alespoň jednu horní závoru) samozřejmě nezaručuje existenci suprema množiny A (tj. nejmenšího prvku v množině všech horních závor). Jako příklad poslouží množina M = Q všech racionálních čísel. Položme A = { x ∈ Q ; x2 ≤ 2 ∨√x ≤ 0 } – jde o množinu všech racionálních čísel splňujících podmínku x ≤ 2. Je zřejmé, že tato množina A je shora omezená. Horní závorou je například číslo 3. Avšak množina A v √ množině racionálních čísel Q žádné supremum nemá. (Supremem by bylo číslo 2. Ale to neleží v množině Q.) Obdobné poznámky platí také o dolních závorách a o infimech. Právě uvedenou poznámku doplníme ještě jedním příkladem. Příklad 10.1. Uvažujme množinu M = (1, 2), tedy otevřený interval všech reálných čísel mezi čísly 1 a 2. Položme A = (1, 2). (Opět jsme zvolili A = M . Ale obdobně bychom mohli volit také např. A = 12 , 2 apod.) Potom takto zvolená množina A v množině M není shora omezená. Jistě se zeptáte proč – zejména když každý prvek množiny A je menší než číslo 2. Avšak číslo 2 neleží v množině M ! Nenajdeme žádný prvek a ∈ M , který by množinu A omezoval shora. (Je-li dána množina M , ve které se máme pohybovat, potom svoje vnímání musíme jakoby omezit jen na tuto množinu M . Mimo tuto množinu (vně této množiny) M už jakoby nic dalšího neexistuje.)

— — — Nyní se zaměříme na pojmy svazu, spojového polosvazu a průsekového polosvazu. Nejdříve však zavedeme pojem binární operace na množině. (Srovnej definici relace na množině ze sedmé kapitoly.) Definice 10.2. (Operace na množině.) Nechť M je nějaká množina. Pak binární operací na množině M rozumíme jakékoliv zobrazení O: M × M → M .

61 Poznámka 10.2. Binární operace obvykle zapisujeme infixově. Vezměme například binární operaci „+ÿ sčítání reálných čísel. Z formálního hlediska jde o zobrazení resp. funkci dvou proměnných +: R × R → R, která každým dvěma reálným číslům a a b přiřadí jejich součet +(a, b), což je opět reálné číslo. Například +(7, 14) = 21. Častěji však operaci součtu zapisujeme infixově, tedy a + b. Například 7 + 14 = 21. Definice 10.3. (Svaz, spojový polosvaz a průsekový polosvaz – množinová definice.) Svazem rozumíme částečně uspořádanou množinu (M, ≤), ve které množina {a, b} má supremum i infimum pro libovolné dva prvky a, b ∈ M . Spojovým polosvazem rozumíme částečně uspořádanou množinu (M, ≤), ve které množina {a, b} má supremum pro libovolné dva prvky a, b ∈ M . Průsekovým polosvazem rozumíme částečně uspořádanou množinu (M, ≤), ve které množina {a, b} má infimum pro libovolné dva prvky a, b ∈ M . Jestliže částečně uspořádaná množina (M, ≤) je spojovým polosvazem, pak na ní můžeme definovat binární operaci „∨ÿ – tedy zobrazení ∨: M × M → M – předpisem a ∨ b = sup{a, b} pro všechna a, b ∈ M . Zavedenou operaci „∨ÿ nazýváme spojením. Odtud název „spojový polosvazÿ. Vidíme, že spojením dvou prvků dostáváme právě jejich supremum. Obdobně, jestliže částečně uspořádaná množina (M, ≤) je průsekovým polosvazem, potom na ní můžeme definovat binární operaci „∧ÿ – tedy zobrazení ∧: M × M → M – předpisem a ∧ b = inf{a, b} pro všechna a, b ∈ M . Zavedenou operaci „∧ÿ nazýváme průsekem. Odtud název „průsekový polosvazÿ. Průsekem dvou prvků dostáváme právě jejich infimum. Když částečně uspořádaná množina (M, ≤) je svazem, potom na ní můžeme definovat obě výše uvedené operace „∧ÿ a „∨ÿ. Nyní vyjmenujeme vlastnosti, které jsou pro zavedené operace průseku a spojení resp. pro infimum a supremum charakteristické: • Operace „∧ÿ i „∨ÿ jsou idempotentní, tzn., že pro každé a ∈ M platí a∧a=a

a

a∨a=a

neboli inf{a, a} = a a současně sup{a, a} = a. • Operace „∧ÿ i „∨ÿ jsou komutativní, tzn., že pro každé a, b ∈ M platí a∧b=b∧a

a

a∨b=b∨a

neboli inf{a, b} = inf{b, a} a současně sup{a, b} = sup{b, a}. • Operace „∧ÿ i „∨ÿ jsou asociativní, tzn., že pro každé a, b, c ∈ M platí a ∧ (b ∧ c) = (a ∧ b) ∧ c a a ∨ (b ∨ c) = (a ∨ b) ∨ c neboliinf a, inf{b, c} = inf inf{a, b}, c a současně sup a, sup{b, c} = = sup sup{a, b}, c .

62

KAPITOLA 10. ČÁSTEČNÉ USPOŘÁDÁNÍ – DALŠÍ POJMY • Operace „∧ÿ a „∨ÿ splňují zákony absobpce, tzn., že pro každé a, b ∈ M platí a ∧ (a ∨ b) = a a a ∨ (a ∧ b) = a neboli inf a, sup{a, b} = a a současně sup a, inf{a, b}} = a. • Operace „∧ÿ i „∨ÿ jsou s původní relací „≤ÿ svázány následujícími předpisy, které platí pro všechna a, b ∈ M : a≤b a≤b

právě tehdy, když právě tehdy, když

a = a ∧ b, b = a ∨ b.

(♠) (♣)

Definice 10.4. (Svaz, spojový polosvaz a průsekový polosvaz – algebraická definice.) Svazem rozumíme množinu M spolu se dvěma idempotentními, komutativními a asociativními operacemi „∧ÿ a „∨ÿ, které navíc splňují zákony absorpce. Spojovým polosvazem rozumíme množinu M spolu s idempotentní, komutativní a asociativní operací „∨ÿ. Průsekovým polosvazem rozumíme množinu M spolu s idempotentní, komutativní a asociativní operací „∧ÿ. Poznámka 10.3. V případě svazu je podstatné, že operace „∧ÿ a „∨ÿ jsou spolu provázány zákony absorpce. Kdyby tomu tak nebylo, dostali bychom jen dva od sebe oddělené polosvazy – množinu M s operací „∧ÿ jako průsekový polosvaz a množinu M s operací „∨ÿ jako spojový polosvaz. Zákony absorpce oba tyto polosvazy vzájemně propojují. Poznámka 10.4. Množinová i algebraická definice svazu, spojového polosvazu a průsekového polosvazu jsou ekvivalentní. Vycházíme-li z množinové definice, pak na množině M můžeme zavést binární operaci „∨ÿ nebo „∧ÿ předpisem a ∨ b = sup{a, b} resp. a ∧ b = inf{a, b} pro a, b ∈ M (podle toho, zda máme svaz, spojový polosvaz nebo průsekový polosvaz). Výsledné operace budou idempotentní, komutativní a asociativní a – v případě svazu – budou splňovat i zákony absorpce. Vycházíme-li z algebraické definice, pak na množině M můžeme zavést relaci „≤ÿ předpisem (♣) resp. (♠) pro a, b ∈ M (podle toho, zda pracujeme se svazem, spojovým polosvazem nebo průsekovým polosvazem; v případě svazu lze použít kterýkoliv ze vztahů (♣) nebo (♠)). Následně pro všechna a, b ∈ M začnou platit vztahy a ∨ b = sup{a, b} resp. a ∧ b = inf{a, b} (pracujeme-li se svazem, budou platit oba tyto vztahy). Vyjmenované vlastnosti suprem a infim, jakož i ostatní tvrzení vyslovená ve výše uvedených poznámkách, zde podáváme bez důkazu. Z části proto, že všechna tato tvrzení snadno plynou z definic suprema a infima, z části proto, že v těchto skriptech na teorii svazů a polosvazů není položen takový důraz. Čtenář si tato tvrzení může promyslet samostatně. — — — Ve zbývající části této kapitoly se budeme věnovat axiomu výběru, Zornovu

63 lemmatu a principu dobrého uspořádání. Než tak učiníme, zavedeme několik nových pojmů. Z dřívějška už známe pojem sjednocení dvou množin (tj. binární operaci sjednocení). V následující definici zavedeme mnohem obecnější pojem sjednocení množiny. Definice 10.5. (Sjednocení množiny.) Nechť M je množina obsahující množiny). Pak jejím sjednocením, tj. sjednocením množiny M, rozumíme množinu [

M = { x ; ∃M ∈ M: x ∈ M } .

S Poznámka 10.5. Operace sjednocení množiny „ ÿ je unární operací na Universu teorie množin. Jinými operacemi, které už známe, jsou například binární operace sjednocení „∪ÿ, průniku „∩ÿ, kartézského součinu „×ÿ množin a tak podobně. Příklad 10.2. Máme například [

{1, 3, 5}, {1, 2, 4, 5}, {1, 4, 5, 7} = {1, 2, 3, 4, 5, 7} .

Vidíme, že operace sjednocení množiny M, zde máme M = {1, 3, 5}, {1, 2, 4, 5}, {1, 4, 5, 7} , sjednocuje množiny „uvnitřÿ množiny M. Poznámka 10.6. Ukažme, jaký je vztah mezi novou operací sjednocení mnoS žiny „ ÿ a operací sjednocení množin „∪ÿ, kterou už známe. Rozmyslete si samostatně, že když A a B jsou dvě množiny, potom [

{A, B} = A ∪ B .

Cvičení 10.1. S 1. Určete {1, 2, 3}, {5, 6, 7}, {3, 4, 5} . 2. Co je výsledkem sjednocení prázdné množiny, tedy

S

∅?

Dále zavedeme pojem řetězce. Definice 10.6. (Řetězec.) Nechť (M, ≤) je částečně uspořádaná množina. Podmnožinu R ⊆ M nazveme řetězcem právě tehdy, když množina R je relací „≤ÿ uspořádána lineárně: ∀x, y ∈ R: x ≤ y ∨ y ≤ x . Připomeňme, že prvek a je maximálním prvkem částečně uspořádané množiny (M, ≤) právě tehdy, když nenajdeme žádný další prvek x ∈ M , pro který by platilo a ≤ x. Máme-li nějakou částečně uspořádanou množinu (M, ≤), můžeme se ptát, zda v této množině najdeme alespoň jeden maximální prvek. V tom nám může pomoci Zornovo (čti cornovo) lemma.

64

KAPITOLA 10. ČÁSTEČNÉ USPOŘÁDÁNÍ – DALŠÍ POJMY

Lemma 10.1. (Zornovo lemma.) Nechť (M, ≤) je částečně uspořádaná množina a nechť je splněna tzv. Zornova vlastnost: každý řetězec R ⊆ M je shora omezený, ∀R ⊆ M : (∀x, y ∈ R: x ≤ y ∨ y ≤ x) =⇒ (∃m ∈ M ∀r ∈ R: r ≤ m) . Potom množina M má (alespoň jeden) maximální prvek. Poznámka 10.7. Prázdná množina R = ∅ je také řetězcem. Odtud (užitím Zornovy vlastnosti) plyne, že množina M musí být neprázdná: I prázdný řetězec musí mít nějakou horní závoru. Horní závorou prázdného řetězce je kterýkoliv prvek množiny M . Poznámka 10.8. Někteří matematici by byli schopni o platnosti Zornova lemmatu vést velmi dlouhé filosofické debaty. Přinejmenším v dřívějších dobách tomu tak bylo. V trošku pokročilejší části teorie množin se totiž dokazuje, že Zornovo lemma je ekvivalentní s axiomem výběru1 . (To znamená, že přijmeme-li axiom výběru za pravdivý, potom můžeme dokázat Zornovo lemma. Na druhou stranu, vezmeme-li Zornovo lemma za pravdivý fakt, potom snadno dokážeme také platnost axiomu výběru.) Důvodem zmíněných filosofických debat je skutečnost, že pomocí axiomu výběru je možné dokázat rozličná tvrzení, která na první pohled vypadají neuvěřitelně, resp. „nesprávněÿ, protože jsou v rozporu s přirozenou intuicí či představivostí. Někteří matematici pak na základě tohoto faktu usuzují, že axiom výběru je nesprávný. Ovšem všechny „rozporyÿ je, s trochou snahy, možné vysvětlit. Také je třeba uvážit fakt, že o axiom výběru se opírají rovněž důkazy celé řady velmi užitečných tvrzení (za všechny uveďme např. Heineho charakteristiku spojitosti funkce). Popření platnosti axiomu výběru by proto znamenalo připravit se i o podstatnou část matematiky. Zmiňme ještě následující problém. Je dána nějaká množina M . Ptáme se, zda tuto množinu je možné dobře uspořádat. Existuje nějaká relace R na M (tj. podmnožina R ⊆ M × M ), která je dobrým uspořádáním množiny M ? Odpověď dává následující věta, známá také jako princip dobrého uspořádání. Princip dobrého uspořádání. Každou množinu je možné dobře uspořádat. V teorii množin se opět dokazuje, že princip dobrého uspořádání je ekvivalentní s axiomem výběru. Takže: axiom výběru, princip dobrého uspořádání a Zornovo lemma jsou navzájem ekvivalentní. — — — Cvičení 10.2. Na množině M = {a, b, c, d}, kde a, b, c, d jsou čtyři navzájem různé prvky, je dána relace „≤ÿ částečného uspořádání splňující vztahy a ≤ b a c ≤ d. (Množina M a relace „≤ÿ je stejná jako ve cvičení 7.5.) Určete všechny řetězce v množině M . (Buďte pozorní. Určete je opravdu všechny.) Jsou nalezené řetězce shora omezené? Má množina M alespoň jeden maximální prvek? 1 Uveďme axiom výběru. Nejprve vak definici: Selektorem na množině (množin) rozumíme funkci, která každé její neprázdné množině přiřadí nějaký její prvek. Přesněji řečeno, množina F je selektorem na systému množin M právě tehdy, když

Fnc(F ) ∧ Dom(F ) = M ∧ ∀X ∈ M: X 6= ∅ ⇒ F (X) ∈ X . Axiom výběru pak zní: Na každé množině M existuje alespoň jeden selektor F.

Kapitola 11

Relace ekvivalence V následující definici připomeneme pojmy reflexivity a tranzitivity relace, které už známe. Zavedeme také dva pojmy, které dosud neznáme. Definice 11.1. Nechť R je relace na množině M . Relace R je reflexivní právě tehdy, když ∀x ∈ M : xRx . Relace R je tranzitivní právě tehdy, když ∀x, y, z ∈ M : xRy ∧ yRz ⇒ xRz . Relace R je symetrická právě tehdy, když ∀x, y ∈ M : xRy ⇒ yRx . Relace R, která je reflexivní, tranzitivní a symetrická, se nazývá relací ekvivalence. Vidíme, že relace ekvivalence modelují (přesněji řečeno mají obdobné vlastnosti jako) predikát rovnosti „=ÿ. Je-li R relace ekvivalence a platí-li pro nějaké dva prvky x a y vztah xRy, znamená to, že tyto dva prvky jsou (z nějakého důvodu) rovnocenné – ekvivalentní. Nyní zavedeme pojem třídy ekvivalence. Definice 11.2. Nechť R je relací ekvivalence na množině M . Zvolme libovolný prvek x ∈ M a položme [x]R = { y ∈ M ; yRx } . Tato množina, kterou jsme označili [x]R , se nazývá třída ekvivalence určená prvkem x. Poznámka 11.1. Rozpomene-li se čtenář na operaci obrazu množiny přes množinu resp. relaci, může si uvědomit, že [x]R = { y ∈ M ; yRx } = R 00 {x} .

65

66

KAPITOLA 11. RELACE EKVIVALENCE

Zabývejme se nyní vlastnostmi tříd ekvivalence. Z reflexivity relace ekvivalence R (platí xRx) okamžitě plyne, že x ∈ [x]R . Každá třída ekvivalence, ať už je určená jakýmkoliv prvkem x ∈ M , je tedy neprázdná (protože x ∈ [x]R ). Zvolme jakýkoliv prvek y ∈ [x]R . Platí tedy yRx. Užitím symetrie relace ekvivalence (z yRx vyplývá xRy) dostáváme, že x ∈ [y]R . Provedeme-li tuto úvahu také obráceně, nahlédneme, že y ∈ [x]R nastává právě tehdy, když x ∈ ∈ [y]R . Zvolme nyní libovolné dva prvky x, y ∈ M a uvažujme třídy ekvivalence [x]R a [y]R těmito prvky určené. Jsou dvě možnosti: buď jsou tyto dvě třídy disjunktní (platí [x]R ∩ [y]R = ∅), anebo nejsou (existuje nějaký prvek z ∈ ∈ [x]R ∩ [y]R ). Ukážeme, že pokud nastává druhá z možností (nejsou disjunktní), potom jsou si tyto třídy rovny, [x]R = [y]R . Máme-li z ∈ [x]R ∩ [y]R , pak zRx a zRy. Užitím tranzitivity (z xRz a zRy plyne xRy; avšak abychom ze zRx odvodili xRz, museli jsme dříve použít také symetrii) dostáváme, že xRy. Symetrie dává také yRx. Nyní se vraťme k tomu, co máme dokázat. Máme dokázat, že [x]R = [y]R . Máme tedy dokázat, že pro libovolný prvek m platí m ∈ [x]R právě tehdy, když m ∈ [y]R . Ale to je už snadné. Jestliže m ∈ [x]R , potom tranzitivita (z mRx a xRy plyne mRy) dává, že m ∈ [y]R . A jestliže m ∈ [y]R , potom tranzitivita (z mRy a yRx plyne mRx) dává, že m ∈ [x]R . Dokázali jsme, že [x]R = [y]R . Vidíme, že z druhé možnosti (třídy [x]R a [y]R nejsou disjunktní) plyne rovnost obou tříd, [x]R = [y]R . Poznamenejme ale, že z první možnosti ([x]R ∩ ∩ [y]R = ∅) plyne nerovnost [x]R 6= [y]R . To proto, že každá ekvivalenční třída je neprázdná. (Kdyby [x]R = [y]R a [x]R ∩ [y]R = ∅, mohlo by to být jenom z důvodu, že [x]R = [y]R = ∅ – spor.) Tím jsme odvodili následující závěr: Rovnost [x]R = [y]R platí právě tehdy, když [x]R ∩ [y]R 6= ∅. Jestliže [x]R ∩ [y]R = ∅, snadno nahlédneme, že ¬xRy. (Je totiž x ∈ [x]R . Protože [x]R ∩[y]R = ∅, platí x ∈ / [y]R .) Na druhou stranu, jestliže [x]R ∩[y]R 6= ∅, pak [x]R = [y]R , jak jsme právě odvodili, a platí xRy. (Protože x ∈ [x]R = [y]R .) Dostali jsme tak ještě jeden závěr: Rovnost [x]R = [y]R nastává právě tehdy, když xRy. Shrňme všechny dosud dosažené výsledky do jednoho tvrzení. Tvrzení 11.1. Nechť R je relace ekvivalence na množině M . Platí, že každá třída ekvivalence určená nějakým prvkem x ∈ M je neprázdná. (Je totiž x ∈ ∈ [x]R .) Dále, pro libovolné dva prvky x, y ∈ M jsou následující výroky ekvivalentní: 1. [x]R = [y]R , 2. [x]R ∩ [y]R 6= ∅ , 3. xRy , 4. x ∈ [y]R , 5. y ∈ [x]R . Pokračujme ve svých úvahách. Máme-li množinu M a relaci ekvivalence R na ní, pak také následující výsledek je zřejmý: Každý prvek x ∈ M patří do nějaké třídy ekvivalence (patří do třídy [x]R ; již víme, že x ∈ [x]R ). Odtud vyplývá, že všechny třídy ekvivalence pokrývají celou množinu M – to znamená, že když

67 S jednotlivé třídy sjednotím, dostanu celou množinu M , neboli x∈M [x]R = M , S jinak zapsáno [x]R ; x ∈ M = M . Snad jen pro úplnost poznamenejme, že dva různé prvky mohou patřit do stejné třídy ekvivalence. Takže se může stát, že některá S třída ekvivalence T = = [x0 ]R (pro nějaké konkrétní x0 ∈ M ) ve sjednocení x∈M [x]R = M vystupuje několikrát (může existovat několik různých prvků x1 , x2 , . . . , xn ∈ M , které jsou různé i od x0 , takových, že T = [x0 ]R = [x1 ]R = [x2 ]R = · · · = [xn ]R ). Ale to nevadí, protože když několikrát sjednotím stále stejnou množinu, dostávám stále stejnou (sjednocovanou) množinu. Nakonec uvažujme množinu všech tříd ekvivalence: M/R = [x]R ; x ∈ M . Opět se může stát, že nějaká třída ekvivalence je v množině M/R uvedena několikrát (pro různé prvky x ∈ M ). Ale to opět nevadí. Již z úvodní hodiny víme, že pokud je nějaký prvek v množině (zavedené výčtem svých prvků) vícekrát, je to totéž, jako kdyby daný prvek byl v množině vyjmenován jen jednou. Poznámka 11.2. Zde jsme relaci ekvivalence označili znakem R. K označení relace ekvivalence s oblibou používáme také jiné znaky, např. „∼ÿ, „≈ÿ, „≡ÿ apod. Třídu ekvivalence určenou prvkem x bychom pak značili např. [x]∼ a množinu všech tříd ekvivalence bychom označili M/ ∼. Uveďme několik příkladů relací ekvivalence. V každém příkladu popíšeme také výslednou množinu tříd ekvivalence. Příklad 11.1. (Identita.) Nechť M je libovolná množina. Na množině M definujme relaci ekvivalence I tak, že pro libovolné dva prvky x, y ∈ M platí vztah xIy právě tehdy, když x = y (oba prvky jsou si rovny). Je tedy I = [x, y] ∈ ∈ M × M ; x = y . Potom I je relace ekvivalence na M – ověřte reflexivitu, tranzitivitu a symetrii. (V jistém smyslu jde o „nejjemnější možnouÿ relaci ekvivalence, protože I obsahuje pouze „diagonáluÿ kartézského součinu M × M .) Snadno nahlédneme, že třída ekvivalence určená prvkem x ∈ M obsahuje pouze prvek x, tedy [x]R = {x}. Takže M/R = {x} ; x ∈ M . Relace I je současně funkcí, Fnc(I), je to identické zobrazení na množině M . Pro každý prvek x ∈ M platí x = I(x). Graficky můžeme relaci I znázornit následovně: I

M M

Příklad 11.2. (Orientované úsečky.) Nechť M je množina všech orientovaných úseček v rovině (případně v prostoru). Orientovanou úsečkou rozumíme úsečku, jejíž jeden krajní bod považujeme za počáteční a druhý krajní bod považujeme za koncový – můžeme tedy říci, že orientovaná úsečka je vázaný vektor. Na množině M uvažujme relaci ekvipolence. Tuto relaci označme znakem R. Dvě orientované úsečky jsou ekvipolentní právě tehdy, když jsou rovnoběžné, mají stejnou orientaci a mají také stejnou délku. (Jinými slovy, dvě orientované −−→ −−→ úsečky AB a CD jsou ekvipolentní právě tehdy, když existuje nějaká středová

68


souměrnost, při níž bod A se zobrazí na bod D a bod B se zobrazí na bod C.) Není příliš těžké ověřit, že R je relací ekvivalence na M . Třídou ekvivalence je zde množina všech orientovaných úseček, které jsou navzájem ekvipolentní – jsou rovnoběžné, mají stejnou orientaci a stejnou délku. Třídě ekvivalence (tj. množině všech ekvipolentních vázaných vektorů) říkáme volný vektor. Příklad 11.3. (Křivková souvislost.) Nechť X je množina všech bodů v rovině (popř. na přímce nebo v prostoru apod.). Uvažujme libovolnou podmnožinu M ⊆ X. Pro jednoduchost vezměme nějaký konkrétní příklad. Položme M = h0, 1i × h0, 1i ∪ h2, 3i × h2, 3i ∪ h4, 5i × h0, 1i . Množina M je tvořena třemi („oddělenýmiÿ) čtverci v rovině. Délka strany každého z těchto čtverců je 1. (Nakreslete si obrázek! Anebo si ho aspoň představujte.) Nadále se omezíme jen na tuto množinu M , vše mimo ni jakoby „neexistujeÿ. Spojitou křivkou v množině M rozumíme jakékoliv spojité zobrazení f : ha, bi → M , kde a < b jsou dvě libovolná konečná reálná čísla. Je to tedy funkce, která každému bodu x uzavřeného intervalu ha, bi přiřadí nějaký bod f (x) množiny M . Tato funkce f navíc musí být spojitá. Zkusíte-li si takovouto funkci f nakreslit, dostanete „čáruÿ (tj. křivku), kterou je možné „nakreslit bez nutnosti zvednout tužku od papíruÿ – to je prapůvodní Eulerova definice spojitosti. (Poznamenejme, že někteří autoři spojitou křivku definují jinak. Spojitou křivkou rozumí množinu bodů, která je obrazem spojité funkce f výše popsaných vlastností. Spojitou křivkou tedy rozumí množinu Rng(f ). Funkci f mající výše uvedené vlastnosti pak nazývají reprezentací dané křivky. Je zřejmé, že jedna a táž křivka může mít několik různých reprezentací f .) Na množině M , kterou jsme výše zavedli, nyní definujme relaci ekvivalence R následovně: Zvolme dva body x, y ∈ M . Vztah xRy platí právě tehdy, když body x a y je možné spojit spojitou křivkou (která celá leží v množině M ). (Existují konečná reálná čísla a < b a existuje spojitá křivka f : ha, bi → M taková, že f (a) = x ∈ M a f (b) = y ∈ M .) V naší množině M lze každé dva body ze čtverce h0, 1i× × h0, 1i spojit spojitou křivkou. Stejně tak je možné libovolné dva body ze čtverce h2, 3i × h2, 3i nebo ze čtverce h4, 5i× × h0, 1i spojit křivkou. Vezmeme-li však body x a y ze dvou různých čtverců, z nichž množina M sestává (např. x ∈ h0, 1i× × h0, 1i a y ∈ h2, 3i× × h2, 3i), už je není možné spojit spojitou křivkou, která by celá ležela v množině M . (Křivka by musela jít i „venÿ z množiny M , což nelze.) Snadno nahlédneme, že zavedená relace R je relací ekvivalence na množině bodů M . Ověříme reflexivitu (xRx): K tomu stačí uvažovat křivku f , která „stojí na místěÿ, pro každé t ∈ ha, bi je f (t) = x. Anebo jakoukoliv uzavřenou křivku, která začíná i končí v bodě x. Ověříme symetrii (jestliže xRy, potom yRx): To je snadné. Máme-li spojitou křivku spojující bod x s bodem y, potom po této křivce stačí jít pozpátku. Nakonec ověříme tranzitivitu (jestliže xRy a yRz, potom xRz): Jestliže máme spojitou křivku f jdoucí z bodu x do bodu y a spojitou křivku g jdoucí z bodu y do bodu z, potom tyto dvě křivky stačí jen na sebe navázat. Tím dostaneme spojitou křivku spojující bod x s bodem z.

69 Vidíme také, že jednotlivými třídami ekvivalence podle relace R jsou zde právě jednotlivé čtverce h0, 1i × h0, 1i, h2, 3i × h2, 3i a h4, 5i × h0, 1i, ze kterých množina M sestává. Obecně lze říci, že nějaká množina K je křivkově souvislá právě tehdy, když každé dva její body lze spojit spojitou křivkou (která celá leží jen v množině K). Relace R tedy množinu M rozložila na jednotlivé třídy ekvivalence, které jsou křivkově souvislé. Příklad 11.4. (Reprezentace spojitých křivek.) Předcházející příklad nám vlastně poskytl ještě jeden příklad relace ekvivalence. Nechť M je nějaká množina bodů roviny (třeba jako v předcházejícím příkladě). Dále uvažujme množinu F všech reprezentací spojitých křivek v množině M . To znamená, že F je množina všech spojitých zobrazení f : ha, bi → M , kde a < b jsou dvě konečná reálná čísla. Na množině F zavedeme relaci ekvivalence následujícím způsobem: dvě reprezentace f, g ∈ F křivek jsou ekvivalentní právě tehdy, když reprezentují stejnou křivku (tedy Rng(f ) = Rng(g)). Lehce ověříme, že jde o relaci ekvivalence. Je třeba ověřit reflexivitu, tranzitivitu a symetrii: jistě f i f reprezentuje stále stejnou křivku; jestliže f a g reprezentují stejnou křivku, potom také g a f reprezentují stejnou křivku; jestliže f a g reprezentují stejnou křivku a g a h reprezentují stejnou křivku, potom f a h reprezentují stejnou křivku. Příklad 11.5. (Relace kongruence.) Zvolme jakékoliv nenulové celé číslo n ∈ Z. Na množině všech celých čísel Z zavedeme relaci kongruence modulo n. Dvě celá čísla a, b ∈ Z jsou kongruentní modulo n a píšeme a ≡ b (mod n) právě tehdy, když čísla a i b dávají stejný zbytek při dělení číslem n. To nastává právě tehdy, když n | (a − b) – číslo n dělí (a − b) – existuje číslo k ∈ Z takové, že kn = (a − b). Ověřte, že relace kongruence modulo n je relací ekvivalence na množině celých čísel Z. Promyslete si, že a ≡ a (mod n), že z a ≡ b (mod n) vyplývá b ≡ a (mod n) a že z a ≡ b (mod n) a b ≡ c (mod n) vyplývá a ≡ c (mod n), to vše pro libovolná celá čísla a, b, c ∈ Z. Množina celých čísel Z se rozpadá na celkově n (pokud n > 0, resp. −n, pokud n < 0) tříd ekvivalence. Dvě čísla patří do stejné ekvivalenční třídy právě tehdy, když při dělení číslem n dávají stejný zbytek. Příklad 11.6. (Zlomky.) Nyní uvažujme množinu uspořádaných dvojic M = = [a, b] ∈ Z × Z ; b 6= 0 . Na množině M zaveďme relaci ekvivalence „∼ÿ takto: [a, b] ∼ [a0 , b0 ] právě tehdy, když ab0 = ba0 . To nastává právě tehdy, 0 když ab = ab0 , takže uspořádané dvojice [a, b] a [a0 , b0 ] reprezentují jedno a totéž 0 racionální číslo ab = ab0 . Příklad 11.7. (Celá čísla.) Uvažujme množinu uspořádaných dvojic M = = [a, b] ∈ N × N ; b 6= 0 . Na množině M zaveďme relaci ekvivalence „∼ÿ následovně: [a, b] ∼ [a0 , b0 ] právě tehdy, když a + b0 = b + a0 . To nastává právě tehdy, když a − b = a0 − b0 , takže uspořádané dvojice [a, b] a [a0 , b0 ] reprezentují jedno a totéž celé číslo a − b = a0 − b0 . Po několika příkladech uveďme pro změnu definici.

70


Definice 11.3. (Rozklad množiny.) Nechť M je libovolná množina. Nechť M je kolekce podmnožin množiny M . (To znamená, že pro každé A ∈ M platí A ⊆ M .) Množina M je rozkladem množiny M právě tehdy, když jsou splněny následující dvě podmínky: S 1. M = M , 2. pro každé A, B ∈ M platí, že A ∩ B 6= ∅ právě tehdy, když A = B. Poznámka 11.3. První podmínka říká, že když jednotlivé množiny z M sjednotíme, dostaneme množinu M . To znamená, že množiny obsažené v M pokrývají množinu M , nebo že tyto množiny tvoří pokrytí množiny M . Druhá podmínka říká, že množina M obsahuje pouze neprázdné podmnožiny množiny M (kdyby A = ∅ ∈ M, pak A = A a ∅ ∩ ∅ = ∅ – spor). Současně tato podmínka říká, že dvě různé množiny z M (platí tedy A, B ∈ M a A 6= B) už musejí být disjunktní (A ∩ B 6= ∅ by znamenalo spor). Následující tvrzení je nyní zřejmé – stačí se jen vrátit k výše provedeným úvahám, kdy jsme zkoumali vlastnosti tříd ekvivalence určených jedním prvkem. Tvrzení 11.2. Nechť R je relace ekvivalence na množině M . Potom množina všech tříd ekvivalence M/R = [x]R ; x ∈ M tvoří rozklad množiny M . Poznámka 11.4. Rozklad M/R proto nazýváme rozkladem množiny M na třídy ekvivalence. Pro množinu všech tříd ekvivalence ale používáme ještě jeden přesnější název. Definice 11.4. (Faktorová množina.) Nechť R je relace ekvivalence na množině M . Množině M/R = [x]R ; x ∈ M říkáme faktorová množina množiny M podle relace R. Následující tvrzení je také zřejmé. Je lepší jej pochopit intuitivně. (Důkaz – jediný vzoreček – sice podáváme také, ale je daleko lepší tvrzení pochopit, než se tento důkaz učit „nazpaměťÿ.) Tvrzení 11.3. Nechť M je rozklad množiny M . Potom na množině M existuje právě jedna relace ekvivalence R taková, že M = M/R. S S Důkaz. R = A∈M A × A, neboli R = { A × A ; A ∈ M }.

— — — Již víme, že faktorová množina M/R určená relací R tvoří rozklad. Na druhou stranu, rozklad množiny zase zpátky určuje jistou relaci ekvivalence. Dostáváme tak hlavní výsledek celého tohoto pojednání o relacích ekvivalence:

71 Věta 11.4. Rozklady množiny M a relace ekvivalence na množině M si vzájemně odpovídají. Výše jsme uvedli několik příkladů relací ekvivalence na různých množinách. A na výše uvedených příkladech je možné demonstrovat všechny poznatky, které jsme zde objasnili (rozklad apod.) Uvedeme ještě jeden malý příklad (obsahující i lehoučké cvičení). Příklad 11.8. Na množině M = {1, 2, 3, 4, 5, 6} budiž dána relace ekvivalence R = [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3], [4, 4], [4, 5], [5, 4], [5, 5], [6, 6] . (Ověřte, že jde o relaci ekvivalence na M – ověřte reflexivitu, tranzitivitu a symetrii.) Dále máme rozklad M/R = M = {1, 2, 3}, {4, 5}, {6} . (Ověřte, že jde o rozklad množiny M – ověřte potřebné vlastnosti.) Nahlédněte, že rozklad M/R = M a relace R si vzájemně odpovídají! — — —

Cvičení 11.1. Na množině M = {1, 2, 3, 4, 5} je dána relace ekvivalence R = [1, 1], [1, 3], [1, 5], [3, 1], [3, 3], [3, 5], [5, 1], [5, 3], [5, 5], [2, 2], [2, 4], [4, 2], [4, 4] . Určete rozklad M/R. Cvičení 11.2. Máme rozklad M = {1, 2}, {3, 4}, {5} množiny M = {1, 2, 3, 4, 5}. Určete odpovídající relaci ekvivalence R na množině M tak, aby platilo M/R = M.

72


Kapitola 12

Poznámka o kvaziuspořádání V této kapitole uvedeme stručnou poznámku o kvaziuspořádání. Uvedeme také vztah mezi kvaziuspořádáním, částečným uspořádáním a relací ekvivalence. Poznámka 12.1. Víme (viz sedmou kapitolu), že kvaziuspořádání je relace, která je reflexivní a tranzitivní. Také víme, že relace ekvivalence je reflexivní, tranzitivní a symetrická. Můžeme tedy říci, že relace ekvivalence je symetrické kvaziuspořádání. Platí také následující tvrzení. Jeho důkaz neuvádíme. (Jeho důkaz je snadný, plyne okamžitě z definic.) Zdatný čtenář by toto tvrzení mohl dokázat samostatně, případně platnost níže uvedeného tvrzení nahlédnout intuitivně. Tvrzení 12.1. Nechť „ÿ je relace kvaziuspořádání na množině M . Na množině M zaveďme relaci „∼ÿ následovně: pro x, y ∈ M platí x ∼ y právě tehdy, když x y a současně y x. Potom „∼ÿ je relací ekvivalence na množině M . Na faktorové množině M/ ∼ zaveďme relaci „≤ÿ následovně: pro [x]∼ , [y]∼ ∈ ∈ M/ ∼ (kde x, y ∈ M ) platí [x]∼ ≤ [y]∼ právě tehdy, když x y. (Definice relace „≤ÿ není závislá na volbě reprezentantů x a y.) Potom relace „≤ÿ je relací částečného uspořádání na faktorové množině M/ ∼.

73

74

KAPITOLA 12. POZNÁMKA O KVAZIUSPOŘÁDÁNÍ

Kapitola 13

Mohutnost množin V této kapitole se budeme věnovat důležitému pojmu mohutnosti (kardinality) množiny, který zobecňuje pojem počtu prvků pro konečné množiny. Uvažujme dvě množiny X a Y . Ptáme se, zda mají stejný počet prvků. Jsou-li konečné, můžeme jejich prvky spočítat a výsledné počty prvků pak porovnat. Co ale dělat když některá z množin je nekonečná? V takovém případě už prvky (intuitivně) spočítat neumíme. Na druhé straně je otázka, zda mají stejný počet prvků, mnohem jednodušší než otázka, kolik mají prvků. Prvky množin X a Y totiž počítat nemusíme, stačí zjistit, zda existuje vzájemně jednoznačné zobrazení. K tomuto problému se uvádí následující klasický příklad: Když chceme zjistit zda je v tanečním sále více děvčat nebo kluků, není třeba je počítat. Stačí zahrát do tance, spárovat děvčata a kluky a zjistit, zda zůstala sedět děvčata, kluci, nebo nikdo. O tuto úvahu se opírá několik následujících definic. Definice 13.1. Množiny X a Y jsou ekvivalentní 1 (můžeme říkat též ekvipotentní nebo že mají stejnou mohutnost) a píšeme X ≈ Y právě tehdy, když existuje prostá funkce F zobrazující množinu X na množinu Y . Formálně máme X ≈ Y právě tehdy, když ∃F : Fnc−1 (F ) ∧ Dom(F ) = X ∧ Rng(F ) = Y . Definice 13.2. Množina X je subvalentní 2 množině Y (říkáme též, že X má menší mohutnost než Y ) a píšeme X Y právě tehdy, když existuje prostá funkce F zobrazující množinu X do množiny Y . Formálně máme X Y právě tehdy, když ∃F : Fnc−1 (F ) ∧ Dom(F ) = X ∧ Rng(F ) ⊆ Y . Definice 13.3. Množina X je ostře subvalentní množině Y (má ostře menší 1 Latinsky: aequus = rovný (přímý), stejný. (Neplést s latinským equus = kůň, hřebec nebo equa = kobyla, klisna.) Latinsky je dále: valens = silný, mocný, mohutný; valeo = platiti (mj. o mincích), míti význam. Slovo „ekvivalentníÿ znamená „býti stejně hodnotnýÿ, zde však spíše „stejně mocný / mohutnýÿ. Zmiňme ještě latinské slovo potens = mohoucí, mocný, mající moc (vládnoucí). 2 Latinsky sub = pod (pod něčím, níže než).

75

76

KAPITOLA 13. MOHUTNOST MNOŽIN

mohutnost) a píšeme X ≺ Y právě tehdy, když X Y ∧ X 6≈ Y . Platí následující jednoduché tvrzení, jehož důkaz přenechávám čtenáři. Tvrzení 13.1. Pro libovolné dvě množiny X a Y platí: X ⊆ Y =⇒ X Y . Poznámka 13.1. Co když X ⊂ Y ? Platí X ≺ Y ? Ne. Stále může platit X ≈ ≈ Y , jak následující příklad ukazuje. Nechť N = {1, 2, 3, . . .} je množina všech přirozených čísel a nechť N0 = {0, 1, 2, 3, . . .} je množina přirozených čísel zahrnující i nulu. Potom zřejmě N0 ⊃ N, avšak N0 ≈ N. Stačí totiž uvážit zobrazení f : N0 → N definované předpisem f : n 7→ n + 1 pro všechna n ∈ N0 . Potom f je prosté zobrazení zobrazující množinu N0 na množinu N, což dokazuje N0 ≈ N. Uveďme několik základních vlastností predikátů „≈ÿ a „ÿ. Důkaz následujících tvrzení je veskrze snadný, a proto si dovoluji přenechat jej čtenáři. Tvrzení 13.2. Pro libovolné množiny X, Y , Z platí: 1. X ≈ X , 2. X ≈ Y ∧ Y ≈ Z ⇒ X ≈ Z , 3. X ≈ Y ⇒ Y ≈ X , 4. X X , 5. X Y ∧ Y Z ⇒ X Z , Nyní vyslovíme důležitou Cantorovu-Bernsteinovu větu. Její důkaz už je obtížnější, proto jej neuvádím. Věta 13.3. (Cantorova-Bernsteinova.) Pro libovolné dvě množiny X a Y platí X Y ∧ Y X =⇒ X ≈ Y . Poznámka 13.2. Předcházející snadné tvrzení v podstatě vyjadřovalo, že predikáty ≈„ÿ splňují obdoby zákonů reflexivity, tranzitivity a symetrie. Nepoměrně obtížnější Cantorova-Bernsteinova věta vyjadřuje obdobu zákona antisymetrie pro predikát „ÿ. — — — Platí rovněž následující věta. Věta 13.4. (Cantorova.) Nechť A je libovolná množina. Potom A ≺ P(A).

77 Důkaz. Nejprve dokážeme A P(A). To je snadné, protože když a ∈ A, potom {a} ∈ P(A). Stačí tedy uvážit prosté zobrazení F : A → P(A), které prvku a přiřadí {a}. Fakt, že nemůže platit A ≈ P(A), dokážeme sporem. Kdyby totiž platilo A ≈ ≈ P(A), potom by existovala prostá funkce F : A → P(A) zobrazující množinu A na množinu P(A) dosvědčující tak, že A ≈ P(A). Uvažujme množinu C = {x ∈ A ; x ∈ / F (x) } . Zřejmě je C ∈ P(A). Proto existuje z ∈ A tak, že F (z) = C. A nyní: Jestliže z ∈ C, potom z ∈ / F (z) = C. Jestliže z ∈ / C = F (z), potom z ∈ C. Spor. Tedy platí A 6≈ P(A). Proto A ≺ P(A). Poznámka 13.3. V důkazu byla použita slavná Cantorova diagonální metoda. Intuitivní popis její myšlenky je následující. Předpokládejme pro spor, že A ≈ P(A). Mezi množinami A a P(A) tedy existuje vzájemně jednoznačné zobrazení. Předpokládejme, že prvky množiny A je možné seřadit do „posloupnostiÿ: a1 , a2 , a3 , . . . Napišme tyto prvky vodorovně. A ve stejném pořadí napišme svisle jejich obrazy. Dostaneme tak následující „tabulkuÿ: a1

a2

a3

...

F (a1 ) F (a2 ) F (a3 ) .. . Jelikož zobrazení F je prosté a na, „posloupnostÿ F (a1 ), F (a2 ), F (a3 ), . . . musí vyjmenovat všechny prvky množiny P(A). Sestrojme množinu C následujícím postupem: Probírejme postupně prvky množiny A, tedy prvky a1 , a2 , a3 , . . . Jestliže a1 ∈ F (a1 ), potom prvek a1 do množiny C nevložíme; jinak ho tam vložíme. Jestliže a2 ∈ F (a2 ), potom prvek a2 do množiny C nevložíme; jinak ho tam vložíme. Atd. Nyní je zřejmé, že množina C je různá od všech množin F (a1 ), F (a2 ), F (a3 ), . . . (Kvůli prvku a1 se liší se od F (a1 ). Kvůli prvku a2 se liší se od F (a2 ). Atd. Množina C byla odlišena na „diagonáleÿ.) To ovšem znamená, že množina C není obsažena v P(A), protože F (a1 ), F (a2 ), F (a3 ), . . . byly všechny prvky této množiny. To je samozřejmě spor. V následující poznámce objasníme tzv. hypotézu kontinua. Poznámka 13.4. Nechť znak N označuje množinu všech přirozených čísel a nechť znak R označuje množinu všech reálných čísel. (Formálně zde tyto množiny nezavádíme. Ale předpokládejme, že víme, o které množiny jde.) Dá se dokázat, že množina přirozených čísel N má ze všech nekonečných množin nejmenší mohutnost. Dále se dá dokázat, že P(N) ≈ R. Georg Cantor vyslovil domněnku, že neexistuje žádná množina, která by měla mohutnost větší než N, ale menší než R. Jde tedy o domněnku, že ¬∃B: N ≺ B ≺ R.

78


Jde o hypotézu kontinua3 . Toto byl dlouhou dobu otevřený problém. Původem rakouský matematik a logik Kurt Gödel ukázal, že pokud hypotézu kontinua přidáme ke stávajícím axiomům teorie množin, potom nedostaneme žádný logický spor. V roce 1963 mladý matematik Paul Cohen dokázal, že pokud ke stávajícím axiomům teorie množin přidáme negaci hypotézy kontinua, potom také nedostaneme žádný logický spor. Hypotéza kontinua je tedy v rámci (standardní) teorie množin nerozhodnutelná. — — — Zakončeme tuto kapitolu definicí a několika příklady. Definice 13.4. Množina A je spočetná právě tehdy, když má stejnou mohutnost jako množina přirozených čísel N. Množina A je nespočetná právě tehdy, když její mohutnost je ostře větší než mohutnost množiny přirozených čísel N. Příklad 13.1. Už jsme si ukázali, že množiny N a N0 mají stejnou mohutnost. Lze ukázat, že i množiny N0 a Z mají stejnou mohutnost. Poněkud překvapivé je, že také množiny N a N × N mají stejnou mohutnost. Stejně tak množiny N a Q+ a Q mají stejnou mohutnost. Cantorovou diagonální metodou se ukáže, že množiny N a h0, 1i nemají stejnou mohutnost. Platí N ≺ h0, 1i. Pracujeme-li v rovině, pak přímka, půlkružnice (bez krajních bodů) a úsečka (bez krajních bodů) mají stejnou mohutnost. Pomocí Cantorovy-Bernsteinovy věty se ukáže, že i množiny h0, 1i a h0, 1i × × h0, 1i mají stejnou mohutnost. — — —

Cvičení 13.1. (Druhý korespondenční úkol.) Tento korespondenční úkol sestává ze dvou částí. (Obě tyto části tvoří jeden, druhý korespondenční úkol.) 1. Vyberte si jeden z následujících dvou příkladů: 1a. Množinu M = {1, 2, 3, 4, 5, 6, 7, 8, 9}, obsahující čísla od 1 do 9, částečně uspořádejte relací dělitelnosti. Nakreslete Hasseův diagram získaného uspořádání. Určete všechny nejmenší, minimální, maximální a největší prvky částečně uspořádané množiny M . 1b. Na množině M = {a, b, c, d, e, f }, obsahující šest různých prvků, je dána relace částečného uspořádání „≤ÿ splňující vztahy a ≤ c ≤ d ≤ ≤ f a b ≤ c ≤ e ≤ f . (Prvky a a b a prvky d a e nejsou vzájemně porovnatelné.) Nakreslete Hasseův diagram částečného uspořádání množiny M . Určete všechny nejmenší, minimální, maximální a největší prvky částečně uspořádané množiny M . 3 Kontinuum – kompaktní prostor s nekonečně mnoha body. Zde je míněna spíše uzavřená a omezená část Euklidovského prostoru, např. uzavřený interval. Dá se dokázat, že mohutnost uzavřeného a omezeného intervalu reálných čísel (tedy kontinua v Euklidovského prostoru) je rovna mohutnosti celé množiny R.

79 2. Je dána relace ekvivalence R = [5, 5], [5, 7], [7, 5], [7, 7], [1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4], [4, 1], [4, 2], [4, 4], [3, 3], [3, 6], [6, 3], [6, 6] . Určete (co možná největší) množinu M , na které je uvedená relace R relací ekvivalence. Pak napište rozklad M/R množiny M na třídy ekvivalence určené relací R.

80


Použitá literatura [1] Barrow, J. D. Pí na nebesích: O počítání, myšlení a bytí. Praha: Mladá fronta, 2000. ISBN 80-204-0855-X. [2] Balcar, B. – Štěpánek, P. Teorie množin. Praha: Academia, 1986. [3] Burian, K. Kapitoly z teorie množin. Ostrava: Pedagogická fakulta v Ostravě, 1985. [4] Burian, K. – Libicher, J. Algebra I. Ostrava: Pedagogická fakulta v Ostravě, 1982. [5] Faure, R. – Heurgonová, E. Uspořádání a Booleovy algebry. Praha: Academia, 1984. [6] Fürst, K. Slovník latinsko-český. Praha: Kvasnička a Hampl, 1941. [7] Šedivý, J. Základní poznatky z algebry a teorie čísel. 2. vydání. Praha: SPN, 1986. [8] B. Kočího malý slovník naučný. Praha: B. Kočí, 1929. 2 sv. [9] Malá československá encyklopedie. Praha: Academia, 1984–1987. 6 sv.

— — — Z knihy [1] čerpáno mnoho historických souvislostí. Citáty v poznámce pod čarou o Bertrandu Russellovi převzaty z této knihy doslovně. Některé historické aj. údaje převzaty také ze skript [7]. Významy latinských slov konsultovány také se slovníkem [6]. Z encyklopedie [9] čerpány uváděné základní životopisné údaje matematiků. Některé údaje o Bertrandu Russellovi doplněny též podle slovníku [8]. Kniha [2] pak představuje obsáhlou monografii o teorii množin. Řadu poznatků lze načerpat také z knihy [5]. K samostatnému studiu lze doporučit též skripta [3] a [4].

81

82

POUŽITÁ LITERATURA

Řešení cvičení 1.1. Máme A = C a B = D, protože nezálezí na pořadí prvků ve výčtu, rovněž nevadí, když prvek je ve výčtu uveden vícekrát. Dále máme E = F , neboť {} i ∅ označuje prázdnou množinu. Z uvedeného plyne, že M = {A, B, C} = {A, B} a že N = {C, D, A} = = {A, B}, neboť A = C a B = D.4 Odtud M = N. Dále samozřejmě O = P, neboť F = ∅. (Poznámka. Rovnost A = B obecně neplatí – zejména jsou-li prvky a, b a c navzájem různé. Je-li však a = c, potom platí také rovnost A = B, následně samozřejmě A = B = C = D.) 2.1. Vztah B ⊆ A dle definice inkluze pro dvě množiny B a A platí právě tehdy, když ∀x: x ∈ B ⇒ x ∈ A .

(∗)

Volme nejprve B = ∅. Protože pro každý prvek x platí x ∈ / ∅, předpoklad (antecedent) implikace ve formuli (∗) nikdy není splněn, takže celá implikace „x ∈ B ⇒ x ∈ Aÿ resp. „x ∈ ∅ ⇒ x ∈ Aÿ je pravdivá pro každé x, tj., formule (∗) je pravdivá. Podle definice inkluze pak máme ∅ ⊆ A. Nyní volme B = A. Nyní je zřejmé, že implikace „x ∈ B ⇒ x ∈ Aÿ resp. „x ∈ A ⇒ x ∈ Aÿ je pravdivá pro každé x, takže formule (∗) je pravdivá. Podle definice inkluze opět máme A ⊆ A. 2.2. Máme dokázat ekvivalenci dvou tvrzení, totiž A = B a A ⊆ B ∧ B ⊆ A. Začneme důkazem směru „⇒ÿ. Víme tedy, že A = B. Máme dokázat, že A ⊆ B ∧ B ⊆ A. Nejprve dokážeme, že A ⊆ B. Jelikož A = B, pro každý prvek x platí x ∈ A ⇔ x ∈ B, tudíž i x ∈ A ⇒ x ∈ B pro každé x. To dokazuje platnost inkluze A ⊆ B. Důkaz inkluze B ⊆ A se provede obdobně. Nyní dokážeme směr „⇐ÿ. Víme, že A ⊆ B a současně B ⊆ A neboli ∀x: x ∈ A ⇒ x ∈ B a ∀x: x ∈ B ⇒ x ∈ A. Dohromady máme ∀x: x ∈ A ⇔ ⇔ x ∈ B. Tím jsme dokázali, že množiny A a B mají stejné prvky. Axiom extensionality pak dává, že A = B. Tímto je důkaz ukončen. 4 Když víme, že A = C, potom při odvození vztahu {A, B, C} = {A, B, A} resp. {C, D, A} = = {A, D, A} ve skutečnosti používáme jeden z logických axiomů pro rovnost. (Vyjmenování všech (schémat) logických axiomů, ačkoliv jich není mnoho, je nad rámec těchto skript. Z toho důvodu je zde neuvádím.) Je proto možné, že úpravy M = {A, B, C} = {A, B, A} = {A, B} resp. N = {C, D, A} = {A, D, A} = {A, B, A} = {A, B} čtenáře „nenapadlyÿ právě kvůli nutnosti (implicitně) použít zmíněný logický axiom pro rovnost.

83

84

ŘEŠENÍ CVIČENÍ

2.3. Potenční množina n-prvkové množiny A má 2n prvků. Potenční množina P(A) je množina všech podmnožin množiny A. Když A je n-prvková, pak její podmnožiny jsou 0-prvkové (tedy prázdná množina), 1-prvkové, . . . , (n− 1)-prvkové a n-prvkové. Těchto podmnožin je po řadě 2-prvkové, n n n n n , , , . . . , a (tedy celá množina A). Dohromady – s ohledem 0 1 2 n−1 n na binomickou větu – je všech těchto podmnožin n (1 + 1)n = n0 + n1 + n2 + · · · + n−1 + nn . 2.4. Platí právě tyto vztahy: {a, b}, {b, c} ⊆ {a, b, c} a {b, c}, {c, d} ⊆ {b, c, d}. Hasseův diagram vypadá následovně: {a, b, c}

{a, b}

{b, c, d}

@ @ {b, c}

@ @ {c, d}

3.1.

Každý z uvedených vztahů je zřejmý. (Nakreslete si obrázky.)

3.2.

Žádný z uvedených vztahů obecně neplatí. (Nakreslete si obrázky.)

3.3. x ∈ C \ (A ∪ B) ⇐⇒ x ∈ C ∧ x ∈ / (A ∪ B) ⇐⇒ ⇐⇒ x ∈ C ∧ ¬ x ∈ (A ∪ B) ⇐⇒ ⇐⇒ x ∈ C ∧ ¬(x ∈ A ∨ x ∈ B) ⇐⇒ ⇐⇒ x ∈ C ∧ (x ∈ /A ∧ x∈ / B) ⇐⇒ ⇐⇒ x ∈ C ∧ x ∈ /A ∧ x∈ / B ⇐⇒ ⇐⇒ x ∈ C ∧ x ∈ C ∧ x ∈ /A ∧ x∈ / B ⇐⇒ ⇐⇒ (x ∈ C ∧ x ∈ / A) ∧ (x ∈ C ∧ x ∈ / B) ⇐⇒ ⇐⇒ x ∈ (C \ A) ∧ x ∈ (C \ B) ⇐⇒ ⇐⇒ x ∈ (C \ A) ∩ (C \ B) . '$

C

'$ '$

&% &% A&% B 3.4. x ∈ A ∪ (B ∩ C) ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x ∈ A ∨ x ∈ (B ∩ C) ⇐⇒ x ∈ A ∨ (x ∈ B ∧ x ∈ C) ⇐⇒ (x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x ∈ C) ⇐⇒ x ∈ (A ∪ B) ∧ x ∈ (A ∪ C) ⇐⇒ x ∈ (A ∪ B) ∩ (A ∪ C) .

85 3.5. 1. Obrázek čtenář najde v definici 3.3. rozdílu množin. Formální odůvodnění je poněkud méně záživné: x ∈ A \ B ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ x ∈ A \ B ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x∈A ∧ x∈ / B ⇐⇒ (x ∈ A ∧ x ∈ / B) ∨ (x ∈ B ∧ x ∈ / B) ⇐⇒ (x ∈ A ∨ x ∈ B) ∧ x ∈ / B ⇐⇒ x ∈ (A ∪ B) ∧ x ∈ / B ⇐⇒ x ∈ (A ∪ B) \ B , x∈A ∧ x∈ / B ⇐⇒ (x ∈ A ∧ x ∈ / A) ∨ (x ∈ A ∧ x ∈ / B) ⇐⇒ x ∈ A ∧ (x ∈ /A ∨ x∈ / B) ⇐⇒ x ∈ A ∧ ¬(x ∈ A ∧ x ∈ B) ⇐⇒ x ∈ A ∧ ¬(x ∈ A ∩ B) ⇐⇒ x∈A ∧ x∈ / (A ∩ B) ⇐⇒ x ∈ A \ (A ∩ B) .

2. Jde o zákon dvojí negace, viz tvrzení 3.2. Obrázek čtenář najde v definici 3.2. průniku množin. 3.6.

Jde o distributivní zákony.

1. Jde o nepatrně změněný vztah z tvrzení 3.3. Proto i důkaz proběhne obdobně. x ∈ (B ∪ C) ∩ A ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x ∈ (B ∪ C) ∧ x ∈ A ⇐⇒ (x ∈ B ∨ x ∈ C) ∧ x ∈ A ⇐⇒ (x ∈ B ∧ x ∈ A) ∨ (x ∈ C ∧ x ∈ A) ⇐⇒ x ∈ (B ∩ A) ∨ x ∈ (C ∩ A) ⇐⇒ x ∈ (B ∩ A) ∪ (C ∩ A) .

x ∈ (B ∪ C) \ A ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x ∈ (B ∪ C) ∧ x ∈ / A ⇐⇒ (x ∈ B ∨ x ∈ C) ∧ x ∈ / A ⇐⇒ (x ∈ B ∧ x ∈ / A) ∨ (x ∈ C ∧ x ∈ / A) ⇐⇒ x ∈ (B \ A) ∨ x ∈ (C \ A) ⇐⇒ x ∈ (B \ A) ∪ (C \ A) .

2.

3.7. 1.

x ∈ (A \ B) \ C ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x ∈ (A \ B) ∧ x ∈ / C ⇐⇒ x∈A ∧ x∈ /B ∧ x∈ / C ⇐⇒ x ∈ A ∧ ¬(x ∈ B ∨ x ∈ C) ⇐⇒ x∈A ∧ x∈ / (B ∪ C) ⇐⇒ x ∈ A \ (B ∪ C) .

86

ŘEŠENÍ CVIČENÍ '$ C '$ '$

&%

&% A&% B Srov. druhé de Morganovo pravidlo z tvrzení 3.1. a cvičení 3.3. 2. x ∈ A \ (B \ C) ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

x∈A ∧ x∈ / (B \ C) ⇐⇒ x ∈ A ∧ ¬(x ∈ B ∧ x ∈ / C) ⇐⇒ x ∈ A ∧ (x ∈ / B ∨ x ∈ C) ⇐⇒ (x ∈ A ∧ x ∈ / B) ∨ (x ∈ A ∧ x ∈ C) ⇐⇒ x ∈ (A \ B) ∨ (x ∈ A ∩ C) ⇐⇒ x ∈ (A \ B) ∪ (A ∩ C) . '$ C '$ '$

&%

&% A&% B

4.1. Volme např. a = 1 a b = c = 2, dále d = e = 1 a f = 2. (Vidíme, že skutečně b = c a e 6= f .) Pak máme

{a}, {a, b}, {a, b, c} = {1}, {1, 2}, {1, 2, 2} = = {1}, {1, 2}, {1, 2} = , = {1}, {1, 2}

obdobně

{d}, {d, e}, {d, e, f } = {1}, {1, 1}, {1, 1, 2} = = {1}, {1}, {1, 2} = . = {1}, {1, 2}

Je tedy

{a}, {a, b}, {a, b, c} = {1}, {1, 2} = {d}, {d, e}, {d, e, f } .

5.1. Oba uvedené vztahy lze nahlédnout intuitivně. Formální důkazy jsou následující:

87 1. ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

[x, y] ∈ (A ∪ B) × (C ∪ D) ⇐⇒ x ∈ (A ∪ B) ∧ y ∈ (C ∪ D) ⇐⇒ (x ∈ A ∨ x ∈ B) ∧ (y ∈ C ∨ y ∈ D) ⇐⇒ (x ∈ A ∧ y ∈ C) ∨ (x ∈ A ∧ y ∈ D) ∨ ∨ (x ∈ B ∧ y ∈ C) ∨ (x ∈ B ∧ y ∈ D) ⇐⇒ [x, y] ∈ (A × C) ∨ [x, y] ∈ (A × D) ∨ ∨ [x, y] ∈ (B × C) ∨ [x, y] ∈ (B × D) ⇐⇒ [x, y] ∈ (A × C) ∪ (A × D) ∪ (B × C) ∪ (B × D) .

2. ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

[x, y] ∈ (A ∩ B) × (C ∩ D) ⇐⇒ x ∈ (A ∩ B) ∧ y ∈ (C ∩ D) ⇐⇒ (x ∈ A ∧ x ∈ B) ∧ (y ∈ C ∧ y ∈ D) ⇐⇒ (x ∈ A ∧ y ∈ C) ∧ (x ∈ A ∧ y ∈ D) ∧ ∧ (x ∈ B ∧ y ∈ C) ∧ (x ∈ B ∧ y ∈ D) ⇐⇒ [x, y] ∈ (A × C) ∧ [x, y] ∈ (A × D) ∧ ∧ [x, y] ∈ (B × C) ∧ [x, y] ∈ (B × D) ⇐⇒ [x, y] ∈ (A × C) ∩ (A × D) ∩ (B × C) ∩ (B × D) .

5.2. 1. Podle definice je množina A relace právě tehdy, když je to množina uspořádaných dvojic, tj. právě tehdy, když A ⊆ Y × X, kde Y a X jsou vhodné množiny. Vzhledem k tomu, že definiční obor Dom(A) množiny A je množina všech druhých složek uspořádaných dvojic z množiny A a její obor hodnot Rng(A) je množina všech prvních složek jejích uspořádaných dvojic, stačí položit Y = Rng(A) a X = Dom(A). (Zajímavé je, že vztah A ⊆ Y × X platí pro libovolné dvě množiny Y ⊇ ⊇ Rng(A) a X ⊇ Dom(A) právě tehdy, když uvedený vztah platí i pro „maléÿ množiny Y = Rng(A) a X = Dom(A). Jestliže není Y ⊇ Rng(A) nebo není X ⊇ Dom(A), potom neplatí ani vztah A ⊆ Y × X.) 3. Množina A−1 obsahuje pouze uspořádané dvojice. Je tedy relací. 2. Jestliže množina A je relace, potom všechny její uspořádané dvojice zůstanou v množině A−1 zachovány. Pouze se zamění jejich složky. Použitím druhé inverze se složky opět vymění, takže dostaneme původní množinu A, tedy A = (A−1 )−1 . Jestliže množina A není relace, potom platí ostrá inkluze (A−1 )−1 ⊂ ⊂ A. Tj., dvojnásobným použitím inverze se množina A zmenší. (Samozřejmě již platí Rel(A−1 ) i Rel (A−1 )−1 , tudíž vždy platí rovnost A−1 = ((A−1 )−1 )−1 .)

88

ŘEŠENÍ CVIČENÍ

5.3. 1. Definici prosté funkce lze přepsat následovně: množina F je prostá funkce právě tehdy, když platí Rel(F ) a současně ∀x, y, z: [y, x] ∈ F ∧ [z, x] ∈ F ⇒ y = z ,

(∗)

∀x, y, z: [z, x] ∈ F ∧ [z, y] ∈ F ⇒ x = y .

(∗∗)

navíc Formule (∗), jelikož předpokládáme Rel(F ), vyjadřuje, že F je funkce. Formule (∗∗) pak říká, že funkce F je prostá. Zároveň ale tato formule (∗∗), jelikož vždy Rel(F −1 ), vyjadřuje, že inverze F −1 je funkce. Formule (∗) pak současně říká, že inverzní funkce F −1 je prostá. 2. Zřejmě máme A = Dom(F ). A jestliže funkce F : A → B zobrazuje množinu A na B, potom potom B = Rng(F ). Protože funkce F je prostá, je vzájemně jednoznačná (dle předchozího bodu), tedy inverze F −1 je také funkcí. Platí ovšem Dom(F ) = Rng(F −1 ) a Rng(F ) = Dom(F −1 ), jak z definic inverze, definičního oboru a oboru hodnot – vzhledem k tomu, že F je relace – vyplývá. Tedy B = Dom(F −1 ) a A = Rng(F −1 ), takže funkce F −1 : B → A zobrazuje množinu B na množinu A. 5.4. Množina Rng(F ) je množinou všech prvních složek uspořádaných dvojic z množiny F . Kartézský součin Rng(F ) × A je pak množina všech uspořádaných dvojic, kde první složka je stejná jako první složka nějaké uspořádané dvojice v množině F a druhá složka je z množiny A. Ty z těchto uspořádaných dvojic (tj. ze součinu Rng(F )× × A), které současně patří do množiny F , pak tvoří zúžení F A. Formální důkaz – na druhém řádku lze vsunout y ∈ Rng(F ), vsunutý vztah y ∈ Rng(F ) plyne z [y, x] ∈ F , který již na řádku je: [y, x] ∈ F A ⇐⇒ [y, x] ∈ F ∧ x ∈ A ⇐⇒ ⇐⇒ [y, x] ∈ F ∧ y ∈ Rng(F ) ∧ x ∈ A ⇐⇒ ⇐⇒ [y, x] ∈ F ∧ [y, x] ∈ Rng(F ) × A ⇐⇒ ⇐⇒ [y, x] ∈ F ∩ Rng(F ) × A . 5.5. Množina F A, tedy zúžení množiny F na A, je množinou všech uspořádaných dvojic z množiny F , které „leží nad množinou Aÿ. Obor hodnot této množiny, tedy množina všech prvních složek uspořádaných dvojic z této množiny, pak tvoří obraz F 00 A. Formální důkaz – opět se opíráme o axiom extensionality, ale už si nevystačíme s výrokovou logikou, musíme použít predikátovou logiku: y ∈ F 00 A ⇐⇒ ∃y: [y, x] ∈ F ∧ x ∈ A ⇐⇒ ⇐⇒ ∃y: [y, x] ∈ F A ⇐⇒ ⇐⇒ y ∈ Rng(F A) . 5.6. Množiny A, B, C lze volit „skoroÿ libovolně. Například = {∅}. A = B = C Pak máme A × B × C = [∅, ∅, ∅] = A × (B × C) = ∅, [∅, ∅] = 6 [∅, ∅], ∅ = (A × B) × C.

89 5.7. Rovnost A × (B × C) = (A × B) × C může platit jen ve výjimečných případech. Například tehdy, když alespoň jedna z množin A, B nebo C je prázdná: pak máme A × (B × C) = ∅ = (A × B) × C. Další případy jsou již natolik speciální, že je zde nebudu uvádět. 5.8. Množiny A × B, A ◦ B, A−1 , A B obsahují pouze uspořádané dvojice. Jsou tedy relacemi. (Ad bod 3.: srov. s bodem 3. tvrzení 5.1. resp. navazujícího cvičení 5.2.) 5.9. Definiční obor Dom(A) resp. obor hodnot Rng(A) je množina druhých resp. prvních složek uspořádaných dvojic z množiny A. V inverzi A−1 je pořadí složek zaměněno. Formálně: 1. x ∈ Dom(A) ⇐⇒ ∃y: [y, x] ∈ A ⇐⇒ ⇐⇒ ∃y: [x, y] ∈ A−1 ⇐⇒ ⇐⇒ x ∈ Rng(A−1 ) , 2. y ∈ Rng(A) ⇐⇒ ∃x: [y, x] ∈ A ⇐⇒ ⇐⇒ ∃x: [x, y] ∈ A−1 ⇐⇒ ⇐⇒ y ∈ Dom(A−1 ) . 5.10.

A×B =

[α, a], [α, b], [α, c], [β, a], [β, b], [β, c], [γ, a], [γ, b], [γ, c] .

5.11. 1. (a) A−1 = (b) A−1 (c) A−1 (d) A−1

[a, α], [b, α], [c, α] , = [a, α], [b, α], [a, β] , = [a, α], [a, β], [c, γ] , = [b, α], [a, β], [c, γ] .

2. (a) Dom(A) = {a, b, c}, (b) Dom(A) = {a, b}, (c) Dom(A) = {a, c}, (d) Dom(A) = {a, b, c}. 3. (a) Rng(A) = {α}, (b) Rng(A) = {α, β}, (c) Rng(A) = {α, β, γ}, (d) Rng(A) = {α, β, γ}. Prvky c, d (v případě (a) a (b)), a, b (v případě (c)), β, γ (v případě (d)) nejsou uspořádanými dvojicemi, proto se v inverzi, definičním oboru ani v oboru hodnot neobjeví.

90

ŘEŠENÍ CVIČENÍ

5.12. [α, a], [β, b] , (b) F A = [β, b], [γ, c] , (c) F A = [γ, c], [δ, d], [ε, e] .

1. (a) F A =

2. (a) F 00 A = {α, β}, (b) F 00 A = {β, γ}, (c) F 00 A = {γ, δ, ε . Prvky d, e (v případě (b)), b (v případě (c)) jsou v množině A „navícÿ, na výsledné zúžení F A nebo obraz F 00 A nemají vliv. 5.13. (a) R ◦ S =

[α, A], [α, B], [α, C], [β, B], [β, C], [γ, C] ,

[α, A], [α, B], [α, C], [β, A], [β, B], [β, C], [γ, A], [γ, B], [γ, C] , (c) R ◦ S = [α, A], [β, A], [β, B], [γ, A], [γ, B], [γ, C] .

(b) R ◦ S =

Uspořádané dvojice [α, d], [β, d], [γ, d], [δ, d] (v případě (a)) resp. [d, A], [d, B], [d, D] (v případě (b)) jsou v množině R resp. S „navícÿ, na výsledné složení R ◦ S nemají vliv. 5.14. Inkluze Rng(R◦ ◦ S) ⊆ Rng(R) je zřejmá, neboť obory hodnot Rng(R◦◦ S) a Rng(R) jsou tvořeny prvními složkami uspořádaných dvojic a protože relace resp. množina R uvedená na pravé straně inkluze je ve skládání R ◦ S první. Obdobně je zřejmá také inkluze Dom(R ◦ S) ⊆ Dom(S), neboť definiční obory Dom(R ◦ S) a Dom(S) jsou tvořeny druhými složkami uspořádaných dvojic a protože relace resp. množina S je ve skládání R ◦ S druhá. 1. Předpokládejme, že Dom(R) ⊆ Rng(S). Máme dokázat rovnost Rng(R ◦ ◦ S) = Rng(R). Vzhledem k tomu, že inkluze Rng(R ◦ S) ⊆ Rng(R) platí triviálně, stačí dokázat pouze inkluzi Rng(R ◦ S) ⊇ Rng(R). Je tedy třeba dokázat, že pro každý prvek x platí implikace x ∈ Rng(R) =⇒ x ∈ Rng(R ◦ S) . Avšak x ∈ Rng(R) právě tehdy, když existuje prvek y takový, že [x, y] ∈ R. Protože y ∈ Dom(R) ⊆ Rng(S), existuje prvek z takový, že [y, z] ∈ S. Vidíme, že [x, z] ∈ R ◦ S, tudíž x ∈ Rng(R ◦ S). 2. Předpokládejme, že Rng(S) ⊆ Dom(R). Stačí dokázat inkluzi Dom(R ◦ ◦ S) ⊇ Dom(S), tedy platnost implikace z ∈ Dom(S) =⇒ z ∈ Dom(R ◦ S) pro každý prvek z. Ovšem z ∈ Dom(S) právě tehdy, když existuje prvek y takový, že [y, z] ∈ S. Je tedy y ∈ Rng(S) ⊆ Dom(R), tudíž existuje prvek x takový, že [x, y] ∈ R. Následně [x, z] ∈ R ◦ S, odtud z ∈ Dom(R ◦ S).

91 5.15. 1. [z, x] ∈ (R ◦ S)−1 ⇐⇒ [x, z] ∈ R ◦ S ⇐⇒ ⇐⇒ ∃y: [x, y] ∈ R ∧ [y, z] ∈ S ⇐⇒ ⇐⇒ ∃y: [z, y] ∈ S −1 ∧ [y, x] ∈ R−1 ⇐⇒ ⇐⇒ [z, y] ∈ S −1 ◦ R−1 . 2. ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

[w, z] ∈ (R ◦ S) ◦ T ⇐⇒ ∃y: [w, y] ∈ R ◦ S ∧ [y, z] ∈ T ⇐⇒ ∃x, y: [w, x] ∈ R ∧ [x, y] ∈ S ∧ [y, z] ∈ T ⇐⇒ ∃x: [w, x] ∈ R ∧ [x, z] ∈ S ◦ T ⇐⇒ [w, z] ∈ R ◦ (S ◦ T ) .

5.16. Uvádím formální důkazy. Je však lepší si uvedené vztahy napřed rozmyslet – k tomu viz poznámku 5.14. 1. y ∈ F 00 (A ∪ B) ⇐⇒ ⇐⇒ ∃x: [y, x] ∈ F ∧ (x ∈ A ∨ x ∈ B) ⇐⇒ ⇐⇒ ∃x: [y, x] ∈ F ∧ x ∈ A ∨ [y, x] ∈ F ∧ x ∈ B ⇐⇒ ⇐⇒ ∃x: [y, x] ∈ F ∧ x ∈ A ∨ ∃x: [y, x] ∈ F ∧ x ∈ B ⇐⇒ ⇐⇒ y ∈ F 00 A ∨ y ∈ F 00 B ⇐⇒ ⇐⇒ y ∈ (F 00 A) ∪ (F 00 B) . 2. y ∈ F 00 (A ∩ B) ⇐⇒ ⇐⇒ ∃x: [y, x] ∈ F ∧ (x ∈ A ∧ x ∈ B) ⇐⇒ ⇐⇒ ∃x: [y, x] ∈ F ∧ x ∈ A ∧ [y, x] ∈ F ∧ x ∈ B =⇒ =⇒ ∃x: [y, x] ∈ F ∧ x ∈ A ∧ ∃x: [y, x] ∈ F ∧ x ∈ B ⇐⇒ ⇐⇒ y ∈ F 00 A ∧ y ∈ F 00 B ⇐⇒ ⇐⇒ y ∈ (F 00 A) ∩ (F 00 B) . 3. y ∈ (F 00 A) \ (F 00 B) ⇐⇒ ⇐⇒ y ∈ F 00 A ∧ y ∈ / F 00 B ⇐⇒ ⇐⇒ ∃x: [y, x] ∈ F ∧ x ∈ A ∧ ∀x: [y, x] ∈ /F ∨ x∈ / B =⇒ =⇒ ∃x: [y, x] ∈ F ∧ (x ∈ A ∧ x ∈ / B) ⇐⇒ 00 ⇐⇒ y ∈ F (A \ B) .

92

ŘEŠENÍ CVIČENÍ

5.17. 1. Jde o důsledek bodu 1. předcházejícího cvičení 5.16. – přestože F −1 nemusí být funkce (obecně je to pouze relace). Také lze postupovat přímo: x ∈ F −1 (A ∪ B) ⇐⇒ F (x) ∈ A ∪ B ⇐⇒ ⇐⇒ F (x) ∈ A ∨ F (x) ∈ B ⇐⇒ ⇐⇒ x ∈ F −1 (A) ∨ x ∈ F −1 (B) ⇐⇒ ⇐⇒ x ∈ F −1 (A) ∪ F −1 (B) . 2.

x ∈ F −1 (A ∩ B) ⇐⇒ F (x) ∈ A ∩ B ⇐⇒ ⇐⇒ F (x) ∈ A ∧ F (x) ∈ B ⇐⇒ ⇐⇒ x ∈ F −1 (A) ∧ x ∈ F −1 (B) ⇐⇒ ⇐⇒ x ∈ F −1 (A) ∩ F −1 (B) .

3.

x ∈ F −1 (A \ B) ⇐⇒ F (x) ∈ A \ B ⇐⇒ ⇐⇒ F (x) ∈ A ∧ F (x) ∈ / B ⇐⇒ ⇐⇒ x ∈ F −1 (A) ∧ x ∈ / F −1 (B) ⇐⇒ ⇐⇒ x ∈ F −1 (A) \ F −1 (B) . b, [a, b] ; a ∈ A, b ∈ B .

6.1.

pB =

6.2.

Zřejmé. Podívejte se do páté kapitoly na definici 5.6. operace Rng.

6.3. 1. Množina B A = (A → B) má 32 = 9 prvků. 2. Množina B A = (A → B) má nm prvků. 6.4. 1. Máme F (a) = 1, F (b) = 0, F (c) = 1, F (d) = 1, takže F = [1, c], [1, d] .

[1, a], [0, b],

2. X = {a, c}. 6.5.

První korespondenční úkol.

7.1. „≤ÿ =

[a, a], [b, b], [d, d], [e, e],

[a, b], [b, c], [d, e], [e, f ],

[a, c], [b, f ], [d, f ], [e, g],

[a, d], [b, g], [d, g], [e, h],

[a, e], [b, j ], [d, h], [e, i ],

[a, f ], [c, c], [d, i ], [e, j ],

[a, g], [a, j], [c, f ], [c, g], [c, j], [d, j ], [f , f ], [f , g], [f , j], [g, g], [g, j ], [h, h], [h, i ], [h, j ], [i, i ], [ i , j ], [j , j] .

93 7.2. a "" bb

d „≤ÿ =

" b " b

e

f

b c " b

g

[a, a], [b, b], [b, a], [c, c], [c, a], [d, d], [d, b], [d, a], [e, e], [e, b], [e, a], [f , f ], [f , c], [f , a], [g, g], [g, c], [g, a] .

7.3. Kdyby množina A byla prázdná, A = ∅, potom P(A) = {∅}. Kdyby množina A byla jednoprvková, A = {a}, pak P(A) = ∅, {a} . V obou případech však platí M = P(A) \ {∅, A} = ∅. Množina M je tedy prázdná. Proto v ní žádný minimální ani maximální prvek neexistuje. Pokud množina A je nekonečná, potom v systému M = P(A) \ {∅, A} najdeme nekonečně mnoho minimálních prvků – budou to všechny jednoprvkové podmnožiny množiny A – ale maximální prvek nenajdeme žádný.

7.4. 1. Když a ∈ M je největší prvek, pak m ≤ a pro každé m ∈ M . Je třeba dokázat, že a je maximálním prvkem, tzn., že pro každé m ∈ M splňující a ≤ m už platí a = m. Zvolme tedy prvek m ∈ M , pro který platí a ≤ m. Současně ale víme, že m ≤ a. Z antisymetrie plyne a = m. 2. Nechť a, b ∈ M jsou dva (ne nutně různé) největší prvky. Takže pro každé m ∈ M platí m ≤ a a m ≤ b. Odtud b ≤ a i a ≤ b, tudíž, pomocí antisymetrie, a = b.

7.5.

„≤ÿ =

b

d

a

c

[a, a], [a, b], [b, b], [c, c], [c, d], [d, d] .

Minimální prvky jsou a, c. Maximální prvky jsou b, d. Největší ani nejmenší prvky neexistují. Dvojice prvků, které nelze porovnat, jsou následující: a, c; a, d; b, c; b, d.

7.6.

Uspořádání množiny Z resp. N je znázorněno vlevo resp. vpravo:

94

ŘEŠENÍ CVIČENÍ .. . 2

.. . 3

1

2

0

1

−1 −2 .. . Množina Z žádný minimální ani maximální prvek nemá. Tudíž nemůže mít ani nejmenší nebo největší prvek. Množina N má nejmenší prvek 1. Tento prvek současně minimálním prvkem množiny N. Maximální prvek v množině N nenajdeme. Ani největší prvek proto nenajdeme. 7.7. 1. Např. M = {1, 2} a R = trická, není reflexivní.

[1, 2] . Pak R je na M tranzitivní a antisyme-

2. Např. M = {1, 2, 3} a R = [1, 1], [1, 2], [2, 2], [2, 3], [3, 3] . Pak R je na M reflexivní a antisymetrická, není tranzitivní. 3. Např. M = {1, 2} a R = [1, 1], [1, 2], [2, 1], [2, 2] . Potom R je na M reflexivní a tranzitivní, není antisymetrická. 7.8. Reflexivita: víme a ≥ a, ekvivalentně a ≤op a. Tranzitivita: víme, že z a ≥ b a b ≥ c plyne a ≥ c, ekvivalentně z a ≤op b a b ≤op c plyne a ≤op c. Antisymetrie: z a ≥ b a b ≥ a plyne a = b, ekvivalentně a ≤op b a b ≤op a plyne a = b. 8.1. Mějme n lineárně uspořádaných množin M1 , . . . , Mn . Na jejich kartézském součinu M = M1 × · · · × Mn zavedeme relaci lexikografického uspořádání „ÿ následovně: Nechť a, b ∈ M . Máme a = [a1 , . . . , an ] a b = [b1 , . . . , bn ], kde ai , bi ∈ Mi pro i = 1, . . . , n. Klademe a b právě tehdy, když a ≺ b nebo a = b. K tomu klademe a ≺ b právě tehdy, když existuje index i0 = 1, . . . , n takový, že ai = bi pro i = 1, . . . , i0 a ai0 < bi0 . Slovy můžeme říci, že platí a b právě tehdy, když uspořádané n-tice a a b se shodují v prvních (i0 − 1) složkách, v následující i0 -té složce platí vztah „<ÿ, a zbývající složky už mohou být libovolné. Reflexivita: a a. Zřejmé, neboť a = a. Tranzitivita: jestliže a b c, potom a c. Tranzitivita je zřejmá, jestliže a = b nebo b = c. Předpokládejme proto, že a 6= b 6= c. Existují tedy indexy i0 , j0 = 1, . . . , n tak, že ai = bi pro i = 1, . . . , i0 a ai0 < bi0 , obdobně bi = ci pro i = 1, . . . , j0 a bj0 < cj0 . Vezměmě k0 = min{i0 , j0 }. Potom ai = ci pro i = 1, . . . , k0 a ak0 < ck0 , takže a ≺ c. Antisymetrie: jestliže a b a, potom a = b. Zřejmé. Kdyby a 6= b, potom

95 by muselo platit a ≺ b ≺ a, tedy (stejně jako v důkazu tranzitivity) a ≺ a, což není možné. Je tedy a = b. 8.2.

Není. Např. prvky a a c nejsou porovnatelné.

9.1. Nechť a, b ∈ M jsou dva prvky, které jsou od sebe různé, přesto však vzájemně porovnatelné. Platí tedy vztah a < b nebo a > b. Bez újmy na obecnosti předpokládejme, že platí první vztah, a < b, protože jinak zaměníme označení obou prvků. Uvažujme množinu A = { x ∈ M ; a < x }. Množina A je jistě neprázdná, protože např. b ∈ A, avšak nemá první prvek. Ke každému x ∈ A totiž existuje prvek y ∈ A takový, že a < y < x, neboť uspořádání „≤ÿ je husté. Žádný prvek x ∈ A tedy nemůže být prvním prvkem množiny A (muselo by platit x ≤ y pro všechna y ∈ A). 9.2. Množina M není uspořádána ani hustě (např. není žádné x ∈ M , pro které by platilo a < x < b) ani dobře (např. množina A = {b, d} nemá první prvek). 9.3. Množina M je hustě uspořádána. (Když x, y ∈ M a platí x < y, pak například x < 21 (x + y) < y.) Množina M není dobře uspořádána. (Například množina A = (1, 2) – otevřený interval reálných čísel od 1 do 2 – nemá první prvek.) 9.4. Množina M není hustě uspořádána. (Například neexistuje žádné x ∈ M takové, aby a < x < b.) Množina M je dobře uspořádána. (Nechť je dána neprázdná množina A ⊆ M . Za prvek x dosazujme prvky množny M v pořadí a, b, c, d. Jakmile x ∈ A, pak x je prvním prvkem množiny A.) 10.1. 1.

S

2.

S

{1, 2, 3}, {5, 6, 7}, {3, 4, 5} = {1, 2, 3, 4, 5, 6, 7}.

∅ = ∅.

10.2. V množině M lze nalézt tyto řetězce: {a}, {b}, {a, b}, {c}, {d}, {c, d}. Všechny řetězce jsou shora omezené. Horní závorou prvních tří řetězců je prvek b, horní závorou ostatních tří řetězců je prvek d. Ano, množina M obsahuje maximální prvkek; maximálními prvky jsou jsou b a d. 11.1.

M/R = {1, 3, 5}, {2, 4} .

11.2.

R = [1, 1], [1, 2], [2, 1], [2, 2], [3, 3], [3, 4], [4, 3], [4, 4], [5, 5] .

13.1.

Druhý korespondenční úkol.

96

ŘEŠENÍ CVIČENÍ

Dodatek A: Obsah přednášek z UTELO 1. Intuitivní pojem množiny. Množiny zavedené výčtem svých prvků. Predikát náležení („∈ÿ) a nenáležení („∈ÿ). / Opakování prvků ve výčtu, změna pořadí prvků ve výčtu, (axiom extensionality). Množina prázdná (rozdíl oproti množině obsahující prázdnou množinu). 2. Další základní predikáty teorie množin: inkluze a ostrá inkluze. Inkluze a ostrá inkluze, pojem podmnožiny a vlastní podmnožiny. Triviální podmnožiny (množina prázdná a „celáÿ, tj. reflexivita inkluze). Potenční množina. 3. Základní množinové operace. Sjednocení, průnik a rozdíl dvou množin (tj. binární operace s množinami). De Morganova pravidla (důkaz obrázkem i pomocí ax. extensionality, metodou neurč. prvku). Zákon dvojí negace (C \ (C \ A) = A ∩ C) a distributivita (důkazy obrázkem i pomocí ax. extensionality, metodou neurč. prvku). Pojem disjunktních množin (binární predikát). 4. Neuspořádaná dvojice. Uspořádané dvojice. Pojem neuspořádané dvojice. Wienerova definice uspořádané dvojice. Věta o rovnosti dvou uspořádaných dvojic ([a, b] = [x, y] ⇐⇒ (a = x ∧ b = y)). Její důkaz. Pojem uspořádané trojice, čtveřice atd. 5. Další operace s množinami, další predikáty teorie množin. Kartézský součin dvou množin (A × B). Problém kartézského součinu více než dvou (ale konečně mnoha) množin (A × (B × C)). Relace (Rel(A)). Skládání relací, nebo i množin (R ◦ S). Zobrazení resp. funkce (Fnc(A)). Definiční obor funkce nebo relace, nebo i množiny (Dom(A)). Obor hodnot funkce nebo relace, nebo i množiny (Rng(A)). Inverze relace nebo funkce, nebo i množiny (A−1 ). Vzájemně jednoznačná funkce (Fnc−1 (F )). Funkce prostá a funkce na. Zúžení funkce, relace, nebo i množiny (F A). Obraz množiny přes funkci, nebo i množinu (F 00 A). Příklady. 6. Další pojmy. Kartézský součin a projekce. Množina všech zobrazení mezi dvěma množinami (B A neboli (A → B) neboli {A → B}). Vzájemně jednoznačný vztah (tj. vzájemně jednoznačné zobrazení) mezi potenční množinou a množinou všech zobrazení do dvouprvkové množiny ({0, 1}A ). 7. Vlastnosti relací. Relace částečného uspořádání. Relace na množině. Reflexivita, tranzitivita, antisymetrie relace na množině, porovnatelnost každých dvou prvků relací na množině. Relace částečného uspořádání, relace 97

98

DODATEK A:

OBSAH PŘEDNÁŠEK Z UTELO

lineárního uspořádání. Příklady částečně uspořádaných množin (inkluze na množině, spec. uspořádání potenční množiny inkluzí, dělitelnost přirozených čísel). Hasseovy diagramy. Příklady Hasseových diagramů (potenční množina prázdné, jedno-, dvou- a tříprvkové množiny s inkluzí, celá čísla a přirozená čísla se standardním uspořádáním). Nejmenší (první) prvek, minimální prvek, maximální prvek, největší (poslední) prvek množiny. Vztah mezi prvky nejmenšími a minimálními, vztah mezi prvky největšími a maximálními. Příklady nejm., min., max. a nejv. prvků (potenční množina s inkluzí, potenční množina aspoň dvouprvkové množiny bez množiny prázdné a celé s inkluzí, celá čísla a přirozená čísla se standardním uspořádáním). Relace opačná, tj. inverze (k relaci část. usp. je také relací částečného uspořádání). 8. Relace lineárního uspořádání. Příklad množiny uspořádané částečně ale ne lineárně (potence aspoň dvouprvkové množiny s inkluzí). Příklady lineárně uspořádaných množin (přirozená čísla, celá čísla a čísla racionální a reálná se standardním usp.). Další příklad: lexikografické uspořádání (na množině Rn pro n = 1, 2, 3, . . . , obecně na kartézském součinu konečně mnoha lineárně uspořádaných množin). 9. Uspořádání husté a dobré. Husté uspořádání (příklady množin, které nejsou hustě uspořádány, přirozená čísla, celá čísla, příklady hustě uspořádaných množin, racionální čísla, reálná čísla, vše se standardním uspořádáním). Dobré uspořádání (příklad dobře uspořádané množiny, přirozená čísla, příklady množin uspořádaných lineárně ale ne dobře, celá čísla, nezáporná racionální čísla, racionální čísla, reálná čísla, vše se standardním uspořádáním). 10. Částečné uspořádání – další pojmy. Horní závora, dolní závora, supremum, infimum. Polosvaz spojový a průsekový. Svaz – svazové uspořádání. Příklady množin shora omezených a neomezených. Příklady množin shora omezených nemajících supremum. Řetězec. Řetězec shora omezený. Zornovo lemma (bez důkazu). (Možná také: Selektor. Axiom výběru (bez důkazu). Princip dobrého uspořádání (bez důkazu). (Ekvivalence Zornova lemmatu, axiomu výběru a principu dobrého uspořádání.)) 11. Vlastnosti relací. Relace ekvivalence. Relace na množině. Relace reflexivní, tranzitivní a symetrická na množině. Relace ekvivalence. Třída ekvivalence určená prvkem. Základní vlastnosti tříd ekvivalence (x ∈ [x]R , takže [x]R 6= ∅; jestliže x ∈ [y]R , potom y ∈ [x]R ; buď [x]R ∩ [y]R = ∅, anebo [x]R = [y]R ; nadto [x]R = [y]R , právě když xRy). Vlastnosti množiny tříd ekvivalence (jedna množina tříd ekvivalence podmnožinou jiné, právě když jedna relace ekvivalence na množině podmnožinou jiné; důsledek: dvě množiny tříd ekvivalence jsou si rovny, právě když relace ekvivalence na množině jsou si rovny). Příklady relací ekvivalence (identita, množina vázaných vektorů (tj. orientovaných úseček) a relace ekvipolence (rovnoběžné a stejná délka i orientace) na ní, kde třída ekvivalence je volný vektor, křivková souvislost množiny bodů v rovině, reprezentace spojitých křivek, ekvivalence znamená reprezentace stejné křivky, kongruence na množině celých čísel, celá čísla, zlomky). Rozklad množiny. Vztah mezi relací ekvivalence a rozkladem na třídy ekvivalence.

99 12. Poznámka o kvaziuspořádání. Kvaziuspořádání. Relace ekvivalence určená kvaziuspořádáním a částečné uspořádání vzniklých tříd ekvivalence. 13. Mohutnost množin. Ekvivalence (tj. stejná mohutnost množin). Subvalence a ostrá subvalence. Symetrie ekvivalence, reflexivita a tranzitivita ekvivalence a subvalence, tranzitivita ostré subvalence. Cantorova-Bernsteinova věta (bez důkazu). Příklady: Ekvivalence množin N a N0 . Ekvivalence množin N0 a Z. Ekvivalence množin N a N × N. Ekvivalence množin N a Q+ a Q. Nemožnost ekvivalence množin N a h0, 1i. Ekvivalence přímky, (otevřené) půlkružnice a (otevřené) úsečky. Ekvivalence množin h0, 1i a h0, 1i × h0, 1i – pomocí Cantorovy-Bernsteinovy věty.

100

DODATEK A:

OBSAH PŘEDNÁŠEK Z UTELO

Dodatek B: Cvičení ze základů teorie množin Po přečtení třetí kapitoly těchto skript se můžete pokusit o následující cvičení: Cvičení B.1. Nechť A, B a C jsou množiny. Odůvodněte platnost následujících tvrzení. Srovnejte je se známými užitečnými tautologiemi z výrokové logiky. Povšimněte si, že logické spojce „∧ÿ odpovídá množinová operace „∩ÿ; logické spojce „∨ÿ odpovídá množinová operace „∪ÿ; logické spojce „¬ÿ odpovídá množinová operace „C \ · ÿ, kde C je nějaká množina; logické spojce „⇒ÿ odpovídá predikát „⊆ÿ; logické spojce „⇔ÿ (či „≡ÿ) odpovídá predikát „=ÿ. De Morganova pravidla: 1. C \ (A ∪ B) = (C \ A) ∩ (C \ B), 2. C \ (A ∩ B) = (C \ A) ∪ (C \ B). Zákon dvojí negace: 3. C \ (C \ A) = A ∩ C

— a jestliže A ⊆ C, potom A ∩ C = A.

Jako cvičení dokažte: 4. A \ B = A \ (A ∩ B). Distributivita: 5. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), 6. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Komutativita: 7. A ∩ B = B ∩ A, 8. A ∪ B = B ∪ A. Asociativita: 9. A ∩ (B ∩ C) = (A ∩ B) ∩ C, 10. A ∪ (B ∪ C) = (A ∪ B) ∪ C. 101

102

DODATEK B:

CVIČENÍ ZE ZÁKLADŮ TEORIE MNOŽIN

Idempotence: 11. A ∩ A = A, 12. A ∪ A = A. Absorpce: 13. A ∩ (A ∪ B) = A, 14. A ∪ (A ∩ B) = A. Dvě trivialitky, které žádné zvláštní jméno nemají: 15. A ∩ B ⊆ A, 16. A ⊆ A ∪ B. Obdobně platí: 150. A ∩ B ⊆ B, 160. B ⊆ A ∪ B. Jako cvičení dále dokažte: 17. A \ B ⊆ A,

— srov. 15.

4. A \ B = A \ (A ∩ B), 18. A \ B = (A ∪ B) \ B, 19. A \ (B ∪ C) = (A \ B) \ C,

— srov. 1.

20. A \ (B \ C) = (A \ B) ∪ (A ∩ C), 190. (A \ B) \ C = A \ (B ∪ C), 21. (A ∪ B) \ C = (A \ C) ∪ (B \ C), 22. (A ∩ B) \ C = (A \ C) ∩ (B \ C). — — — Někdy se pracuje také s tzv. symetrickým rozdílem množin. Symetrický rozdíl (používáme též název symetrická diference) dvou množin A a B značíme A 4 B a zavádíme jej pomocí následujícího vztahu: A 4 B = (A \ B) ∪ (B \ A) = = (A ∪ B) \ (A ∩ B) . (Nakreslete si obrázek.) Symetrický rozdíl nám může pomoci odpovědět na otázku „ jak moc se dvě množiny od sebe lišíÿ.

103 Cvičení B.2. Ověřte platnost následujících vztahů, kde A, B a C jsou množiny: 1. A 4 A = ∅, 2. A 4 B = B 4 A, 3. A 4 (B 4 C) = (A 4 B) 4 C, 4. A ∩ (B 4 C) = (A ∩ B) 4 (A ∩ C). Cvičení B.3. Platí pro libovolné tři množiny A, B, C také následující vztahy? 1. A ∪ (B 4 C) = (A ∪ B) 4 (A ∪ C) ? 2. A 4 (B ∩ C) = (A 4 B) ∩ (A 4 C) ? 3. A 4 (B ∪ C) = (A 4 B) ∪ (A 4 C) ? [Obecně neplatí. Odůvodněte.] Cvičení B.4. Dokažte, že pro libovolné tři množiny A, B, C platí (A 4 B) ∪ (A 4 C) = (A ∪ B ∪ C) \ (A ∩ B ∩ C) . — — — Kartézský součin dvou množin už znáte. V páté kapitole těchto skript jsme kartézský součin dvou množin A a B označili A × B a zavedli jsme jej vztahem A × B = [x, y] ; x ∈ A, y ∈ B . Cvičení B.5. Nahlédněte platnost následujících vztahů pro libovolné tři množiny A, B, C : 1. A × (B ∪ C) = (A × B) ∪ (A × C), 2. A × (B ∩ C) = (A × B) ∩ (A × C). Cvičení B.6. Budiž dány libovolné čtyři množiny A, B, C, D. Nahlédněte, že platí také následující vztahy: 1. (A ∪ B) × (C ∪ D) = (A × C) ∪ (A × D) ∪ (B × C) ∪ (B × D), 2. (A ∩ B) × (C ∩ D) = (A × C) ∩ (A × D) ∩ (B × C) ∩ (B × D). Nahlédněte, že rovněž následující vztahy platí: 3a. (A ∪ B) × (C ∩ D) = (A × C) ∩ (A × D) ∪ 3b. (A ∪ B) × (C ∩ D) = (A × C) ∪ (B × C) ∩ 4a. (A ∩ B) × (C ∪ D) = (A × C) ∩ (B × C) ∪ 4b. (A ∩ B) × (C ∪ D) = (A × C) ∪ (A × D) ∩

(B × C) ∩ (B × D) , (A × D) ∪ (B × D) , (A × D) ∩ (B × D) , (B × C) ∪ (B × D) .

Cvičení B.7. Platí i následující vztahy, kde A, B a C jsou množiny? 1. (A × B) ∪ C = (A ∪ C) × (B ∪ C) ? 2. (A × B) ∩ C = (A ∩ C) × (B ∩ C) ? [Obecně neplatí.]

104

DODATEK B:

CVIČENÍ ZE ZÁKLADŮ TEORIE MNOŽIN

Vysvětlivky k používaným symbolům Průvodce studiem – vstup autora do textu, specifický způsob, kterým se studentem komunikuje, povzbuzuje jej, doplňuje text o další informace. Příklad – objasnění nebo konkretizování problematiky na přikladu ze života, praxe, společenské reality apod. Pojmy k zapamatování. Shrnutí – předcházející látky, kapitoly. Literatura – použitá ve studijním materiálu, pro doplnění a rozšíření poznatků. Kontrolní otázky a úkoly – prověřují, do jaké míry studující text a problematiku pochopil, zapamatoval si podstatné a důležité informace a zda je dokáže aplikovat při řešení problémů. Úkoly k textu – je potřeba je splnit neprodleně, neboť pomáhají dobrému zvládnutí následující látky. Korespondenční úkoly – při jejich plnění postupuje studující podle pokynů s notnou dávkou vlastní iniciativy. Úkoly se průběžně evidují a hodnotí v průběhu celého kursu. Úkoly k zamyšlení. Část pro zájemce – přináší látku a úkoly rozšiřující úroveň základního kursu. Pasáže a úkoly jsou dobrovolné. Testy a otázky – ke kterým řešení, odpovědi a výsledky studující najde v rámci studijní opory. Řešení a odpovědi – vážou se na konkrétní úkoly, zadání a testy. 105

Úvod do teorie množin a logiky 2

Recommend Documents