Úvod do teorie množin a logiky. David Bartl

Úvod do teorie množin a logiky David Bartl

2

Místo předmluvy Dovoluji si na tomto místě jen skromně poznamenat, že (ačkoliv autor těchto skript) nejsem specialistou na teorii množin. Mohu předat dál jen to, co jsem se sám naučil. Rád bych proto poděkoval svým učitelům matematiky. Zejména bych chtěl poděkovat panu Prof. RNDr. Petru Vopěnkovi, DrSc. Zde podaný přístup k teorii množin do značné míry vychází z jeho pozoruhodných přednášek o úvodních partiích tohoto předmětu, které jsem měl příležitost navštěvovat. Rovněž bych rád poděkoval panu Prof. RNDr. Petru Štěpánkovi, DrSc., na jehož přednáškách se mi dostalo příležitosti získat potřebné znalosti (klasické) logiky. V neposlední řadě bych za obětavou pomoc rád poděkoval panu RNDr. Ladislavu Mišíkovi, CSc., a Mgr. Pavlíně Kukulišové, bez jejichž podpory by napsání těchto skript nebylo možné.

V Ostravě dne 28. listopadu 2003 David Bartl

3

4

Obsah Místo předmluvy

3

1 První seznámení s teorií množin

7

2 Úvod do logiky 19 2.1 Stručný úvod do výrokové logiky . . . . . . . . . . . . . . . . . . 19 2.2 Stručný úvod do predikátové logiky . . . . . . . . . . . . . . . . . 26 3 Axiomy teorie množin 39 3.1 Jazyk teorie množin . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Zermelův-Fraenkelův axiomatický systém teorie množin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4 Mohutnost (kardinalita) množin

59

Použitá literatura

65

5

6

OBSAH

Kapitola 1

První seznámení s teorií množin 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 7

8

KAPITOLA 1. PRVNÍ SEZNÁMENÍ S TEORIÍ MNOŽIN

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 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. Na pří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ů.

9 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}, 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 silně zdůraznili, že třetí možnost není, protože na první pohled se to zdá být samozřejmé. Zanedlouho se však seznámíme s tzv. Russellovým paradoxem, který ve své době v matematice způsobil hlubokou krizi. 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í.

10


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 je 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 extensionality). A v místě zpochybňujícího otazníčku jsme použili právě uvedený 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.

11 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, množ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! — — — Všechny množiny, které jsme si až dosud v příkladech uváděli, byly konečné. Zaměřme nyní svoji pozornost např. na množinu prvních deseti přirozených čísel {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. K této množině můžeme přidat ještě číslo 11: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Dále můžeme pokračovat přidáním čísla 12 a získat tak množinu {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. A tak dále. Obecně, když n je přirozené číslo, pak k n-prvkové množině {1, 2, 3, . . . , n}

12


můžeme přidat další prvek, totiž přirozené číslo n + 1, a obdržet množinu {1, 2, 3, . . . , n, n + 1}, která obsahuje n + 1 prvků. Vidíme, že tento proces se nemusí nikdy zastavit. Velikost množin konstruovaných podle tohoto návodu není shora omezená. (Velikostí množiny zde máme na mysli počet jejích prvků.) Jde o tzv. potenciální nekonečno. V případě potenciálního nekonečna je nekonečnost způsobena tím, že k dané (výchozí konečné) množině lze neustále přidávat další a další prvky. Je však jasné, že k „limitěÿ, tedy k množině, která by obsahovala všechny prvky, jež je možné přidat, nelze dospět v konečném čase. Taktéž, i kdyby taková „limitníÿ množina existovala, nebylo by možné v konečném čase všechny její prvky vyjmenovat, neboli uvést výčet všech jejích prvků. — — — Čtenář jistě zná ze školy (střední nebo základní) množinu všech přirozených čísel {1, 2, 3, 4, 5, . . .}. Oproti dříve uvedeným příkladům zde zaznamenáváme jeden rozdíl: tato množina není konečná. Na tomto místě se setkáváme s tzv. aktuálním nekonečnem. Uvedená množina už totiž nekonečná je a není potřeba k ní cokoliv přidávat. (Uvedu jednu „filosofickouÿ poznámku. Snad se mi podaří ještě trochu jiným způsobem vysvětlit rozdíl mezi nekonečnem potenciálním a aktuálním. Uvažujme množinu přirozených čísel {1, 2, 3, . . .}. Když se snažíme vyjmenovat všechny její prvky (na tuto množinu se díváme „zevnitřÿ), dostáváme potenciální nekonečno. Proces vyjmenovávání prvků nemůže nikdy skončit, stále vyjmenováváme další a další prvky. Když se ale na tuto množinu díváme „zvnějškuÿ (bereme ji jako hotový, skončený celek) máme aktuální nekonečno. — Tato úvaha samozřejmě není omezena jen na množinu přirozených čísel, bylo by možné ji vykonat s jakoukoliv (již aktuálně) nekonečnou množinou. A možná třeba by šlo vymyslet i příklady jiného typu.) S aktuálně nekonečnými množinami jsou ale spojeny jisté potíže. Podívejme se na následující úvahu, kde pracujeme opět s množinou přirozených čísel {1, 2, 3, . . .}. My samozřejmě máme svoji intuitivní představu o tom, co je to přirozené číslo. Když nám někdo předloží nějaký objekt, jsme (intuitivně) schopni rozpoznat, zda tento objekt je přirozené číslo, a tudíž i to, zda tento objekt patří do množiny přirozených čísel. (Množina přirozených čísel tak je, alespoň intuitivně, dobře určena. O každém objektu jsme schopni říci, zda do této množiny patří, nebo ne.) Představme si ale, že někdo by chtěl čistě mechanicky (už nikoliv intuitivně) rozpoznávat, zda předložený objekt patří do množiny přirozených čísel. Pak ovšem nezbývá nic jiného, než uvést seznam (byť nekonečný) všech prvků dané množiny. Nechť n nyní je přirozené číslo. Dotyčná osoba pak může procházet

13 seznam prvků množiny přirozených čísel a prvky ze seznamu postupně porovnávat s předloženým objektem n. Dříve či později osoba ověří, že daný prvek n patří do množiny přirozených čísel. — Předpokládejme nyní, že objekt x není přirozené číslo. Danou osobu opět necháme procházet seznam prvků množiny přirozených čísel a porovnávat je s předloženým objektem x. Je jasné, že osoba v konečném čase (po prozkoumání pouze konečné části seznamu) není schopna říci, zda prvek x patří do množiny přirozených čísel. Uvědomte si, že z faktu, že prvek x nebyl uveden v konečné (tj. dosud prozkoumané) části seznamu, nic nevyplývá! Prvek x totiž může být uveden v následující (zatím ještě neprozkoumané – z důvodu nedostatku času) části seznamu. Anebo na seznamu nemusí být uveden vůbec! Proto v konečném čase nelze rozhodnout, zda prvek x do množiny přirozených čísel patří, nebo ne. Vidíme, že existují objekty (totiž objekty x, které nejsou přirozenými čísly), o nichž nelze rozhodout (nechceme-li se spoléhat na svoji intuici), zda do množiny přirozených čísel patří, nebo ne. Takže lze mít i vážné pochybnosti o tom, že množina přirozených čísel je dobře určena. Následně se lze začít ptát, zda vůbec můžeme pracovat s množinou, která vlastně není dobře určena. A když množina není dobře určena, je to ještě množina? Naši úvahu tak zakončíme zpochybněním samotné existence množiny přirozených čísel. . . (Někteří matematici odmítají s aktuálně nekonečnými množinami pracovat. V případě množiny přirozených čísel jsou ochotni udělat jedinou výjimku – spoléhají na svoji přirozenou intuici pro přirozená čísla. Jinak pracují pouze s potenciálním nekonečnem.) — — — Výše uvedenou úvahou jsme zpochybnili existenci množiny přirozených čísel. Obdobnou úvahou by ale bylo možné zpochybnit existenci libovolné (již aktuálně) nekonečné množiny. Naskýtá se proto otázka, zda aktuálně nekonečné množiny vůbec existují. Poměrně zajímavý důkaz existence aktuálně nekonečné množiny podal v 1. polovině 19. století český učenec Bernard Bolzano1 (1781–1848). Důkaz. (Bolzano.) Označme jako výrok A1 sentenci: „Existuje alespoň jedna pravda (o sobě).ÿ Uvedený výrok A1 je nesporně pravdivý. Kdyby totiž pravdivý nebyl, potom by platilo, že „neexistuje žádná pravdaÿ. Výrok „neexistuje žádná pravdaÿ by byl pravdivý, byla by to pravda. Takže výrok A1 („existuje alespoň jedna pravdaÿ) by nakonec přeci jenom byl pravdivý (spor s předpokladem, že A1 není pravdivý). Ukázali jsme, že výrok A1 je pravdivý. Jako výrok A2 označme sentenci: „Výrok A1 je pravdivý.ÿ Je zřejmé, že výrok A2 je pravdivý. 1 Bernard Bolzano se věnoval filosofii i matematice. Jako jeden z prvních se zabýval systematičtějším studiem množin (ve smyslu „souhrnu věcíÿ). Pozoruhodné jsou také jeho pionýrské práce v oblasti reálných funkcí. S jeho jménem je spojena také tzv. Bolzanova-Cauchyova podmínka konvergence. Čtenáři se s touto podmínkou jistě brzy seznámí v kursu matematické analýzy.

14


Jako výrok A3 označme sentenci: „Výrok A2 je pravdivý.ÿ Je zřejmé, že výrok A3 je pravdivý. Atd. Jako výrok An+1 označme sentenci: „Výrok An je pravdivý.ÿ Je zřejmé, že výrok An+1 je pravdivý. Atd. Jenomže Bůh je vševědoucí. Tím pádem zná všechny pravdy. Tedy i nyní uvedené pravdy. Tyto pravdy v Boží mysli vytvářejí aktuálně nekonečnou množinu. Q. E. D. Uvedený důkaz nás svojí krásou a svojí vnitřní promyšleností může udivit ještě dnes. Z teologického hlediska proti tomuto důkazu nelze vůbec nic namítat. Skutečnost, že do důkazu bylo potřeba zaplést Boha, posouvá otázku existence aktuálního nekonečna do filosofické roviny. (Z matematického hlediska to vlastně důkaz není.) Vskutku, čtenář později uvidí, že v teorii množin se existence aktuálně nekonečné množiny zkrátka postuluje jako axiom. Bez tohoto axiomu (tj. axiomu o tom, že existuje alespoň jedna nekonečná množina) není možné existenci aktuálně nekonečné množiny dokázat žádným seriózním způsobem! Existenci aktuálně nekonečných množin (chceme-li s nimi pracovat) tak musíme předpokládat. — — — Na Bolzana navázal Georg Cantor2 (1845–1918). (Poznámka. Bernard Bolzano za svého života napsal pojednání o množinách. Jeho dílo však bylo v té době nepochopeno nebo pochopeno špatně, jak se dnes všeobecně soudí. Proto vyšlo tiskem až po Bolzanově smrti, v roce 1851. Tehdejší nakladatel ovšem v dobré snaze opravit domnělé Bolzanovy omyly v díle provedl několik úprav. Tato skutečnost dnes velmi ztěžuje porozumění původním Bolzanovým myšlenkám v oblasti prvopočátků teorie množin. Autor si není jist, zda Cantor navázal na Bolzana přímo v tom smyslu, že četl jeho práci. O návaznosti ale beze sporu hovořit můžeme.) Cantor pracoval s pojmem množiny všech množin. Následujme Cantorovy myšlenky a označme písmenem M množinu všech množin. (M – velké písmeno M psané německou frakturou.) Předpokládáme tedy, že M je množina a že každá množina je jejím prvkem. 2 Georg Cantor byl německý matematik. Položil základy 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. Ačkoliv Cantor toužil působit na univerzitě v Berlíně, musel se spokojit s místem na méně známé univerzitě v Halle. Cestu na berlínskou univerzitu měl uzavřenu díky Leopoldu Kroneckerovi, který tam pracoval. Kronecker byl ve své době významným matematikem a měl proto i značný vliv. Cantorovy převratné myšlenky však tvrdošíjně odmítal a dokonce proti nim veřejně nahlas vystupoval. Přestože konflikt mezi Cantorem a Kroneckerem přispěl k pozdějšímu rozvoji konstruktivistického pojetí matematiky (zastávaného zpočátku Kroneckerem, poté rozvinutého Brouwerem), dopady tohoto konfliktu byly pro Cantora dosti tragické.

15 Speciálně tedy musí platit M ∈ M. (Předpokládáme, že M je množina. Dále, M obsahuje všechny množiny. Tedy musí platit M ∈ M.) Obecně platí (ve skutečnosti jde o další axiom teorie množin, tzv. axiom vydělení), že pokud je dána libovolná množina M (zde máme M = M), potom můžeme pracovat také s množinou všech jejích prvků splňujících nějakou předem danou vlastnost ϕ(x). Množinu prvků x množiny M splňujících podmínku ϕ(x) označme znakem N . Máme tedy N=

©

ª x ; x ∈ M ∧ ϕ(x) .

(Zápis ϕ(x) zde označuje nějakou podmínku, nějaký výrok o proměnné x. Výrok ϕ(x) může být např. „x je sudéÿ. Potom N je množina těch prvků x množiny M , které jsou sudé. Anebo výrok ϕ(x) může být např. „x je racionální čísloÿ. Potom by N bylo rovno množině všech racionálních čísel, která současně patří do množiny M . A tak dále.) V roce 1902 si Bertrand Russell3 (1872–1970) povšimnul těžkého rozporu. Jeho úvaha později vešla ve všeobecnou známost jako tzv. Russellův paradox. Popišme, v čem jeho 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 3 Bertrand Russell 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 Russellem: „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.

16


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. (Poznámka. Nechť M je množina všech množin, zavedená Cantorem. Potom, podle axiomu vydělení, můžeme pracovat také s množinou N těch množin X, které neobsahují sebe sama: N = {X ; X ∈ M ∧ X ∈ / X }. Platí N ∈ N, nebo ne? Podmínka ϕ(X), pomocí které jsme prvky z množiny M vydělovali, je X ∈ / X. Čtenář se možná pozastaví nad podivností takové podmínky ϕ(X). Nicméně podmínka X ∈ / X podmínkou je, a množina N – za předpokladu existence množiny M – je proto korektně zavedena.) — — — Domnívám se, že na tomto místě bude účelné vložit poznámku o konvencích, které se při označování prvků množin obvykle 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ř. již zmíněné 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. — — —

17 Russellův paradox otřásl samotnými základy matematiky. A brzy po něm se začaly objevovat i další paradoxy. To na počátku 20. století bylo příčinou hluboké krize v matematice. Matematici byli zaskočeni, s jakou lehkostí bylo možné takové paradoxy tvořit. Veškerá matematická jistota byla pryč. Jako odpověď na tuto krizi se v matematice objevily následující tři (filosofické) směry: Formalismus. Jeho duchovním otcem je slavný německý matematik David Hilbert4 (1862–1943). Cílem je matematiku formalizovat, oprostit matematické symboly od jejich fyzikálního (nebo jiného) významu a se symboly pouze malipulovat podle předem přesně daných pravidel formálního usuzování. Konečným Hilbertovým cílem (tzv. Hilbertův program) bylo tímto způsobem prokázat též vnitřní konzistenci matematiky (tj. nepřítomnost paradoxů, jestliže se matematika postaví na formálním usuzování). Ačkoliv se později ukázalo, že tento poslední Hilbertův cíl není možné naplnit, své zastánce má formalismus dodnes. Intuicionismus. Tento přístup byl rozvinut Luitzenem Brouwerem5 (1881– 1966). Tento směr úzce souvisí s konstruktivismem – odmítá zákon vyloučeného třetího (důkazy existence sporem, protože jde o nekonstruktivní postup) i aktuální nekonečno. Chceme-li s nějakým objektem pracovat, musíme nejprve konstruktivně dokázat jeho existenci. Je potřeba popsat konečný počet kroků, jimiž lze daný objekt sestrojit. Správnost konstrukcí se ověří intuitivní zřejmostí. Okleštěný novopositivismus. Jde o poměrně jednoduchý přístup. Existenci Russellova paradoxu (a ostatních paradoxů) jen vezmeme na vědomí. Nebudeme je vytvářet, při své práci se jim budeme pokud možno vyhýbat. (Nakonec, přítomností nebo nepřítomností uvedených paradoxů v matematice se až tak mnoho nezmění. Lidé kvůli nim nepřestanou sčítat a násobit čísla osvědčeným způsobem, jehož správnost již byla ověřena staletími praxe. Ani matematik nepřestane hloubat (na příklad) nad vlastnostmi spojitých funkcí a nezačně pochybovat o tvrzeních, jejichž pravdivost svým logickým úsudkem sám ověřil.)

4 David Hilbert pracoval na univerzitě v Göttingenu, tehdy nejvýznamnějším centru matematického dění v Evropě. Nějakým způsobem přispěl snad ke každé oblasti matematiky. Rozsah jeho znalostí byl ohromující. Významné jsou jeho příspěvky v oblasti algebry, teorie čísel, (funkcionální) analýzy, geometrie a logiky. V roce 1900 na celosvětovém kongresu matematiků v Paříži přednesl svůj slavný seznam 23 matematických problémů (dodnes známy jako tzv. Hilbertovy problémy). Jeho výběr problémů je obdivuhodný: práce na řešení každého z těchto problémů často znamenala založení nového oboru matematiky. Některé z Hilbertových problémů jsou dosud nevyřešeny. 5 Luitzen Brouwer byl holandský matematik. Věnoval se topologii (prakticky je jejím zakladatelem) a teorii grup. Velmi nahlas prosazoval svoje intuicionistické pojetí matematiky. Později se kvůli názorovým rozdílům dostal i do ostrého konfliktu s Hilbertem (prosazujícím formalismus), ve kterém padlo mnoho jízlivostí. Jejich rozepře vlastně byla žabomyší válkou. Americký matematik John Hays totiž později napsal úsměvnou bajku, ve které vystupuje žabák (Brouwer) a myšák (Hilbert).

18


Kapitola 2

Úvod do logiky Nejstarším pokusem o modelování a zkoumání zákonitostí vnímání a usuzování je logika. Jde o logiku založenou na dvouhodnotové interpretaci pojmu pravdivosti. Tvrzení, jímž se zabývá muže být buď pravdivé nebo nepravdivé. Jiná možnost neexistuje. My se budeme zabývat dvěma základními typy logiky – výrokovou logikou a logikou predikátovou, neboli logikou prvního řádu. Jazyk výrokové a predikátové logiky je nezbytnou součástí teoretické i aplikované matematiky a informatiky. Je třeba si ale uvědomit, že tyto logiky pracují s řadou zjednodušení a omezení, která závisí na zvoleném abstraktním modelu. Proto ještě zdaleka nevystihují všechno to, čím se vyznačuje logika skutečného lidského myšlení. Je vůbec některá z formálních logik schopna svým jazykem podchytit způsob lidského uvažování, na kterém se podílí i intuice? Proč tedy vytváříme zjednodušující modely s jejich jazyky, když máme jazyk přirozený, který má větší schopnost zachytit způsob lidského myšlení? Protože přirozený jazyk je až moc bohatý a často používá vícevýznamové výrazy a podtextové významy a formulace pravidel používání takových nástrojů komunikace by byla velmi obtížná.

2.1

Stručný úvod do výrokové logiky

Výroková logika je jedním z nejjednodušších modelů lidského myšlení. Je postavena na zjednodušení, které spočívá v tom, že sémantika, neboli interpretace, výroků je redukována pouze na jejich pravdivostní hodnoty – pravda (1, true, T) a nepravda (0, false, F). Jinak řečeno, modelovaný svět, reprezentovaný množinou výroků, které jej popisují, se zredukuje na dvouprvkovou množinu {0, 1}. Vyjadřovací prostředek, tedy nástroj modelování je jazyk výrokové logiky a jeho syntax (symboly – abeceda – a konstrukční – syntaktická – pravidla) a sémantika s pravidly interpretace. 19

20

KAPITOLA 2. ÚVOD DO LOGIKY

Symboly jazyka výrokové logiky Symboly pro proměnné:

a, b, c, . . . , x, y, z, x1 , x2 , x3 , . . .

Symboly pro logické konstanty:

true – ozn. T, 1, false – ozn. F, 0.

Symboly pro logické spojky:

¬ – negace, ∧ – konjunkce ∨ – disjunkce ⇒ – implikace ⇔ – ekvivalence

Pomocné symboly:

závorky, . . .

Logické spojky ¬

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 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í: ↔ , ≡ .

Syntaktická pravidla Atomické formule jsou symboly pro logické proměnné a logické konstanty, ze kterých se vytváří další formule podle následujících pravidel: 1. Základní pravidlo. Každá atomická formule je formulí. 2. Indukce. Jsou-li A a B formule, pak ¬A, jsou formule.

A ∧ B,

A ∨ B,

A ⇒ B,

A⇔B

2.1. STRUČNÝ ÚVOD DO VÝROKOVÉ LOGIKY

21

3. Generalizace. Všechny dobře utvořené formule jazyka jsou výsledkem konečného počtu aplikací základního pravidla a pravidla indukce. Poznámka 2.1. Symboly A, B nepatří do jazyka výrokové logiky, ale pouze zastupují jeho libovolné formule. Definovat syntax jazyka obecně nelze jazykem samotným, ale je potřeba použít metajazyka, tedy jazyka přirozeného. Symboly A, B jsou tedy metasymboly.

Interpretace Interpretací rozumíme ohodnocení (valuaci) atomických formulí a interpretace složených formulí, tj. přiřazení některé z logických hodnot pravda (true) nebo nepravda (false), a to použitím interpretačních pravidel.

Interpretační pravidla Unární spojka negace: A 0 1

¬A 1 0

Binární spojky: A 0 0 1 1

B 0 1 0 1

A∧B 0 0 0 1

A∨B 0 1 1 1

A⇒B 1 1 0 1

A⇔B 1 0 0 1

Pomocí interpretačních pravidel dokážeme ohodnotit všechny proměnné libovolné formule. A na základě tohoto ohodnocení dokážeme říci, zda je daná formule splnitelná. Formule je splnitelná, jestliže existuje takové ohodnocení jejích proměnných, při němž je formule interpretována jako pravdivá. Formule je platná – tautologie, jestliže její interpretace při každém ohodnocení jejích proměnných je pravda. Kontradikce je nesplnitelná formule, tj. taková, že je vždy interpretována jako nepravda nezávisle na ohodnocení proměnných. Příklad 2.1. Interpretujte tabulkou formuli (A ⇔ B) ⇒ (A ∧ B) a rozhodněte o její splnitelnosti. Řešení. A 0 0 1 1

B 0 1 0 1

A⇔B 1 0 0 1

A∧B 0 0 0 1

(A ⇔ B) ⇒ (A ∧ B) 0 1 1 1

22


Formule je splnitelná.

¤

Užitečné tautologie Pro logické spojky interpretované podle uvedených pravidel platí následující zákony (tautologie): Identita p ⇐⇒ p. Idempotence (p ∧ p) ⇐⇒ p, (p ∨ p) ⇐⇒ p. Zákon dvojí negace p ⇐⇒ ¬¬p. Zákon vyloučeného třetího ¬p ∨ p. De Morganova1 pravidla ¬(p ∨ q) ⇐⇒ (¬p ∧ ¬q), ¬(p ∧ q) ⇐⇒ (¬p ∨ ¬q). Zákon komutativity (p ∧ q) ⇐⇒ (q ∧ p), (p ∨ q) ⇐⇒ (q ∨ p). Zákon asociativity p ∧ (q ∧ r) ⇐⇒ (p ∧ q) ∧ r, p ∨ (q ∨ r) ⇐⇒ (p ∨ q) ∨ r. Zákon distributivity p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r). Absorpce p ∧ (p ∨ q) ⇐⇒ p, p ∨ (p ∧ q) ⇐⇒ p. 1 Augustus

de Morgan – britský matematik 19. století.


23

Další logické spojky Existují však i jiné logické spojky. Následující tabulka nám poskytuje přehled pravdivostních hodnot všech logických spojek. AB 00 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

AB 01 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

AB 10 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

AB 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

kontradikce konjunkce A ∧ B A B XOR, A ⊕ B disjunkce, A ∨ B NOR, A ↓ B ekvivalence, A ⇔ B ¬B ¬A implikace, A ⇒ B NAND, A ↑ B tautologie

Tuto tabulku jsme sestavili mechanicky – ve dvojkové soustavě v každém řádku přičítáme jedničku. V takto sestavené tabulce je druhá polovina symetrická podle negace: znegováním prvního řádku dostanu poslední atd. Tato tabulka všech logických spojek je často nazývána tabulka booleových funkcí pro dva argumenty. Kromě funkcí pro již známé spojky zde vidíme i funkce odpovídající jiným spojkám: XOR

eXclusive OR

non-ekvivalence, vylučovací nebo, totéž jako ¬(A ⇔ B), čti: „aneboÿ (latinsky „autÿ), značení: ⊕ , jiné značení: ∨ .

NOR

Negated OR

negace disjunkce, Piercova log. funkce, totéž jako ¬(A ∨ B) ≡ ¬A ∧ ¬B, čti: „aniÿ značení: ↓ , jiné značení: | .

NAND

Negated AND

negace konjunkce, Schefferova log. funkce, totéž jako ¬(A ∧ B) ≡ ¬A ∨ ¬B, značení: ↑ .

24


Každou z logických spojek, obecněji každou booleovskou funkci, lze vyjádřit pomocí jiné logické spojky nebo kombinací spojek. Nabízí se otázka, zda lze všechny spojky vyjádřit jen pomocí jedné spojky nebo množiny spojek. Tedy existuje množina spojek, která je funkčně úplná? Následující tautologie definují pomocí negace a implikace všechny ostatní logické spojky: (p ∨ q) ⇐⇒ (¬p ⇒ q), (p ∧ q) ⇐⇒ ¬(p ⇒ ¬q), (p ⇔ q) ⇐⇒ (p ⇒ q) ∧ (q ⇒ p)2 . Z uvedených tautologií vyplývá, že množina {¬, ⇒} je funkčně úplná. V případě potřeby je možné nahradit spojkami negace, konjunkce a disjunkce spojky: (p ⇒ q) ⇐⇒ (¬p ∨ q), (p ⊕ q) ⇐⇒ (p ∧ ¬q) ∨ (¬p ∧ q). Tedy množina spojek {¬, ∧, ∨} je také funkčně úplná. Použijeme-li de Morganova pravidla, získáme množiny {¬, ∧} a {¬, ∨}. Existují však i jednoprvkové funkčně úplné množiny logických spojek. Takovými spojkami jsou ↓ a ↑, neboť platí ¬p ⇐⇒ (p ↓ p), ¬p ⇐⇒ (p ↑ p) (Tato vlastnost uvedených spojek je využívána při konstrukci logických obvodů.) Příklad 2.2. Vyjádřete spojky disjunkci a implikaci jen pomocí spojky NOR. Řešení. A ∨ B ⇐⇒ ¬¬(A ∨ B) ⇐⇒ ¬(A ↓ B) ⇐⇒ (A ↓ B) ↓ (A ↓ B). A ⇒ B ⇐⇒ ¬(A ∧ ¬B) ⇐⇒ ¬A ∨ B ⇐⇒ (A ↓ A) ∨ B ⇐⇒ ⇐⇒ ((A ↓ A) ↓ B) ↓ ((A ↓ A) ↓ B). ¤ Cvičení 2.1. Sestavte tabulku pravdivostních hodnot a rozhodněte o splnitelnosti formulí 1. ((p ∧ q) ⇒ q) ∨ ¬p, 2. a ∧ (b ∨ ¬(¬b ⇒ a)), 3. (¬a ∨ ((b ⇒ a) ∧ c)) ⇒ ¬b. Cvičení 2.2. Dokažte, že spojka NAND tvoří jednoprvkovou funkčně úplnou množinu logických spojek. 2 Využívá se při dokazování. Ekvivalenci (⇔) rozdělíme na dvě implikace (⇒ a ⇐) a dokazujeme, že platí ⇒ i ⇐.


25

Další užitečné tautologie Sylogismus (p ⇒ q) ⇒ ((q ⇒ r) ⇒ (p ⇒ r)). Sylogismus je následující druh usuzování pocházející už z aristotelské logiky: Víme, že všechny objekty z množiny A mají nějakou vlastnost. Víme, že prvek x patří do množiny A. Učiníme závěr, že prvek x má danou vlastnost. Příklad sylogismu: Všichni lidé jsou smrtelní. Sokrates je člověk. Odvozený závěr: Sokrates je smrtelný. Import („⇒ÿ) a export („⇐ÿ) (p ⇒ (q ⇒ (r ⇒ (s ⇒ t)))) ⇐⇒ ((p ∧ q ∧ r ∧ s) ⇒ t). Obměna implikace (A ⇒ B) ⇐⇒ (¬B ⇒ ¬A). Negace implikace ¬(A ⇒ B) ⇐⇒ (¬A ∧ B).

Úpravy logických formulí Úprava logické formule spočívá v její záměně nebo záměně její podformule jinou formulí, se kterou je ekvivalentní. Při tom používáme tautologie (uvedené výše), které nám ukazují, co můžeme nahradit čím, tj., které formule jsou ekvivalentní. Úpravou formulí jsme se již zabývali, a to když jsme nahrazovali logické spojky jinými spojkami. Příklad 2.3. Zjednodušte formuli (¬A ∧ B) ∨ (A ∧ ¬B). Řešení. (¬A ∧ B) ∨ (A ∧ ¬B), ¬(B ⇒ A) ∨ ¬(A ⇒ B), ¬((B ⇒ A) ∧ (A ⇒ B)), ¬(A ⇔ B), A ⊕ B. ¤

Cvičení 2.3. Rozhodněte o pravdivosti formule, formuli upravte a znegujte. 1. (¬A ∧ ¬B) ∨ (¬A ∧ B) ∨ (A ∧ ¬B).

26

KAPITOLA 2. ÚVOD DO LOGIKY 2. (¬A ∧ B) ∨ (A ∧ ¬B). 3. (p ⇒ q) ∨ (q ⇒ p). 4. p ⇒ (q ⇒ (p ∧ q)). 5. ¬A ⇒ (A ⇒ B). 6. ¬(¬q ∨ r) ∨ (¬(p ∨ q) ∨ (p ∨ r)). 7. A ⇒ (¬B ⇒ ¬(A ⇒ B)). 8. (a ⇒ b) ⇒ ((b ⇒ ¬c) ⇒ ¬a). 9. (a ⇒ c) ⇒ ((b ⇒ d) ⇒ ((a ∨ b) ⇒ c)).

2.2

Stručný úvod do predikátové logiky

Chceme zkoumat objekty – množiny, body, přímky, útvary, čísla, . . . Označení pro objekty – máme dva druhy pojmenování: konstanty a proměnné. — Konstanty. Na příklad: 1, 2, 3, . . . – význam těchto symbolů (znaků) je již ustálen. π, ∅ – číslo „píÿ a prázdná množina. Atd. — Proměnné. Na příklad: x, y, z, . . . A, B, C, . . . Atd. Atd. Proměnné se chovají jako dočasné konstanty, ale jejich význam není blíže určen. Je proměnný. S objekty můžeme provádět různé operace. Na příklad: — „2 + 3ÿ, kde „2ÿ a „3ÿ jsou objekty-konstanty a „+ÿje binární funkční symbol, znak operace sčítání. Výsledkem je konstanta. — „x + 3ÿ, kde „xÿ je proměnná. Výsledek je proměnný. — „−10ÿ, kde „10ÿje objekt-konstanta a „−ÿ je unární funkční symbol pro vytvoření záporného čísla. — „{1, 2} ∪ {2, 3, 4}ÿ, kde „{1, 2}ÿ a „{2, 3, 4}ÿ jsou objekty-konstanty a „∪ÿ je binární funkční symbol pro sjednocení. — „A ∪ Bÿ, kde „Aÿ a „Bÿ jsou objekty-proměnné. Výsledek je proměnný. O zkoumaných objektech pronášíme různá tvrzení – jednoduché oznamovací věty, ty lze pak skládat podle syntaktických pravidel i do souvětí, ale stále jen s významem oznamovacím, nikoliv rozkaz nebo otázka. Příklady tvrzení-výroků:

2.2. STRUČNÝ ÚVOD DO PREDIKÁTOVÉ LOGIKY

27

— „3 < 10ÿ, kde „3ÿ a „10ÿ jsou objekty-konstanty a „<ÿ je binární predikátový symbol, znak pro relaci „být menší nežÿ mezi dvěma objekty. Zde můžeme ihned říci, zda výrok platí či ne. — „x ∈ Aÿ, kde „xÿa „Aÿ jsou objekty-proměnné a „∈ÿ je binární predikátový symbol, znak náležení. O pravdivosti tohoto výroku se nelze moc říci, záleží na konkrétních hodnotách proměnných x a A. — „Set(A)ÿ, přičemž „Set(·)ÿ je unární predikát „být množinaÿ. — „2 je sudéÿ, kde „2ÿ je objekt-konstanta a „ je sudéÿ je unární predikát „být sudé čísloÿ. K práci s objekty potřebujeme jazyk. Jazyk predikátové logiky je vlastně jazyk výrokové logiky obohacený o další symboly.

Jazyk I. řádu Jazyk I. řádu obsahuje: Symboly (znaky) pro proměnné (Nekonečně mnoho těchto symbolů.)

x, y, z, x1 , x2 , x3 , . . .

Symboly pro logické spojky

¬, ⇒, ∨, ∧, ⇔.

Symboly pro logické konstanty

true, false.

Symboly pro kvantifikátory

∀, ∃

Funkční symboly (Ke každému funkčnímu symbolu je dána jeho četnost (arita), tj. počet jeho operandů, což je přirozené číslo ≥ 0.)

f , g, sin, . . .

Predikátové symboly (Každý má svoji aritu ≥ 1.)

Set(·), ∈, ≤, . . .

Pomocné symboly

(, ), :, . . .

Poznámka 2.2. Funkční symbol, jehož arita je rovna 0 (nemá operandy), je konstanta. Ze symbolů jazyka lze, podle syntaktických pravidel, tvořit slova. Máme dva druhy slov: termy a formule.

Metadefinice termu 1. Každá proměnná je term.

28

KAPITOLA 2. ÚVOD DO LOGIKY 2. Nechť O(·, ·, . . . , ·) je n-ární funkční symbol (neboli n-místný operační znak) a nechť τ1 , τ2 , . . . , τn , kde n ≥ 0, jsou termy. Potom O(τ1 , τ2 , . . . , τn ) je term. 3. Jiné termy nejsou. Všechny termy lze získat jen pomocí pravidel 1. a 2.

Poznámka 2.3. Operační znak (v pravidle 2.) může být buď nulární (n = 0), nebo unární (n = 1), binární (n = 2), ternární (n = 3) atd. Nulární operační znak je konstanta. Poznámka 2.4. Binární operační znaky obvykle zapisujeme infixovým způsobem. Na příklad namísto „+(2, 3)ÿ (což by odpovídalo pravidlu 2.) píšeme jednoduše „2 + 3ÿ.

Metadefinice formule 1. Nechť P(·, ·, . . . , ·) je n-ární predikátový symbol a nechť τ1 , τ2 , . . . , τn , kde n ≥ 1, jsou termy. Potom P(τ1 , τ2 , . . . , τn ) je (atomická) formule. 2. Nechť A a B jsou formule. Potom (¬A),

(A ⇒ B),

(A ∨ B),

(A ∧ B),

(A ⇔ B)

jsou formule. 3. Nechť A je formule a x je proměnná. Potom (∀x: A),

(∃x: A)

jsou formule. (Jiné značení: (∀x)(A), (∃x)(A) nebo ∀x(A), ∃x(A) apod.) 4. Jiné formule nejsou. Poznámka 2.5. Predikátový symbol (v pravidle 1.) může být unární (n = 1), binární (n = 2), ternární (n = 3) atd. Poznámka 2.6. Unární predikát vyjadřuje vlastnost nějakého objektu. Na příklad, k vyjádření vlastnosti „býti množinouÿ můžeme použít unární predikát Set(·). Zápis „Set(X)ÿ tedy znamená, že „daný objekt X je množinaÿ. Binární predikát vyjadřuje vztah mezi dvěma objekty. Příkladem vztahu mezi dvěma objekty může být fakt, že jeden je prvkem druhého. K vyjádření této skutečnosti používáme binární predikát ∈(·, ·) (nebo zkrátka · ∈ · – jak uvidíme


29

v následující poznámce). Stručný zápis „x ∈ Aÿ tak znamená, že „objekt x náleží objektu Aÿ. Jiným příkladem binárního predikátu je predikát rovnosti · = · (popř. =(·, ·)). Zápis „X =Yÿ vyjadřuje rovnost mezi objekty X a Y , tzn., že X i Y je jeden a tentýž objekt. Poznámka 2.7. Také binární predikáty bývá obvyklé zapisovat infixovým způsobem. Na příklad místo „≤(2, 3)ÿ nebo „=(5, 5)ÿ apod. píšeme zkrátka „2 ≤ 3ÿ nebo „5 = 5ÿ apod. Krajní a případně i další závorky (podle pravidla 2. a 3.) často vynecháváme. Příklad 2.4. Příklad formule: číslo 1 + 1 je sudé . | {z } | {z } term

unární predikát

Příklad 2.5. Jiný příklad formule: 1 + 1 < 2 + 2 ⇐⇒ 8 < 9. Poznámka 2.8. Formule ∀x: 1 = 1 je v pořádku. Vypadá však lépe, pokud proměnná x má ve formuli A (pravidlo 3.) alespoň jeden volný výskyt. Poznámka 2.9. V logice se spojky ¬ a ⇒ považují za základní logické spojky. Ostatní logické spojky se dají odvodit: A∨B

– syntaktická zkratka za (¬A) ⇒ B,

A∧B

– syntaktická zkratka za ¬(¬A ∨ ¬B), čili ¬((¬¬A) ⇒ ¬B),

A⇔B

– syntaktická zkratka za (A ⇒ B) ∧ (B ⇒ A).

Stejně tak jen ∀ je „základní kvantifikátorÿ a ∃ je kvantifikátor odvozený: ∃x: A(x) je zkratka za ¬(∀x: ¬A(x)). Tedy platí: ∀x: ¬A(x) ⇐⇒ ¬∃x: A(x), ∃x: ¬A(x) ⇐⇒ ¬∀x: A(x).

Kvantifikátory Máme dva kvantifikátory: ∀ – základní (všeobecný, velký) kvantifikátor, odpovídá nekonečné (nebo konečné, záleží na množině prvků) konjunkci: nechť x1 , x2 , . . . jsou všechny možné hodnoty, kterých proměnná x může nabýt, potom ∀x: A(x) znamená vlastně A(x1 ) ∧ A(x2 ) ∧ · · · .

30


Formuli ∀x: A(x) čteme: pro všechna x / pro každé x platí A(x). ∃ – odvozený (existenční) kvantifikátor, odpovídá nekonečné (nebo konečné) disjunkci: nechť x1 , x2 , . . . jsou všechny možné hodnoty, kterých proměnná x může nabýt, potom ∃x: A(x) znamená vlastně A(x1 ) ∨ A(x2 ) ∨ · · · . Formuli ∃x: A(x) čteme: existuje x tak, že platí A(x). Formuli ∀x ∃y: A(x, y) čteme: ke každému x existuje y tak, že platí A(x, y). Není správné uvedenou formuli číst „pro každé x existuje. . . ÿ – je ale možné, že toto pravidlo má svoje výjimky.

Vázané a volné proměnné Výskyt proměnné x ve formuli A a může být buď volný nebo vázaný. Vázaný výskyt. Proměnná x se vyskytuje v nějakém termu, ten se vyskytuje v nějaké formuli B a formule A obsahuje (∀x: B) nebo (∃x: B) jako svoji podformuli. Volný výskyt. Výskyt, který není vázaný. Proměnná x je vázaná ve formuli A, má-li tam vázaný výskyt, a volná, má-li volný výskyt. Formule se nazývá otevřená, když obsahuje jen volné proměnné a žádnou vázanou. Formule se nazývá uzavřená, když všechny proměnné jsou vázané. Uzavřené formule jsou matematická tvrzení (věty). Formule s jednou volnou proměnnou vyjadřuje vlastnost jednoho objektu. Formule se dvěma volnými proměnnými vyjadřuje vztah mezi dvěma objekty. Příklad 2.6. Uvažujme formuli x = 10 ∧ (∃x: (x > 10 ∨ y = 1)). Proměnná x má v této formuli volný (první) i vázaný (druhý) výskyt, proměnná y je volná.


31

Zavedení nového predikátu definicí Nechť A je formule a buďte x1 , x2 , . . . , xn právě všechny, navzájem různé, proměnné formule A. Budiž P(·, ·, . . . , ·) nový n-ární predikátový symbol, (n ≥ 1). Definice: přidáme nový definující axiom P(x1 , x2 , . . . , xn ) ⇔ A. Poznámka 2.10. Nově zavedený predikát P je vlastně jen syntaktická zkratka za formuli A. Příklad 2.7. Několik příkladů: x ≤ y ⇐⇒ (x < y ∨ x = y), x | y ⇐⇒ ∃z ∈ N: z · x = y, X ⊆ Y ⇐⇒ ∀z: (z ∈ X ⇒ z ∈ Y ).

Zavedení funkce (operace) definicí Nechť A je formule a nechť y, x1 , x2 , . . . , xn jsou právě všechny volné, navzájem různé, proměnné formule A. Nechť O(·, ·, . . . , ·) je nový n−ární operační znak (n ≥ 1). Nechť platí, že ∀x1 · · · ∀xn ∃!y: A(y, x1 , x2 , . . . , xn ) neboli ∀x1 · · · ∀xn ∃y: A(y, x1 , x2 , . . . , xn ) ∧ ∀z: Ay [z](z, x1 , x2 , . . . , xn ) ⇒ y = z. Definice: přidáme nový definující axiom y = O(x1 , x2 , . . . , xn ) ⇐⇒ A(y, x1 , x2 , . . . , xn ). Poznámka 2.11. Opět je to syntaktická zkratka, ale složitější – už se pracuje i s predikátem rovnosti. Definovat lze v podstatě cokoliv. Definice je ale účelné volit uvážlivě – určují, kudy teorii vedu, kterým směrem teorii rozvíjím. Příklad 2.8. Řekněme, že na intervalu h− π2 , π2 i máme funkci sinus (sin x). Na intervalu h−1, 1i bychom chtěli definovat funkci arkus-sinus (arcsin y). Můžeme definovat x = arcsin y ⇐⇒ y = sin x. Tato definice je korektní, protože formule na pravé straně (y = sin x) splňuje potřebnou podmínku ∀y ∈ h−1, 1i ∃!x ∈ h− π2 , π2 i: y = sin x.

32


Matematická teorie Matematická teorie je „ jenÿ soustava axiomů (uzavřené formule) – tvrzení, o jejichž pravdivosti se nepochybuje, rovněž musí být známy i predikáty a operace, se kterými se v dané teorii pracuje. Některé axiomy jsou společné všem teoriím (jejich schémata budou uvedena v následujícím oddíle). My se budeme zabývat teorií množin. Mějme nějakou formuli A (tvrzení). Jsou zde dvě zcela odlišné otázky: (1) Lze formuli A v dané teorii dokázat, je formule A dokazatelná? (2) Je formule A v dané teorii pravdivá? Důkaz formule – čistě syntaktická záležitost. Co je to důkaz?

Důkaz à la Hilbert (ve stylu Hilbertově) Důkazem formule A rozumíme konečnou posloupnost formulí ϕ1 , ϕ2 , . . . , ϕn takovou, že 1. ϕn je dokazovaná formule A, 2. každá z formulí ϕ1 , ϕ2 , . . . , ϕn je buď axiom, anebo je odvozena z předchozích formulí užitím některého odvozovacího pravidla (modus ponens, generalizace). Pravidlo modus ponens (tj. pravidlo odloučení): A, A ⇒ B B Pravidlo generalizace:

A ∀x A Nyní uvedeme schémata logických axiomů – jsou společné všem (matematickým) teoriím: I. A ⇒ (B ⇒ A), II. (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)), III. (¬B ⇒ ¬A) ⇒ (A ⇒ B), kde A, B, C jsou libovolné formule. IV. Schéma axiomů specifikace: ∀x A =⇒ Ax [t], kde t je term substituovatelný za proměnnou x do formule A. V. Schéma axiomů prenexní operace: ∀x(A ⇒ B) =⇒ (A ⇒ ∀x B), přičemž proměnná x nesmí mít volný výskyt ve formuli A.


33

Schémata axiomů pro rovnost: VI. axiom identity: x = x, VII. axiom rovnosti pro operace: x1 = y1 ⇒ x2 = y2 ⇒ · · · ⇒ xn = yn ⇒ ⇒ O(x1 , x2 , . . . , xn ) = O(y1 , y2 , . . . , yn ), VIII. axiom rovnosti pro predikáty: x1 = y1 ⇒ x2 = y2 ⇒ · · · ⇒ xn = yn ⇒ ⇒ P(x1 , x2 , . . . , xn ) ⇒ P(y1 , y2 , . . . , yn ), kde x a x1 , . . . , xn a y1 , . . . yn jsou proměnné, O je n-ární operační znak (neboli funkční symbol) a P je n-ární predikátový symbol. Příklad 2.9. Příklad důkazu (ve stylu Hilbertově). Dokážeme zcela triviální tvrzení, že „A ⇒ Aÿ pro libovolnou formuli A. Důkaz sestává z následující posloupnosti pěti formulí ϕ1 , . . . , ϕ5 ; při pravém okraji uvádíme poznámku, zda formule je axiomem nebo zda byla odvozena z předchozích pravidlem modus ponens: 1. 2. 3. 4. 5.

` (A ⇒ ((A ⇒ A) ⇒ A)), axiom I., ` (A ⇒ ((A ⇒ A) ⇒ A)) ⇒ ((A ⇒ (A ⇒ A)) ⇒ (A ⇒ A)), axiom II., ` (A ⇒ (A ⇒ A)) ⇒ (A ⇒ A), MP 1.+ 2., ` (A ⇒ (A ⇒ A)), axiom I., ` A ⇒ A, MP 4.+ 3.

Jak je vidět, důkazy i těch nejjednodušších formulí provedené plně formálním způsobem jsou poměrně dlouhé. V matematice proto důkazy tvrzení podáváme raději slovy. Matematikům stačí, že v případě potřeby by podaný slovní důkaz na posloupnost formulí (důkaz ve stylu Hilbertově) bylo možné převést. Idea za tím: „Pravdivost formule se snažíme podepřít jejím důkazem.ÿ

Pravdivost formule Důkaz formule byl čistě syntaktická záležitost. Pravdivost formule je sémantická záležitost – „z říše Platonského nebeÿ. Máme Universum („nebeÿ) a v něm jsou objekty, kterým říkáme individua. Předpokládáme, že v tomto Universu platí axiomy naší teorie (takže jde o model dané teorie). Chceme-li rozhodnout o pravdivosti nějaké formule A, musíme se podívat, jestli daná formule A v tom Universu (ale raději na všech Universech, kde platí naše axiomy) je splněna – pravdivá.

34


Idea za tím: „Bůh vidí, jestli daná formule (v daném Universu) pravdivá je, nebo není.ÿ Ale my to nevidíme. My se pravdivost formule snažíme podpírat jejím důkazem. To se opírá o následující větu (či přesněji metavětu) o korektnosti. Věta 2.1. (Věta o korektnosti.) Jestliže formule A je dokazatelná, potom je pravdivá ve všech modelech dané teorie. Kurt Gödel3 (1906–1978) dokázal také následující dvě hluboké (meta)věty. Věta 2.2. (Gödelova věta o úplnosti.) Jestliže formule A je pravdivá ve všech modelech dané teorie, potom je též dokazatelná z axiomů té teorie. Věta 2.3. (Gödelova věta o neúplnosti.) Jestliže teorie je „dostatečně bohatáÿ (obsahuje aritmetiku), potom v ní jsou i tzv. nerozhodnutelná tvrzení – formule A taková, že nelze dokázat ani A ani ¬A, nelze ji dokázat ani vyvrátit. Obě uvedené věty měly hluboký dopad na filosofii matematiky. Vlastně znamenaly konec původního velkého Hilbertova programu. Traduje se, že David Hilbert se s platností těchto dvou vět osobně nikdy nesmířil. Formalismus (jakožto pojetí základů matematiky) ale může pokračovat dále. Na formalismus už ve 40. letech 20. století bez sebemenších problémů navázala skupina francouzských matematiků sdružených pod pseudonymem Nicolas Bourbaki. Jejich práce jsou charakteristické přísnou axiomatickou výstavbou, vysokým stupněm abstrakce i obecnosti. Jedním z významných představitelů moderního formalismu je francouzský matematik Jean Dieudonné.

Platné formule s kvantifikátory Na závěr této kapitoly si uvedeme několik vztahů mezi formulemi s kvantifikátory. Znak ϕ (popř. ψ) označuje formuli bez volného výskytu proměnné x. Naopak zápis ϕ(x) nebo ψ(x) naznačuje, že proměnná x v těchto formulích má volný výskyt. Triviálně platí ∀x ϕ(x) =⇒ ϕ(x1 ), ϕ(x1 ) =⇒ ∃x ϕ(x), kde x1 je jedna z možných hodnot (konstanta), kterých proměnná x může nabývat. Dále platí: ∀x (ϕ(x) ∧ ψ(x)) ⇐⇒ (∀x ϕ(x) ∧ ∀x ψ(x)), (∀x ϕ(x) ∨ ∀ xψ(x)) =⇒ ∀x (ϕ(x) ∨ ψ(x)), ∃x (ϕ(x) ∨ ψ(x)) ⇐⇒ (∃x ϕ(x) ∨ ∃x ψ(x)), 3 Kurt Gödel – původem Rakušan (pocházel z Brna). Pak (r. 1940) se přestěhoval do Ameriky. Snad nejslavnější logik všech dob.

2.2. STRUČNÝ ÚVOD DO PREDIKÁTOVÉ LOGIKY ∃x (ϕ(x) ∧ ψ(x)) =⇒ (∃x ϕ(x) ∧ ∃x ψ(x)), (∀x ϕ(x) ∧ ψ) ⇐⇒ ∀x (ϕ(x) ∧ ψ), (∀x ϕ(x) ∨ ψ) ⇐⇒ ∀x (ϕ(x) ∨ ψ), (∃x ϕ(x) ∧ ψ) ⇐⇒ ∃x (ϕ(x) ∧ ψ), (∃x ϕ(x) ∨ ψ) ⇐⇒ ∃x (ϕ(x) ∨ ψ), (ϕ ∧ ∀x ψ(x)) =⇒ ∀x (ϕ ∧ ψ(x)), (ϕ ∨ ∀x ψ(x)) =⇒ ∀x (ϕ ∨ ψ(x)), (ϕ ∧ ∃x ψ(x)) =⇒ ∃x (ϕ ∧ ψ(x)), (ϕ ∨ ∃x ψ(x)) =⇒ ∃x (ϕ ∨ ψ(x)), ∀x (ϕ(x) ⇒ ψ) ⇐⇒ (∃x ϕ(x) ⇒ ψ), ∃x (ϕ(x) ⇒ ψ) ⇐⇒ (∀x ϕ(x) ⇒ ψ), ∀x (ϕ ⇒ ψ(x)) ⇐⇒ (ϕ ⇒ ∀x ψ(x)), ∃x (ϕ ⇒ ψ(x)) ⇐⇒ (ϕ ⇒ ∃x ψ(x)), ∀x ∀y ϕ(x, y) ⇐⇒ ∀y ∀x ϕ(x, y), ∃x ∃y ϕ(x, y) ⇐⇒ ∃y ∃x ϕ(x, y), ∃x (ϕ(x) ⇒ ψ(x)) ⇐⇒ (∀x ϕ(x) ⇒ ∃x ψ(x)), (∃x ϕ(x) ⇒ ∃x ψ(x)) =⇒ ∃x (ϕ(x) ⇒ ψ(x)), ∀x (ϕ(x) ⇔ ψ(x)) =⇒ (∀x ϕ(x) ⇔ ∀x ψ(x)). Těchto tautologií využíváme při úpravách formulí a při jejich důkazech. Příklad 2.10. Dokažte, že platí 1. ∀x (ϕ(x) ⇒ ψ) ⇐⇒ (∃x ϕ(x)) ⇒ ψ, 2. ∃x (ϕ(x) ⇒ ψ(x)) ⇐⇒ (∀x ϕ(x)) ⇒ (∃x ψ(x)), 3. (∃x ϕ(x)) ⇒ (∃x ψ(x)) =⇒ ∃x (ϕ(x) ⇒ ψ(x)). Řešení. 1. ∀x (ϕ(x) ⇒ ψ) ⇐⇒ ∀x (¬ϕ(x) ∨ ψ) ⇐⇒ (∀x ¬ϕ(x)) ∨ ψ ⇐⇒ ⇐⇒ (¬¬∀x ¬ϕ(x)) ∨ ψ ⇐⇒ ⇐⇒ (¬∃x ϕ(x)) ∨ ψ ⇐⇒ (∃x ϕ(x)) ⇒ ψ. 2. ∃x (ϕ(x) ⇒ ψ(x)) ⇐⇒ ∃x (¬ϕ(x) ∨ ψ(x)) ⇐⇒ ⇐⇒ (∃x ¬ϕ(x)) ∨ (∃x ψ(x)) ⇐⇒ ⇐⇒ (¬¬∃x ¬ϕ(x)) ∨ (∃x ψ(x)) ⇐⇒ ⇐⇒ (∀x ϕ(x)) ⇒ (∃x ψ(x)).

35

36

KAPITOLA 2. ÚVOD DO LOGIKY 3. (∃x ϕ(x)) ⇒ (∃x ψ(x)) ⇐⇒ =⇒ ⇐⇒ ⇐⇒

(∀x ¬ϕ(x)) ∨ (∃x ψ(x)) =⇒ (∃x ¬ϕ(x)) ∨ (∃x ψ(x)) ⇐⇒ ∃x (¬ϕ(x) ∨ ψ(x)) ⇐⇒ ∃x (ϕ(x) ⇒ ψ(x)). ¤

Cvičení 2.4. Pokuste se odůvodnit platnost (alespoň některých) uvedených tautologií. Cvičení 2.5. Rozhodněte, zda následující formule jsou tautologie nebo zda jsou alespoň splnitelné (pro vhodnou volbu formulí ϕ a ψ apod.): 1. ∃x (ϕ(x) ⇔ ψ(x)) =⇒ (∃x ϕ(x)) ⇔ (∃x ψ(x)), 2. (∃x ϕ(x) ⇔ ∃x ψ(x)) =⇒ ∃x (ϕ(x) ⇔ ψ(x)), 3. ∀x ∀y R(x, y) =⇒ ∀y ∃x R(x, y), 4. ∀x (∀y R(x, y) ⇒ P (x)) =⇒ ∀y (R(y, y) ⇒ P (y)), 5. ∀x ∃y (R(x, y) ∧ ∀z (R(x, z) ⇒ y = z)) =⇒ ∀y ∃x R(x, y).

Normální tvary formulí Už víme, že každou logickou formuli lze vyjádřit jen pomocí spojek ¬, ∧, ∨. Užitím de Morganových pravidel a pravidel distributivity lze formuli vyjádřit v KNF – konjunktivní normální formě: (· · · ∨ · · · ∨ · · ·) ∧ (· · · ∨ · · · ∨ · · ·) ∧ · · · ∧ (· · · ∨ · · · ∨ · · ·). Terminologie: — Prvotní formule – buď p(x, y, . . .), kde p je predikát, nebo ∀x: ϕ(x), kde ϕ je formule. — Literál – buď je to prvotní formule nebo její negace. — Klauzule – disjunkce literálů (literály se mohou samozřejmě opakovat nebo být ve více klauzulích). — Formule – konjunkce klauzulí. Anebo lze formuli upravit na DNF – disjunktivní normální formu: (· · · ∧ · · · ∧ · · ·) ∨ (· · · ∧ · · · ∧ · · ·) ∨ · · · ∨ (· · · ∧ · · · ∧ · · ·). Terminologie:


37

— Prvotní formule. — Literál. — hbez názvui – konjunkce literálů. — Formule – disjunkce toho hbez názvui. V predikátové logice – u formulí s kvantifikátory – se ještě formule převádějí na prenexní4 (normální) formy: Q1 x1 Q2 x2 Q3 x3 . . . Qn xn : | {z } prefix

B |{z}

,

otevˇ ren´ e j´ adro

kde Qi jsou kvantifikátory ∀ nebo ∃, znaky xi jsou proměnné a B je otevřená formule (neobsahuje už žádné další kvantifikátory).

Algoritmus převodu formule na prenexní tvar 1. Přejmenuj všechny vázané proměnné tak, aby všechny vázané proměnné měly různá jména a lišily se i od volných proměnných. 2. Všechny logické spojky vyjádři jen pomocí ¬, ∧, ∨. 3. Výskyty formulí ¬∀x: ϕ(x) a ¬∃x: ϕ(x) zaměň za ∃x: ¬ϕ(x) a ∀x: ¬ϕ(x). Případně ještě použij de Morganova pravidla a opakuj. 4. Všechny kvantifikátory lze nyní dát dopředu. Tento krok je korektní, protože používáme již známe tautologie ϕ ∧ ∀x: ψ(x) ϕ ∨ ∀x: ψ(x) ϕ ∧ ∃x: ψ(x) ϕ ∨ ∃x: ψ(x)

⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

∀x: (ϕ ∧ ψ(x)), ∀x: (ϕ ∨ ψ(x)), ∃x: (ϕ ∧ ψ(x)), ∃x: (ϕ ∨ ψ(x)),

kde formule ϕ neobsahuje proměnnou x volně, protože už v 1. kroku proměnné byly přejmenovány. 5. Volitelně. Otevřené jádro lze ještě upravit na KNF nebo DNF nebo i jinak. Příklad 2.11. Formuli (∀x: ((ϕ(x) ∧ ∃y: ψ(x, y)) ⇒ ∃y: χ(x, y))) ⇒ (∃z: (ϕ(z) ⇒ ψ(z, x))) převeďte do prenexního tvaru. 4Z

latiny: pre = před, necto = vázat, tedy všechny proměnné jsou svázané vpředu.

38

KAPITOLA 2. ÚVOD DO LOGIKY Řešení. 1. Přejmenuj proměnné: (∀u: ((ϕ(u) ∧ ∃v: ψ(u, v)) ⇒ ∃y: χ(u, y))) ⇒ (∃z: (ϕ(z) ⇒ ψ(z, x))). 2. Vyjádři jen pomocí ¬, ∧, ∨: ¬(∀u: ((¬ϕ(u) ∨ ¬∃v: ψ(u, v)) ∨ ∃y: χ(u, y))) ∨ ∃z: (¬ϕ(z) ∨ ψ(z, x)). 3. Proveď záměny „¬∀ → ∃¬ÿ a „¬∃ → ∀¬ÿ: ∃u: (ϕ(u) ∧ (∃v: ψ(u, v)) ∧ ∀y: ¬χ(u, y)) ∨ ∃z: (¬ϕ(z) ∨ ψ(z, x)). 4. Kvantifikátory přesuň dopředu: ∃u ∃v ∀y ∃z: (ϕ(u) ∧ ψ(u, v) ∧ ¬χ(u, y)) ∨ ¬ϕ(z) ∨ ψ(z, x).

5. Dostali jsme prenexní formu a dokonce nám jádro vyšlo v DNF. Jádro proto již dále upravovat nebudeme. ¤ Příklad 2.12. Převeďte do prenexního tvaru formuli ∃x ∀y: ϕ(x, y) ∧ ∃x ∀y: ψ(x, y). Řešení. 1. krok, přejmenovat proměnné: ∃x ∀y: ϕ(x, y) ∧ ∃u ∀v: ψ(u, v). 2. krok OK, 3. krok OK, 4. krok, kvantifikátory přesunout dopředu: ∃x ∀y ∃u ∀v: ϕ(x, y) ∧ ψ(u, v). ¤ Poznámka 2.12. Poslední příklad lze vyřešit i jiným způsobem: ∃x ∀y: ϕ(x, y) ∧ ∃x ∀y: ψ(x, y), ∃x ∀v: ϕ(x, v) ∧ ∃u ∀v: ψ(u, v), ∃x ∃u: (∀v: ϕ(x, v) ∧ ∀v: ψ(u, v)), ∃x ∃u ∀v: ϕ(x, v) ∧ ψ(u, v)). Vidíme, že pouhá mechanická aplikace výše uvedeného algoritmu nemusí dát vždy ten nejjednodušší možný výsledek. Cvičení 2.6. Převeďte do prenexní formy formule 1. ∀x (P (x) ∧ ∀y ∃x (¬Q(x, y) ⇒ R(a, x, y))), 2. ∀x ((∀x P (x) ∨ ∀z R(z, y)) ⇒ ¬∀y S(x, y), 3. ∀x ∃y: (R(x, y) ∧ ∀z: (R(x, z) ⇒ y = z)) ⇒ ∀y ∃x: R(x, y).

Kapitola 3

Axiomy teorie množin Jsou dva obecně uznávané axiomatické systémy teorie množin: Zermelův-Fraenkelův a Bernaysův-Gödelův systém. V této části načrtneme Zermelův-Fraenkelův axiomatický systém teorie množin.

3.1

Jazyk teorie množin

Jazyk teorie množin používá následující tři základní predikáty: Set(·) – unární predikát „býti množinouÿ. · ∈ · – binární predikát náležení. · = · – binární predikát rovnosti. Později zavedeme i další predikáty definicí. Základní jazyk teorie množin neobsahuje žádné operace. Později zavedeme několik operací definicí. — — — Poznamenejme, že první dva predikáty (Set a ∈) jsou predikáty vlastní teorii množin. Třetí predikát (=) je univerzální predikát rovnosti (identity) dvou objektů, se kterým se můžeme setkat i v jiných teoriích. Již víme z předchozí kapitoly, že zápis Set(X) značí výrok „X je množinaÿ, zápis X ∈ Y značí výrok „(objekt) X je prvkem (objektu) Y ÿa že X = Y značí výrok „(objekt) X se rovná (je shodný s / splývá s objektem) Yÿ – X i Y je jeden a tentýž objekt. — — — Uveďme také všeobecně používané zkratky: X∈ /Y X 6= Y

je zkratka za je zkratka za 39

¬(X ∈ Y ), ¬(X = Y ).

40

KAPITOLA 3. AXIOMY TEORIE MNOŽIN

(První zkratka znamená, že „X není prvkem Y ÿ, druhá zkratka znamená, že „X se nerovná / je různé od Y ÿ.)

3.2

Zermelův-Fraenkelův axiomatický systém teorie množin

Axiom A1 . (Axiom extensionality.) Dvě množiny jsou si rovny právě tehdy, když obsahují stejné prvky: ∀X ∀Y : (Set(X) ∧ Set(Y )) =⇒ (X = Y ⇐⇒ ∀Z: Z ∈ X ⇔ Z ∈ Y ). Poznámka 3.1. Již víme z první kapitoly (právě pomocí axiomu extensionality), že zápisy {X}, {X, X}, {X, X, X} představují stále stejnou množinu {X}. Obdobně zápisy {X, Y }, {X, X, Y }, {X, X, Y, Y, X} představují jedinou množinu {X, Y }. Axiom A2 . (Axiom prázdné množiny.) Existuje prázdná množina, tj. množina neobsahující žádné prvky: ∃Y : Set(Y ) ∧ ∀X: X ∈ / Y. Uveďme svoji první větu v teorii množin. Věta 3.1. Existuje právě jedna prázdná množina: ∃! Y : Set(Y ) ∧ ∀X: X ∈ / Y. Důkaz uvedené věty plyne okamžitě z axiomu extensionality. Protože je jediná, můžeme ji definovat jako konstantu (zavedení funkčního symbolu-konstanty definicí). Definice 3.1. Prázdnou množinu označujeme znakem ∅. Z uvedených dvou axiomů nelze dostat nic víc. Víme tedy, že existuje (jednoznačně určená) prázdná množina, ale nevíme jestli existují také jiné množiny, a když, tak kolik jich je. (S těmito dvěma axiomy je konzistentní i model teorie obsahující prázdnou množinu a žádnou jinou.) Následující axiom už zaručuje i existenci neprázdné množiny. Axiom A3 . (Axiom dvojice.) Jsou-li dány libovolné dva objekty X, Y , potom existuje množina Z = {X, Y }, která obsahuje pouze tyto dva prvky a žádné jiné: ∀X ∀Y ∃Z: Set(Z) ∧ ∀T : (T ∈ Z ⇔ (T = X ∨ T = Y )). Z axiomu dvojice a axiomu extensionality ihned plyne následující věta.

3.2. ZERMELŮV-FRAENKELŮV AXIOMATICKÝ SYSTÉM

41

Věta 3.2. Pro každé X, Y existuje právě jedna množina Z = {X, Y }. ∀X ∀Y ∃! Z: Set(Z) ∧ ∀T : (T ∈ Z ⇔ (T = X ∨ T = Y )). Poznámka 3.2. Vlastně opět můžeme zavést (definovat) binární operaci {·, ·}, která z libovolných dvou prvků X a Y „vyrobíÿ množinu {X, Y }. Poznámka 3.3. Jestliže X = Y , pak axiom dvojice dává pouze jednoprvkovou množinu Z = {X, X} = {X}. Užitím axiomu dvojice můžeme vytvářet další množiny: máme ∅, můžeme vytvořit {∅},

{{∅}}, {{{∅}}}, {{{{∅}}}}, {∅, {∅}}, {{∅}, {{∅}}}, . . .

...,

A tak dále a tak dále. Teď už máme v Universu množin dostatek. Pokud budeme chtít pracovat s nějakým pojmem, můžeme jej pojmenovat pomocí jedné (z výše uvedených) množin. Objekty dalších typů už nemají význam. Proto zavedeme následující axiom A0 . Bohatost Universa se tím do jisté míry omezuje. Axiom A0 . V Universu jsou jenom množiny: ∀X: Set(X). V Universu teď máme hodně jedno- a dvouprvkových množin, pořád však nevíme zda existují také tříprvkové (víceprvkové) množiny. Dvouprvkové množiny představují neuspořádané dvojice. Jsme schopni jazykem teorie množin vyjádřit i uspořádané dvojice? V důsledku axiomu A0 musíme uspořádanou dvojici definovat jako nějakou speciální množinu. Je třeba si uvědomit, že pro uspořádané dvojice jsou charakteristické dvě věci: dva objekty, které obsahuje a pořadí objektů, v jakém do uspořádané dvojice vchází. Následující definici navrhl Norbert Wiener1 . Definice 3.2. Uspořádanou dvojicí prvků X a Y (v daném pořadí) rozumíme množinu [X, Y ] = {{X}, {X, Y }}. Poznámka 3.4. V této definici člen {X, Y } určuje objekty v dvojici a člen {X} určuje, který prvek je první. Pro uspořádané dvojice se užívá také jiného značení: hX, Y i nebo (X, Y ). 1 Norbert Wiener, významný americký matematik 20. století, zakladatel kybernetiky, pracoval také v oblastech matematické analýzy a teorie pravděpodobnosti a matematické statistiky

42


Věta 3.3. Dvě uspořádané dvojice jsou si rovny právě tehdy, když jsou si rovny jejich první i druhé prvky: pro každé A, B, X, Y platí, že [A, B] = [X, Y ] ⇐⇒ X = A ∧ Y = B. Důkaz. Implikace ⇐ je triviální. Dokážeme implikaci ⇒. Rozlišíme dva případy: buď X = Y , anebo X 6= Y . Když X = Y , pak máme [X, Y ] = {{X}, {X, Y }} = {{X}, {X, X}} = {{X}, {X}} = = {{X}} = {{A}, {A, B}} = [A, B]. Pak ovšem {X} = {A} a {X} = {A, B}, protože množiny {{X}} i {{A}, {A, B}} mají stejné prvky. Nutně tedy X = A a X = B. Podle předpokladu je X = Y . Dostáváme tak, že X = A = Y = B. Nechť nyní X 6= Y . Předně je zřejmé, že A 6= B. (Kdyby A = B, pak by stačilo zaměnit označení proměnných X, Y a A, B a použít předchozí část důkazu. Obdrželi bychom, že X = Y .) Podle předpokladu máme [X, Y ] = {{X}, {X, Y }} = {{A}, {A, B}} = [A, B]. Obě množiny tedy musejí mít stejné prvky (dle axiomu extensionality). Tedy musí platit {X} ∈ {{A}, {A, B}}. Odtud plyne, že platí buď {X} = {A},

anebo {X} = {A, B}.

První možnost ({X} = {A}) znamená, že X = A. Druhá možnost ({X} = = {A, B}) by znamenala, že X = A = B, což není možné (víme A 6= B). Tedy platí X = A. Z předpokladu {{X}, {X, Y }} = {{A}, {A, B}} rovněž plyne, že {X, Y } ∈ {{A}, {A, B}}. Takže platí buď {X, Y } = {A},

anebo {X, Y } = {A, B}.

První možnost by znamenala X = Y = A, což není možné (víme X 6= Y ). Platí tedy druhá možnost. Protože již víme X = A, z rovnosti {X, Y } = {A, B} plyne Y = B. Dokázali jsme, že X = A a Y = B. ¤ Pomocí pojmu uspořádané dvojice zavedeme i pojem uspořádané trojice, čtveřice atd. následujícím způsobem.


43

Definice 3.3. Uspořádaná trojice [X, Y, Z] je zkratka za [X, [Y, Z]]. Tedy £ ¤ £ ¤ X, Y, Z = X, [Y, Z] . Pojem uspořádané trojice tedy vychází z pojmu uspořádané dvojice, který již známe. Vskutku: [X, [Y, Z]] je uspořádaná dvojice, X je její první složka a [Y, Z] (sama uspořádaná dvojice!) je její druhá složka. Obdobně uspořádaná čtveřice [A, B, C, D] je zkratka za [A, [B, C, D]]. Tedy £ ¤ £ ¤ A, B, C, D = A, [B, C, D] . (Je to uspořádaná dvojice. Druhá složka je uspořádaná trojice. A pojem uspořádané trojice jsme už zavedli.) Obecně, uspořádanou n-ticí [A1 , A2 , . . . , An ] rozumíme uspořádanou dvojici [A1 , [A2 , . . . , An ]]. Je tedy £ ¤ £ ¤ A1 , A2 , . . . , An = A1 , [A2 , . . . , An ] . Poznámka 3.5. Je třeba si uvědomit, že zavedené množiny jsou pořád jenom dvouprvkové. Skutečně, na příklad množina ©© ª © ªª [X, Y, Z] = X , {Y }, {Y, Z} má dva prvky {X} a {{{Y }, {Y, Z}}}. Dosud uvedené axiomy (extensionality, prázdné množiny, dvojice a axiom A0 ) totiž neumožňují odvodit existenci tříprvkové (víceprvkové) množiny. Proto jsme pojem uspořádané trojice zavedli rekurzivním způsobem jen pomocí pojmu uspořádané dvojice. — — — Osvěžme výklad zavedením predikátu inkluze definicí. Definice 3.4. Definujme binární predikát inkluze · ⊆ · („býti podmnožinouÿ) a ostré inkluze · ⊂ · („býti vlastní podmnožinouÿ) následujícím způsobem: def.

X⊆Y

⇐⇒ ∀Z: Z ∈ X ⇒ Z ∈ Y,

X⊂Y

⇐⇒ X ⊆ Y ∧ X 6= Y.

def.

První formule vyjadřuje, že množina X je podmnožinou množiny Y právě tehdy, když pro libovolný prvek Z platí: jestliže Z náleží množině X, potom náleží i množině Y . Druhá formule vyjadřuje, že množina X je vlastní podmnožinou množiny Y právě tehdy, když X je podmnožinou Y ale X je různé od Y . Poznámka 3.6. Někteří autoři používají jiné značení, podmnožinu (nikoliv vlastní) označují symbolem ⊂. Zápisem X ⊂ Y tito autoři vyjadřují, že ∀Z: Z ∈ X ⇒ Z ∈ Y . S pojmem vlastní podmnožiny tito autoři nepracují. My budeme symboly ⊆ a ⊂ používat ve významu podle výše uvedené definice.

44

KAPITOLA 3. AXIOMY TEORIE MNOŽIN Důkazy následujících dvou vět jsou snadné a přenecháváme je čtenáři.

Věta 3.4. Každá množina X má alespoň dvě (triviální) podmnožiny, totiž ∅ a X: ∅⊆X a X ⊆ X. Věta 3.5. Dvě množiny jsou si rovny právě tehdy, když jsou ve vzájemné inkluzi: X = Y ⇐⇒ X ⊆ Y ∧ Y ⊆ X. Cvičení 3.1. Odůvodněte platnost uvedených dvou vět. Poznámka 3.7. Poslední věta se často požívá při důkazech rovnosti dvou množin. Jsou dány nějaké dvě množiny X a Y . Máme dokázat X = Y . Důkaz provedeme tak, že dokážeme X ⊆ Y a Y ⊆ X. Inkluze X ⊆ Y se dokáže podle definice: Zvolíme libovolný prvek Z ∈ X a nějakým způsobem dokážeme, že z faktu Z ∈ X vyplývá Z ∈ Y . Jinou možností je dokázat, že z faktu Z ∈ / Y vyplývá Z ∈ / X. Obdobně pro inkluzi Y ⊆ X. Uveďme si ještě další dvě všeobecně používané zkratky. Nechť X je proměnná, A je množina a ϕ(X) je jakákoliv formule obsahující proměnnou X volně. Potom ∀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. — — — Pokračujme dalšími axiomy teorie množin. Axiom A04 . (Schéma axiomů vydělení.) Nechť ϕ(X) je formule a A je množina. Potom Set({ X ; X ∈ A ∧ ϕ(X) }). Volněji řečeno, všechny prvky X množiny A, které splňují podmínku ϕ(X), vytvářejí množinu. Tuto množinu { X ; X ∈ A ∧ ϕ(X) } lze zapsat také zkráceně jako { X ∈ A ; ϕ(X) }. Platí tedy: { X ; X ∈ A ∧ ϕ(X) } = { X ∈ A ; ϕ(X) } (zápis na pravé straně rovnice je zkratka za zápis na levé straně). Uvedené schéma axiomů vydělení lze zapsat i jinak – formulí: Nechť ϕ(X) je formule, která neobsahuje proměnnou Z volně. Potom ∀A ∃Z: ∀X: X ∈ Z ⇐⇒ X ∈ A ∧ ϕ(X).

(∗)

Množina Z, jejíž existence se touto formulí postuluje, je právě množina { X ; X ∈ A ∧ ϕ(X) }.


45

Uvedené schéma axiomů není axiomem. Axiom – totiž konkrétní axiom vydělení pro formuli ϕ(X) – dostaneme, až když do uvedeného schématu dosadíme nějakou konkrétní formuli ϕ(X). Uvedené schéma tak zastupuje nekonečně mnoho axiomů: pro každou možnou formuli ϕ(X) jeden axiom. Poznámka 3.8. Podmínka, aby ve formuli (∗) proměnná Z neměla volný výskyt ve ϕ(X), je důležitá. Kdybychom tuto podmínku opomněli, znamenalo by to, že množina Z by se mohla odvolávat sama na sebe. Příklad 3.1. Self-reference (tj. odkaz na sebe sama) je podstatou mnoha paradoxů. Jedním z elementárních příkladů takového paradoxu je tvrzení tato věta není pravdivá. Je tato věta pravdivá? Pokud ano, pak není pravdivá, protože to sama o sobě tvrdí. Pokud ne, pak není pravda, že není pravdivá – protože toto uvedená věta o sobě tvrdí – tedy je pravdivá. Paradox.) Na obdobném principu je založen Russellův paradox, se kterým jsme se seznámili v první kapitole. Podívejme se na Russellův paradox ještě jednou: Uvažujme množinu (?) Z = {X ; X ∈ Z ∧ X ∈ / X }.

(∗∗)

Platí Z ∈ Z? Už víme, že Z ∈ Z právě tehdy, když Z ∈ / Z, což je paradox. Povšimněme si dvou věcí: (1) Uvedená „množinaÿ Z se již ve svojí definici (∗∗) odkazuje sama na sebe. (2) Uvedená „množinaÿ Z neodpovídá schématu axiomů vydělení. (Méně zkušený čtenář by se mohl nechat zmást a „vidětÿ, že množina Z zavedená podle (∗∗) schématu axiomů vydělení odpovídá. Jako formuli ϕ(X) bychom vzali výrok „X ∈ / Xÿ. A pokud Z je množina (?), potom podle axiomu vydělení platí Set({ X ; X ∈ Z ∧ X ∈ / X }). Ale tato úvaha není správně – kde bereme jistotu, že Z je množina? Přesněji řečeno, pohybujeme se v kruhu: abychom dokázali (podle schématu axiomů vydělení), že Z je množina, musíme předpokládat, že Z je množina (abychom schéma mohli použít).) Russellův paradox (ve spojení se schématem axiomů vydělení) dnes můžeme chápat jako důkaz neexistence množiny všech množin. Věta 3.6. Neexistuje množina všech množin: ¬∃Y ∀X: X ∈ Y. Důkaz. Důkaz provedeme sporem. Předpokládejme, že Y – množina všech množin – existuje. Potom, v důsledku schématu axiomů vydělení, existuje také množina M = {X ; X ∈ Y ∧ X ∈ / X}.

46


Nyní ovšem, jako v Russellově paradoxu, z možnosti M ∈ M vyplývá M ∈ /M a z možnosti M ∈ / M vyplývá M ∈ M , což je spor. Množina všech množin tedy nemůže existovat. ¤

Poznámka 3.9. Myšlence, která je v důkazu použita, se říká diagonální metoda. S touto metodou se ještě setkáme na několika místech. Díky schématu axiomů vydělení můžeme definovat dvě základní binární operace s množinami: rozdíl dvou množin · \ · a průnik dvou množin · ∩ · . (Třetí elementární operaci – sjednocení – ještě definovat nemůžeme. Dosud uvedené axiomy na to nestačí.) Definice 3.5. Rozdíl dvou množin X a Y je množina všech prvků, které náleží množině X a nenáleží množině Y : def.

X \ Y = {Z ; Z ∈ X ∧ Z ∈ / Y }. Průnik dvou množin X a Y je množina všech prvků, které náleží množině X i množině Y : def. X ∩ Y = { Z ; Z ∈ X ∧ Z ∈ Y }. (Poznámka. Výsledky obou operací jsou množiny podle schématu axiomů A04 . Množina, ze které se „vydělujeÿ, je množina X, podmínka ϕ(Z) je „Z ∈ / Yÿ v prvním případě a „Z ∈ Y ÿ ve druhém případě. Ve druhém případě si dokonce můžeme vybrat: lze „vydělovatÿ z množiny Y a jako podmínku ϕ(Z) vzít „Z ∈ Xÿ.) Nyní zavedeme definicí binární predikát „dvě množiny býti disjunktníÿ. Definice 3.6. Dvě množiny X a Y jsou disjunktní2 právě tehdy, když X ∩ Y = ∅ – jejich průnik je prázdný. Cvičení 3.2. Nechť X, Y a Z jsou množiny. Nahlédněte, že platí 1. X ∩ Y = Y ∩ X, 2. (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z), 3. X \ Y ⊆ X, 4. X ∩ Y ⊆ X, 5. X ∩ Y ⊆ Y . Cvičení 3.3. Nechť X, Y a Z jsou množiny. Platí také následující vztahy? 1. X \ Y = Y \ X? 2 Disjunktní

– z latinského disiunctio = rozpojení, rozloučení.


47

2. (X \ Y ) \ Z = X \ (Y \ Z)? 3. X \ Y ⊆ Y ? [Obecně neplatí. Odůvodněte.] Schéma axiomů vydělení nám umožňuje definovat i obecný průnik (neprázdného) souboru množin. Nechť A je neprázdná množina (obsahující množiny). Chtěli bychom definovat obecný průnik \ A = { X ; ∀Y ∈ A: X ∈ Y }. Na příklad

© ª ∩ {1, 3, 5}, {1, 2, 4, 5}, {1, 4, 5, 7} = {1, 5}.

Uvedená konstrukce ovšem neodpovídá schématu axiomů vydělení A04 : chybí zde základní množina, ze které bychom „vydělovaliÿ. Konstrukci proto přepíšeme. Budiž B libovolná množina. Potom podle schématu A04 platí Set({ X ; X ∈ B ∧ ∀Y ∈ A: X ∈ Y }).

(∗∗∗)

Uvedená formule (∗∗∗) platí pro každé B. Speciálně tedy platí i pro každé B ∈ A. Jenomže, jestliže B ∈ A, potom formule X ∈ B ∧ ∀Y ∈ A: X ∈ Y a ∀Y ∈ A: X ∈ Y jsou ekvivalentní! Jestliže tedy A 6= ∅, potom existence alespoň jednoho B ∈ A je zaručena a platí Set({X ; ∀Y ∈ A: X ∈ Y }). V případě A 6= ∅ tedy můžeme položit \ A = { X ; ∀Y ∈ A: X ∈ Y }. Pro neprázdné množiny tedy můžeme definovat unární operaci průniku

T

·.

Definice 3.7. Pro libovolnou neprázdnou množinu A definujeme \ def. A = { X ; ∀Y ∈ A: X ∈ Y }. Jestliže A = ∅, potom výsledek operace

T

A není definován.

Poznámka 3.10. Co se (ve výše uvedené definici) stane, když A = ∅? Potom bychom měli \ ∅ = { X ; ∀Y ∈ ∅: X ∈ Y } = = { X ; ∀Y : Y ∈ ∅ ⇒ X ∈ Y }.

48


Ovšem předpoklad Y ∈ ∅ v uvedené implikaci je vždy nepravdivý. Celá implikace Y ∈ ∅ ⇒ X ∈ Y je tudíž vždy pravdivá (pro každé X i Y ). Následně i formule ∀Y : Y ∈ ∅ ⇒ X ∈ Y T je splněna pro všechna X! Vidíme, že průnik ∅ obsahuje každou množinu X – je to „množina všech množinÿ. My již však víme, že množina všech množin neexistuje. Co to tedy je? Výsledkem operace průniku na prázdnou množinu je tzv. univerzální třída neboli celé Universum teorie množin. (Univerzální třída (Universum) je třída, která obsahuje každou množinu. To není žádný rozpor, protože třída není množina. V Zermelově-Fraenkelově systému hraje pojem třídy jen pomocnou úlohu. Třídy vlastně neexistují – nejsou v Universu (vzhledem k axiomu A0 ).) Jakkoli je schéma axiomů vydělení užitečné při konstrukci nových množin, jeho aplikací vznikají pouze podmnožiny množin již existujících. Doposud nemáme k dispozici žádný prostředek, pomocí kterého bychom mohli množiny spojovat-sjednocovat. Existenci sjednocení je nutno postulovat dalším axiomem. Axiom A5 . (Axiom sjednocení.) Sjednocení všech množin obsažených v množině A je množina: ∀A: Set({ X ; ∃Y ∈ A: X ∈ Y }). S Definice 3.8. Výsledek sjednocení množiny A značíme A: [ def. A = { X ; ∃Y ∈ A: X ∈ Y }. Poznámka 3.11. Vlastně jsme definovali další unární operaci

S

·.

Příklad 3.2. Na příklad [ {{1, 3, 5}, {1, 2, 4, 5}, {1, 4, 5, 7}} = {1, 2, 3, 4, 5, 7}. Povšimněme si, že prázdná množina zde nečiní žádné potíže. Máme [ ∅ = ∅. Pro sjednocení dvou množin používáme jednodušší značení – definujeme třetí elementární množinovou operaci, totiž binární sjednocení · ∪ · . Definice 3.9. Nechť X a Y jsou dvě množiny. Definujeme [ def. X ∪Y = {X, Y }. Věta 3.7. Sjednocení dvou množin X a Y je množina obsahující prvky, které patří do množiny X nebo do množiny Y : X ∪ Y = { Z ; Z ∈ X ∨ Z ∈ Y }.


49

Důkaz je jednoduchý a přenechávám jej čtenáři. Operace sjednocení, průniku a rozdílu množin jsou vlastně booleovskými operacemi. Platí pro ně de Morganova pravidla. Věta 3.8. (De Morganova pravidla.) Nechť A, B a C jsou množiny. Potom platí C \ (A ∩ B) = (C \ A) ∪ (C \ B) a duálně C \ (A ∪ B) = (C \ A) ∩ (C \ B). Důkaz. Dokážeme první vztah (pomocí axiomu extensionality A1 ): X ∈ C \ (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ý (duální) vztah se dokáže obdobně. Čtenář nechť se o důkaz druhého vztahu pokusí samostatně. ¤

Cvičení 3.4. Nechť A a B jsou dvě množiny. Zkuste nahlédnout (a odůvodnit) následující vztahy: 1. A \ B = (A ∪ B) \ B = A \ (A ∩ B). 2. A \ (A \ B) = A ∩ B. Příklad 3.3. Dosud jsme mohli vytvářet nejvýše dvouprvkové množiny. Teprve axiom sjednocení A5 nám umožňuje vytvářet i tříprvkové (víceprvkové) množiny. Na příklad: © ª © ª © ª © ª ∅ ∪ {∅} ∪ {{∅}} = ∅, {∅}, {{∅}} a podobně. (Existence množin, které jsme sjednocovali, plynula z axiomu existence prázdné množiny A2 a axiomu dvojice A3 .) Přejděme k dalšímu axiomu teorie množin. Axiom A6 . (Axiom potenční množiny.) Systém všech podmnožin dané množiny A je také množina: ∀A: Set({ X ; X ⊆ A }).

50


Definice 3.10. Množinu všech podmnožin dané množiny nazýváme potenční množina. Potenční množinu množiny A značíme P(A): def.

P(A) = { X ; X ⊆ A }. (Poznámka. Někteří autoři pro označení potenční množiny množiny A používají i jiná značení: P (A) nebo 2A . Platí tedy P (A) = 2A = P(A).) Poznámka 3.12. Právě jsme definicí zavedli další unární operaci P(·). Poznámka 3.13. Axiomy A5 a A6 jsou speciálním případem cantorovského schématu { X ; ϕ(X) }, kde ϕ(X) je formule. (Formule ϕ(X) v axiomu A5 byla „∃Y ∈ A: X ∈ Y ÿ a v axiomu A6 to byla formule „X ⊆ Aÿ.) My již víme, že objekt { X ; ϕ(X) } v obecnosti množinou není (obecně je to jen třída). Abychom zaručili existenci množiny prvků X splňujících podmínku ϕ(X), musíme použít schéma axiomů vydělení A04 – musí být dána množina, ze které se „vydělujeÿ. Příklad 3.4. © ª P(∅) = ∅ , © ª P({X}) = ∅, {X} , © ª P({X, Y }) = ∅, {X}, {Y }, {X, Y } , © ª P({X, Y, Z}) = ∅, {X}, {Y }, {Z}, {X, Y }, {X, Z}, {Y, Z}, {X, Y, Z} . Pomocí axiomu sjednocení (případně axiomu potenční množiny) už můžeme vytvořit libovolně velkou množinu. Ale nekonečnou množinu pořád ještě vytvořit neumíme. Následující axiom zodpovídá kladně otázku, zda existuje aktuálně nekonečná množina. Axiom A7 . (Axiom nekonečné množiny.) Existuje nekonečná množina. ∃Z: (∅ ∈ Z ∧ ∀X: X ∈ Z ⇒ X ∪ {X} ∈ Z). Pro větší srozumitelnost uveďme, co je výsledkem operace X ∪ {X} k danému X: X X ∪ {X} ∅

{∅}

{∅} {∅, {∅}} .. .

{∅, {∅}} {∅, {∅}, {∅, {∅}}}


51

Vidíme, že tato posloupnost nikdy neskončí. A množina Z, jejíž existence se v axiomu nekonečna postuluje, obsahuje přinejmenším tuto nekonečnou posloupnost. (Množina Z může obsahovat i další prvky.) Množina Z je tak – zatím alespoň intuitivně – nekonečná. — — — Všechny dosud uvedené axiomy (A0 , A1 , A2 , A3 , A04 , A5 , A6 , A7 ) tvoří původní Zermelův axiomatický systém teorie množin. Až v roce 1922 Abraham Fraenkel formuloval Axiom substituce (nahrazení). Přidáním tohoto axiomu dostáváme Zermelův-Fraenkelův axiomatický systém teorie množin. Axiom A4 . (Schéma axiomů substituce.) Nechť ψ(Y, X) je formule, kde Y a X jsou dvě z jejích volných proměnných. Předpokládejme, že ke každému X existuje nejvýše jedno Y tak, aby platilo ψ(Y, X), ∀X: ∀Y ∀W : ψ(Y, X) ∧ ψY [W ](W, X) ⇒ W = Y, kde W je nová proměnná, která ve formuli ψ(Y, X) nemá volný výskyt. Znak ψY [W ](W, X) označuje formuli ψ(Y, X), ve které všechny volné výskyty proměnné Y byly zaměněny výskytem proměnné W . Nechť A je množina. Potom Set({ Y ; ∃X ∈ A: ψ(Y, X) }). Uvedené schéma axiomů lze zapsat i jinak – formulí: Nechť ψ(Y, X) je formule, která neobsahuje proměnnou W ani Z volně. Potom ¡ ¢ ∀X: ∀Y ∀W : ψ(Y, X) ∧ ψY [W ](W, X) ⇒ W = Y =⇒ ¡ ¢ =⇒ ∀A ∃Z: ∀Y : Y ∈ Z ⇐⇒ ∃X ∈ A: ψ(Y, X) . Pokusme se uvedené schéma intuitivně vysvětlit. Čtenář nechť si zopakuje odstavec o zavedení operace definicí z předchozí kapitoly. Zde, ve schématu axiomů substituce se setkáváme s něčím obdobným. Formule ψ(Y, X) zde téměř definuje operaci. Vskutku: ke každému X existuje nejvýše jedno Y tak, že ψ(Y, X). Není to tedy operace v pravém slova smyslu, protože pro některá X nemusí být definována (nemusí existovat Y tak, aby ψ(Y, X)). Následkem toho můžeme výrok Set({ Y ; ∃X ∈ A: ψ(Y, X) }) chápat tak, že obrazy nějaké operace (totiž „operace definovanéÿ formulí ψ(Y, X)) aplikované na množinu A vytvářejí množinu. Tento přístup se plně zračí v Mirimanově3 verzi axiomu substituce. ˜ 4 . (Mirimanovo schéma axiomů substituce.) Nechť O(·) je opeAxiom A race zavedená definicí. Máme tedy nějakou formuli ψ(Y, X) splňující podmínku ∀X ∃! Y : ψ(Y, X). 3 Mirimanov

– ruský emigrant – formuloval tento axiom už v roce 1917. Jeho práce však byly tehdy úplně zapomenuty.

52


a definující axiom O(X) = Y ⇐⇒ ψ(Y, X). Potom obrazy operace O(·) aplikované na libovolnou množinu A také vytvářejí množinu: Set({O(X) ; X ∈ A}). (Rozepsáním definice operace O(·) můžeme uvedený výrok přepsat do tvaru Set({Y ; ∃X ∈ A: ψ(Y, X)}).) Poznámka 3.14. Mirimanovův axiom substituce je snad intuitivně zřejmější. ˜ 4 rozdíl. Podívejme se blíže, jaký je mezi schématy A4 a A Ve schématu A4 se požadovalo, aby ke každému X existovalo nejvýše jedno Y ˜ 4 se požaduje, aby ke každému X existovalo tak, aby ψ(Y, X). Ve schématu A právě jedno Y – aby existovalo alespoň jedno a současně aby existovalo nejvýše ˜ 4 oproti schématu A4 navíc požaduje i existenci Y ! jedno Y . Vidíme, že schéma A ˜ (Schéma A4 toho po formuli ψ(Y, X) požaduje více. Takové předpoklady jsou splněny v menším počtu případů než volnější předpoklady schématu A4 . ˜ 4 , platí tedy implikace „A4 ⇒ A ˜ 4 ÿ. Schéma A4 je proto silnější než schéma A Zkuste si to promyslet.) Až na tuto jedinou „drobnostÿ (totiž předpoklad existence Y ) mezi schématy ˜ 4 a A4 žádný další rozdíl není. Je proto pozoruhodné, že Mirimanov svoji A (slabší) verzi objevil už v roce 1917, tedy 5 let před Fraenkelem. Následující věta (spíše je to metavěta) říká, že Fraenkelovo schéma axiomů substituce A4 je silnější než původní Zermelovo schéma axiomů vydělení A04 . Proto je možné schéma A04 z celé teorie vynechat. Ale vzhledem k jeho jednoduchosti je lepší, pokud to jde, vystačit pouze s A04 a schéma A4 nepoužívat. V celém dalším textu tak budeme činit. Věta 3.9. Schéma axiomů substituce implikuje schéma axiomů vydělení: „A4 =⇒ A04 ÿ. Důkaz. Nechť je dána množina A a formule ϕ(X). Chceme ukázat, že objekt { X ; X ∈ A ∧ ϕ(X) } je množina. Schéma A04 při důkazu ovšem nesmíme použít, uvedenou skutečnost musíme dokázat pomocí schématu A4 . Zvolme tedy novou proměnnou Y , která nemá volný výskyt ve formuli ϕ(X), a položme ψ(Y, X) ⇐⇒ (Y = X ∧ ϕ(X)). Je zřejmé, že formule ψ(Y, X) má všechny vlastnosti požadované ve schématu axiomů substituce A4 . Proto, podle A4 , { Y ; ∃X ∈ A: ψ(Y, X) } = { X ; X ∈ A ∧ ϕ(X) } je množina.

¤ — — —


53

Nyní máme vše připraveno pro uvedení série definic důležitých pojmů (operací a predikátů) teorie množin. Začneme pojmem (operací) kartézského4 součinu. Definice 3.11. (Kartézský součin.) Kartézský součin množin A a B je množina def. A × B = { [a, b] ; a ∈ A ∧ b ∈ B }. Obecně, kartézský součin n množin A1 , A2 , . . . , An je množina def.

A1 × A2 × · · · × An = { [a1 , a2 , . . . , an ] ; a1 ∈ A1 ∧ a2 ∈ A2 ∧ · · · ∧ an ∈ An }. Jestliže množiny A1 , A2 , . . . , An si jsou 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 . Poznámka 3.15. Vzhledem k £tomu, jakým způsobem byla uspořádaná trojice ¤ £ ¤ (obecně n-tice) zavedena, totiž a1 , a2 , . . . , an = a1 , [a2 , . . . , an ] , obecně platí (např. pro tři množiny) A1 × A2 × A3 = A1 × (A2 × A3 ) 6= (A1 × A2 ) × A3 . Kartézský součin není asociativní. Poznámka 3.16. Pozorného čtenáře možná napadne otázka: Je kartézský součin množina? Užitím schématu axiomů vydělení A04 ukážeme, že tomu tak skutečně je. © ª Připomeňme si, že [a, b] = {a}, {a, b} . Předpokládejme a ∈ A a b ©∈ B. Je zřejmé, že {a}, {a, b} ⊆ A ∪ B. Tedy {a}, {a, b} ∈ P(A ∪ B). Tudíž {a}, ª {a, b} ⊆ P(A ∪ B). Odtud plyne, že © ª [a, b] = {a}, {a, b} ∈ P(P(A ∪ B)). Definici kartézského součinu tak lze ekvivalentně přepsat do následujícího tvaru: A × B = { Z ; Z ∈ P(P(A ∪ B)) ∧ ∃a ∈ A ∃b ∈ B: Z = [a, b] }. Vidíme, že podle schématu axiomu vydělení A04 kartézský součin je množina. 4 Slovo kartézský je odvozeno od latinského slova Cartesius, což je latinské příjmení francouzského učence René 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. Ve svojí filosofii vyznával zásadu jasnosti a zřetelnosti každé teze, rozčlenění složitého na jednoduché, postup od známého k neznámému a úplnost logické dedukce. Kladl velký důraz na prověřování poznání rozumem. — Pochybovat lze o všem. Lze ale pochybovat i o závěrech odvozených vlastním myšlením? K tomu se vztahuje jeho známý výrok „myslím, tedy jsemÿ (latinsky „cogito, ergo sumÿ). Lze o tom pochybovat? 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.

54


Definice 3.12. (Inverze množiny.) Inverzí množiny A je množina def.

A−1 = { [X, Y ] ; [Y, X] ∈ A }. Poznámka 3.17. Opět je na místě otázka, zda jde o množinu. Již víme z předchozí poznámky, že [X, čeho? © Y ] ∈ P(P(.ª. .)). Jenomže potence potence S Jestliže [Y, X] = {Y }, {X, Y } ∈ A, potom {Y }, {X, Y } ∈ A, a tudíž SS X, Y ∈ A. Dostáváme, že ¡ ¡S S ¢¢ [X, Y ] ∈ P P A . Následně můžeme inverzi množiny A přepsat do následujícího tvaru: © ¡ ¡S S ¢¢ ª A−1 = Z ; Z ∈ P P A ∧ ∃X ∃Y : Z = [X, Y ] ∧ [Y, X] ∈ A . Inverze množiny je tedy množinou podle schématu axiomů vydělení A04 . Značení následujících množinových operací je motivováno jejich anglickými názvy, které rovněž uvádíme. Definice 3.13. (Definiční obor – domain.) Definičním oborem libovolné množiny A je množina def.

Dom(A) = { X ; ∃Y : [Y, X] ∈ A }. Definice 3.14. (Obor hodnot – range.) Oborem hodnot libovolné množiny A je množina def.

Rng(A) = { Y ; ∃X: [Y, X] ∈ A }. Poznámka 3.18. V našem textu jsme se rozhodli pro tradiční terminologii. Termín „oborÿmá trochu historický nádech. Dříve se totiž místo pojmu množina používal pojem obor. Ostatně ještě dnes se někdy můžeme setkat se slovním obratem „řešte rovnici v oboru reálných číselÿ apod. Poznámka 3.19. Čtenáře možná velmi udivuje, že definiční obor je 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šíÿ volit první složku jako definiční obor a druhou složku jako obor hodnot. Naše rozhodnutí však £ plyne¤ z definice uspořádané trojice (n-tice). Na 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. Viz níže definici funkce. Poznámka 3.20. Opět ověříme, že Dom(A) a Rng(A) jsou množiny. ZSpředS -před-předchozí poznámky už víme, že pokud [Y, X] ∈ A, potom X, Y ∈ A. Poslední dvě definice tak lze uvést v následujícím ekvivalentním tvaru: © SS Dom(A) = X ; X ∈ A ∧ ∃Y : [Y, X] ∈ A }, © SS Rng(A) = Y ; Y ∈ A ∧ ∃X: [Y, X] ∈ A }.


55

Definiční obor a obor hodnot tak jsou množiny podle schématu axiomů vydělení A04 . Definice 3.15. (Parcializace – zúžení definičního oboru.) Parcializací neboli zúžením definičního oboru množiny A na množinu B rozumíme def.

A ¹ B = { [Y, X] ; X ∈ B ∧ [Y, X] ∈ A }. Věta 3.10. A ¹ B = A ∩ (Rng(A) × B). Důkaz této věty je triviální a přenecháváme jej čtenáři. (Čtenář musí dokázat inkluze ⊆ a ⊇. Inkluze ⊆ znamená, že z [Y, X] ∈ A ¹ B (tedy z výroku X ∈ ∈ B ∧ [Y, X] ∈ A) plyne [Y, X] ∈ A ∩ (Rng(A) × B) (tedy výrok [Y, X] ∈ ∈ A ∧ ([Y, X] ∈ A ∧ X ∈ B). Inkluze ⊆ se nahlédne obdobně.) Poznámka 3.21. Z této věty také vyplývá, že zúžení A ¹ B je množina: již víme, že obor hodnot množiny A je množina, že kartézský součin dvou množin je množina a konečně že průnik dvou množin je množina. Definice 3.16. (Obraz množiny.) Obrazem množiny B přes množinu A rozumíme def. A 00 B = { Y ; ∃X ∈ B: [Y, X] ∈ A }. Poznámka. Jestliže A je funkce (tj. zobrazení, viz níže), potom obraz množiny B se častěji značí A(B). Věta 3.11. A 00 B = Rng(A ¹ B). Důkaz této věty opět přenecháváme čtenáři. Poznámka 3.22. Poslední věta opět dokazuje, že obraz množiny A 00B je množina: víme, že zúžení A ¹ B je množina a také víme, že obor hodnot množiny je množina. Dosud jsme zaváděli operace definicí. Nyní zavedeme několik predikátů (a ještě jednu operaci) definicí. Definice 3.17. (Relace.) Množina A je relace právě tehdy, když obsahuje pouze uspořádané dvojice: def.

Rel(A) ⇐⇒ ∀Z: Z ∈ A ⇒ ∃X ∃Y : Z = [X, Y ]. Poznámka. Obdobně bychom mohli definovat také unární predikát Rel3 (A) – množina A je množinou uspořádaných trojic. Apod.

56


Poznámka 3.23. Relace modeluje vztah mezi dvěma objekty prostředky teorie množin. Nezaměňujte relaci (tj. množinu uspořádaných dvojic) s binárním predikátem! Jde o dvě zcela rozdílné věci! Množiny (a tedy speciálně i relace – množiny uspořádaných dvojic) jsou objekty v Universu. Kdežto binární predikát vyjadřuje vztahy mezi objekty v Universu. Relace se obvykle značí písmeny R, S apod., ale také (pokud jde o relace uspořádání) znaky ≤, < apod. Jestliže R je relace, potom bývá obvyklé používat následující zkratku: xRy

je zkratka za

[x, y] ∈ R.

Ostatně jsme již dávno zvyklí psát např. 3 ≤ 7, 2 < 5 atd. Následující věta podává dvě charakteristiky predikátu „množina býti relacíÿ. Podává též elementární vlastnosti operace inverze množiny a její vztah k predikátu „býti relacíÿ. Důkaz této věty je snadný, a proto jej přenecháváme čtenáři. Věta 3.12. 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 ). Následující věta je složitá jen na první pohled. Důkaz opět přenecháváme čtenáři. Věta 3.13. Nechť A je množina relací: ∀X ∈ A: Rel(X). Potom sjednocení množiny A je relace: ¡S ¢ Rel A . Definice 3.18. (Skládání množin.) Nechť R a S jsou množiny. Složením těchto dvou množin rozumíme ª def. © R ◦ S = [X, Z] ; ∃Y : [X, Y ] ∈ R ∧ [Y, Z] ∈ S . Poznámka 3.24. Je zřejmé, že R◦◦ S ⊆ Rng(R)× × Dom(S). Složení dvou množin tak můžeme přepsat do následujícího tvaru: © R ◦ S = T ; T ∈ Rng(R) × Dom(S) ∧ ª ∧ ∃X ∃Z ∃Y : T = [X, Z] ∧ [X, Y ] ∈ R ∧ [Y, Z] ∈ S . Vidíme, že složení dvou množin je množina podle schématu axiomů vydělení A04 .


57

Funkce je speciálním typem relace. Tento pojem opět zavádíme jako unární predikát. Definice 3.19. (Funkce.) Množina F je funkce právě tehdy, když je to relace a současně platí, že každé X z definičního oboru se zobrazí na nejvýše jedno Y z oboru hodnot: def.

Fnc(F ) ⇐⇒ Rel(F ) ∧ ∀X ∀Y ∀Z: [Y, X] ∈ F ∧ [Z, X] ∈ F ⇒ Y = Z. Přidejme též poslední definici této kapitoly. Definice 3.20. (Vzájemně jednoznačná funkce.) Funkce F je vzájemně jednoznačná (lze také říkat, že F je prostá nebo že F je invertibilní), pokud také F −1 je funkce: def.

Fnc−1 (F ) ⇐⇒ Fnc(F ) ∧ Fnc(F −1 ). Poznámka 3.25. Funkce modeluje pojem zobrazení prostředky teorie množin. Pojem funkce (totiž množiny, která má vlastnost Fnc(·)) a operace (např. operace zavedené definicí – výše jsme takových operací zavedli spoustu) opět není možné zaměnit. Operace je totiž definovaná na celém Universu. S pojmem operace se navíc můžeme setkat i v jiných teoriích (nejen v teorii množin). Kdežto funkce (množina mající vlastnost Fnc(·)) je jen jedním z objektů Universa a v uvedené podobě se s ní můžeme setkat jen v teorii množin. Funkce obvykle značíme písmeny F , G, H apod. Protože funkce je relace, můžeme (pokud Fnc(F )), obdobně jako u relací, místo [y, x] ∈ F použit zkratku yF x. Avšak jestliže F je funkce, potom bývá obvyklé používat mnohem názornější zkratku: y = F (x)

je zkratka za což je ekvivalentní

yF x, [y, x] ∈ F.

V matematice se také velmi často používá následující zkratka. Zápis F:A → B

je zkratka za

Fnc(F ) ∧ Dom(F ) = A ∧ Rng(F ) = B. — — —

V této kapitole jsme se seznámili s několika množinovými operacemi. Kromě kartézského součinu to byly operace inverze množiny (·−1 ), definičního oboru (Dom(·)), oboru hodnot (Rng(·)), zúžení definičního oboru (· ¹ ·), obrazu (· 00 ·) a skládání (· ◦ ·). Ačkoliv zavední posledně jmenovaných operací bylo motivováno zejména jejich použitím na funkce nebo relace, poznamenejme, že tyto operace jsou definovány pro všechny množiny. Uvedené operace je tedy možné použít i na množiny, které funkcemi nebo relacemi nejsou (nemají vlastnost Fnc(·) nebo

58


Rel(·)). Snad jen o smysluplnosti obdrženého výsledku by někdy bylo možné diskutovat. . . Vraťme se ještě k operaci skládání (· ◦ ·). Nechť F a G jsou funkce (Fnc(F ) ∧ ∧ Fnc(G)) a nechť x je libovolný prvek definičního oboru složené funkce (x ∈ ∈ Dom(F ◦ G)). Pak platí následující vztah: ¡ ¢ ¡ ¢ F ◦ G (x) = F G(x) . (Poznámka. Je jasné, že F ◦ G je funkce. Takže zápis (F ◦ G)(x) značí hodnotu této (jedné) složené funkce v bodě x. Na pravé straně je třeba nejprve vypočíst G(x), což je hodnota funkce G v bodě x. Vypočtená hodnota se pak dosadí do funkce F .) Čtenář možná tento vztah zná již ze střední školy nebo odjinud. Jde o poměrně známý vztah. Často se tento vztah bere jako „definiceÿ složené funkce. Povšimněte si, že platnost tohoto vztahu je podmíněna tím, že obraz prvku (obor hodnot) je první složkou uspořádané dvojice a vzor (definiční obor) je až druhou složkou uspořádané dvojice – viz operace Dom(·) a Rng(·). Připomínáme, že s tím souvisí i způsob zavedení uspořádané n-tice prvků. Pokud bychom snad chtěli, aby obor hodnot byl druhou a definiční obor první složkou uspořádané dvojice a přitom zachovat platnost vztahu (F ◦ G)(x) = F (G(x)), museli bychom (kromě způsobu zavedení uspořádané n-tice) změnit definici operace skládání · ◦ ◦ .

Kapitola 4

Mohutnost (kardinalita) 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. Věta 4.1. (Tarského1 věta o pevném bodě.) Nechť A je libovolná množina a F : P(A) → P(A) je funkce monotónní vzhledem k inkluzi. Platí tedy ∀X, Y ⊆ A: X ⊆ Y =⇒ F (X) ⊆ F (Y ). Potom funkce F má alespoň jeden pevný bod: ∃C ⊆ A: F (C) = C. Důkaz. Uvažujme množinu M = { X ; X ⊆ A ∧ X ⊆ F (X) } (podmínka X S ⊆ A je ekvivalentní X ∈ P(A), takže M je množina podle A04 ) a položme C = M . Tedy [ C= M = { Z ; ∃X ∈ M : Z ∈ X }. Potom pro každé X ∈ M nutně platí X ⊆ C. Z monotonie funkce F plyne, že pro každé X ∈ M platí F (X) ⊆ F (C). Pro každé X ∈ M tedy platí X ⊆ ⊆ F (X) ⊆ F (C), a tudíž X ⊆ F (C) pro každé X ∈ M . Odtud plyne, že [ C= M = { Z ; ∃X ∈ M : Z ∈ X } ⊆ F (C). 1 Alfred

Tarski (1902–1983), polský matematik a logik. Od roku 1939 žil v USA.

59

60

KAPITOLA 4. MOHUTNOST (KARDINALITA) MNOŽIN

(Protože každé Z ∈ X ∈ M splňuje Z ∈ X ⊆ F (C), je jasné, že Protože C ⊆ F (C) a F je monotónní, plyne odtud, že

S

M ⊆ F (C).)

F (C) ⊆ F (F (C)). Množina F (C) je tedy prvkem množiny M . My ale už víme, že každé X ∈ M splňuje X ⊆ C. Tedy F (C) ⊆ C. Dokázali jsme inkluzi F (C) ⊆ C i inkluzi C ⊆ F (C). Platí tedy F (C) = C. ¤ Věta 4.2. (Věta Banachova2 .) Nechť A, B jsou libovolné množiny a nechť F : A → B a G: B → A jsou vzájemně jednoznačné funkce (Fnc−1 (F )∧ ∧Fnc−1 (G), ne nutně surjektivní – „naÿ). Potom existují množiny A ⊆ A a B ⊆ B tak, že B = F 00 A

a současně

A \ A = G 00 (B \ B).

Důkaz. Sestrojme funkci H: P(A) → P(A) následujícím vzorcem: H(X) = A \ G 00 (B \ F 00 X) libovolné X ⊆ A. (Dáno X ⊆ A. Nejprve vezmeme obraz X přes funkci F . Z tohoto obrazu vezmeme doplněk v množině B a zobrazíme jej zpátky přes G do A. Nakonec vezmeme doplněk v množině A.) Poznamenejme, že H je množina podle A04 , protože © ª H = [Y, X] ∈ P(A) × P(A) ; Y = A \ G 00 (B \ F 00 X) . Tvrdíme, že H splňuje podmínky Tarského věty. Vskutku. Nechť X ⊆ Y ⊆ ⊆ A. Potom: F B\F G 00 B \ F H(X) = A \ G 00 B \ F

X X 00 X 00 X 00 X 00

⊆ Y, ⊆ F 00 Y, ⊇ B \ F 00 Y, ⊇ G 00 B \ F 00 Y, ⊆ A \ G 00 B \ F 00 Y = H(Y ).

Podle Tarského věty má H pevný bod. Existuje tedy množina A ⊆ A tak, že H(A) = A. Položme B = F 00 A (tím je dokázána první část tvrzení věty). Stačí nyní dokázat, že A \ A = G 00 (B \ B). Uvažme, že podle definice H platí A = H(A) = A \ G 00 (B \ F 00 A) = = A \ G 00 (B \ B), tedy A \ A = G 00 (B \ B). ¤ 2 Stefan Banach (1892–1945), vynikající polský matematik, působil na universitě ve Lvově. Zabýval se teorií normovaných vektorových prostorů, je spoluzakladatelem funkcionální analýzy.

61 Poznámka 4.1. Banachova věta je starší než věta Tarského. Teď se budeme zabývat následujícím problémem. Uvažujme dvě množiny A a B. Ptáme se, zda mají stejný počet prvků. Problém je v tom, že počítat prvky ještě neumíme. Na druhé straně je otázka, zda mají stejný počet prvků, mnohem jednodušší než otázka, kolik mají prvků. Počty prvků množin A a B počítat totiž 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 v tanečním sále více je 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. Definice 4.1. Množiny X a Y jsou ekvivalentní3 (můžeme říkat též ekvipotentní nebo že mají stejnou mohutnost) a píšeme X ≈ Y právě tehdy, když existuje prostá funkce F z množiny X na množinu Y : X≈Y

def.

⇐⇒ ∃F : Fnc−1 (F ) ∧ Dom(F ) = X ∧ Rng(F ) = Y.

Definice 4.2. Množina X je subvalentní4 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 z množiny X do množiny Y : X¹Y

def.

⇐⇒ ∃F : Fnc−1 (F ) ∧ Dom(F ) = X ∧ Rng(F ) ⊆ Y.

Definice 4.3. Množina X je ostře subvalentní množině Y (má ostře menší mohutnost) právě tehdy, když X≺Y

def.

⇐⇒ X ¹ Y ∧ X 6≈ Y.

Věta 4.3. (Věta Cantorova-Bernsteinova.) Pro libovolné dvě množiny A a B platí A ¹ B ∧ B ¹ A =⇒ A ≈ B. Důkaz. Jestliže A ¹ B, potom existuje prostá funkce F : A → B. Jestliže B ¹ ¹ A, potom existuje prostá funkce G: B → A. Vidíme, že jsou splněny podmínky Banachovy věty. Tudíž existují množiny A ⊆ A a B ⊆ B tak, že B = F 00A a G 00(B\\ B) = A\\ A. 3 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í). 4 Latinsky sub = pod (pod něčím, níže než).

62

KAPITOLA 4. MOHUTNOST (KARDINALITA) MNOŽIN Potom prostá funkce H: A → B definovaná H(x) = F (x) −1

H(y) = G tedy

pro x ∈ A,

(y)

pro y ∈ A \ A,

¡ ¢ ¡ ¡ ¢¢−1 , H = F ¹A ∪ G¹ B\B

zobrazuje množinu A na množinu B. Proto A ≈ B.

¤

Poznámka 4.2. Tato věta je opět starší než věta Banachova. Povšimněme si následující jednoduché věty (důkaz přenecháváme čtenáři). Věta 4.4. X ⊆ Y =⇒ X ¹ Y . Věta 4.5. (Věta Cantorova.) Nechť A je libovolná množina. Potom A ≺ P(A). 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), která je na množinu P(A), která dosvědčuje, ž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 4.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 F (a1 ) F (a2 ) F (a3 ) .. .

a2

a3

...

63 Jelikož 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. Důsledek 4.6. Neexistuje množina největší mohutnosti. Mohutnost množin je shora neohraničená: ¬∃Y ∀X: X ¹ Y. Důkaz. Kdyby taková množina Y existovala, potom její potence P(Y ) by podle Cantorovy věty měla ještě větší mohutnost – spor. ¤

Poznámka 4.4. Popišme si na tomto místě tzv. Cantorův paradox. Již v první kapitole jsme zmínili, že Cantor uvažoval množinu všech množin, označme ji M. Pokud by taková množina existovala, musela by nutně mít největší mohutnost ze všech množin. (Množina M by obsahovala všechny množiny. Každá jiná množina by už byla jen podmnožinou množiny M, a tedy by měla i menší (nebo stejnou) mohutnost.) Cantor ovšem dokázal, že musí platit M ≺ P(M). Paradox. Dnes tento paradox můžeme chápat jako další důkaz neexistence množiny všech množin (věta 3.6.). Poznámka 4.5. 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. (Tyto množiny jsme dosud nezavedli. 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. Jde o hypotézu kontinua5 . Toto byl dlouhou dobu otevřený problém. 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 5 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.

64

KAPITOLA 4. MOHUTNOST (KARDINALITA) MNOŽIN

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á. Věta 4.7. Nechť A je systém množin takový, že platí ∀X ∈ A ∃Y ∈ A: X ≺ Y. Potom ∀X ∈ A: X ≺

[

A. S

Důkaz. Zvolme X ∈ A. Potom zřejmě X ¹ A, protože X ⊆ S platilo X ≈ A, by existovalo též Y ∈ A takové, že [ [ A≈X≺Y ¹ A, což je spor. Tedy X ≺

S

A.

S

A. Kdyby

¤

Použitá literatura [1] Barrow, J. D. Pí na nebesích. Praha: Mladá fronta, 2000. ISBN 80-204-0855-X. [2] Balcar, B. – Štěpánek, P. Teorie množin. Praha: Academia, 1986. [3] Fürst, K. Slovník latinsko-český. Praha: Kvasnička a Hampl, 1941. [4] Šedivý, J. Základní poznatky z algebry a teorie čísel. 2. vydání. Praha: SPN, 1986. [5] B. Kočího malý slovník naučný. Praha: B. Kočí, 1929. 2 sv. [6] 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é údaje převzaty také ze skript [4]. Dále latinské názvy logických spojek převzaty z těchto skript. Významy latinských slov konsultovány také se slovníkem [3]. Z encyklopedie [6] čerpány uváděné základní životopisné údaje matematiků. Některé údaje o Bertrandu Russellovi doplněny též podle slovníku [5]. Kniha [2] pak představuje obsáhlou monografii o teorii množin.

65

Úvod do teorie množin a logiky. David Bartl

Recommend Documents