Teorie množin (NAIL063), LS 2019/2020
Přednáška se koná ve středu v 12:20 v S9 na Malé Straně.
Záznam v SISu, sylabus
K přednášce je letos nepovinné cvičení: Cvičení z teorie množin (NAIL124)
Na případných konzultacích se můžeme domluvit osobně nebo e-mailem (kyncl zavináč kam.mff.cuni.cz).
Doporučená literatura:
- [BS] B. Balcar, P. Štěpánek, Teorie množin, Academia, Praha, 2001 (případně dřívější vydání). K dispozici v Půjčovně skript a učebnic MFF UK v Troji. Od 19.3.2020 možnost distanční výpůjčky. Dočasně (od 18.3.2020) také zpřístupněna na webu Národní knihovny: http://kramerius-vs.nkp.cz
- [T++] Dodatky k teorii množin (budou postupně rozšiřované)
Další zdroje:
- Do nekonečna a ještě dál...... - seriál Matematického korespondenčního semináře, vcelku. Jednotlivé kapitoly:
- Díl první - Svět nekonečen - neformální úvod: nekonečna, spočetné množiny, dobře uspořádané množiny, indukce, rekurze
- Díl druhý - Pevné základy - formálnější základy, axiomy, ordinální čísla, přirozená čísla
- Díl třetí - Síla volby - axiom výběru, Zornovo lemma, Cauchyho rovnice, kardinální čísla, příklady na transfinitní rekurzi
- Mirek Olšák, Esence teorie množin - velmi názorná animovaná videa (mírně odlišná terminologie - axiom existence, axiom nekonečna, uspořádání, ...)
- Karel Hrbacek, Thomas Jech: Introduction to Set Theory, 3. edition, Marcel Dekker, 1999
- Thomas Jech, Set theory, Springer, 2003 (Part I)
- Richard Evan Schwartz, Gallery of the infinite, American Mathematical Society, Providence, RI, 2016 (link)
Doporučená cvičení
Témata přednášek:
19.2.
- Úvodní informace, stručná historie teorie množin, paradoxy
- Jazyk teorie množin (a logiky): symboly, formule, rozšíření o další symboly
- Příklady logických axiomů včetně axiomů rovnosti, odvozovací pravidla (logiku budeme používat intuitivně)
- Zermelo-Fraenkelova teorie (ZF)
- Axiom existence množiny
- Axiom extenzionality
26.2.
- Schéma axiomů vydělení, průnik, rozdíl, prázdná množina
- Axiom dvojice, neuspořádaná dvojice {a,b}, jednoprvková množina {a}, uspořádaná dvojice (a,b), (x,y)=(u,v) implikuje x=u a y=v, uspořádaná n-tice
- Axiom sumy, suma množiny a, sjednocení dvou množin a, b, neuspořádaná n-tice
- Axiom potence, potenční množina množiny a
- Schéma axiomů nahrazení
4.3.
- Axiom fundovanosti (regularity)
- Třídy
- Třídové termy, třída určená formulí ("definovatelný soubor množin"), každá množina je třída, ostatní třídy jsou vlastní třídy
- Rozšíření jazyka teorie množin o třídové termy a třídové proměnné, eliminace třídových termů
- Binární třídové operace: průnik, sjednocení, rozdíl
- Univerzální třída V, (absolutní) doplněk třídy
- Relace "být podtřídou", "být vlastní podtřídou"
- Unární třídové operace: suma, průnik, potence
- Univerzální třída není množina
- Průnik množiny a třídy je vždy množina
- Kartézský součin tříd, kartézský součin množin je vždy množina
- Kartézská mocnina X^n jako třída všech uspořádaných n-tic
11.3. (samostatné studium)
[BS] kapitola I, 4.14-4.20, 4.22, 4.25-4.30, 4.32-4.33, 4.36-4.37, 5.1-5.6
- Relace
- (Binární) relace, n-ární relace
- Relace náležení a identity
- Definiční obor (třídy) X, obor hodnot X, obraz třídy Y třídou X, zúžení třídy X na třídu Y; je-li X množina, pak jsou to také množiny
- Inverzní relace, složení relací
- Zkratka pro kvantifikaci přes třídu
- Zobrazení (třídy X do třídy Y, na třídu Y, prosté), třída ^aA všech zobrazení množiny a do třídy A; je-li A množina, je ^aA také množina; je-li a neprázdná a A vlastní třída, je ^aA také vlastní třída
- Uspořádání
- Připomenutí základních vlastností relací (reflexivní apod.) na třídě A, dědičnost
- Uspořádání na třídě A, srovnatelné prvky
- Lineární uspořádání, ostré uspořádání, značení
18.3. (samostatné studium)
[BS] kapitola I, 5.7-5.9, (příklady 5.10-5.12), 5.13 (i)-(ii), 5.16-5.17, 5.26 [T++], 5.27-5.28, (5.32-5.38), 5.42-5.47
- Majoranta, maximální prvek, největší prvek, supremum; největší prvek je vždy maximální, v lineárním uspořádání je maximální prvek třídy maximálně jeden (a pak už je i největší), největší prvek i supremum jsou jednoznačné a lze psát a=max(X), a=sup(X)
- Shora omezená množina, dolní množina, dolní množina určená prvkem x (hlavní ideál určený x), x≤y implikuje inkluzi dolních množin určených x,y
- Poznámka: Dedekindovy řezy na množině racionálních čísel jako definice reálných čísel ([T++] - definice a příklady)
- Dobré uspořádání, je to dědičná vlastnost, každé dobré uspořádání je lineární
- Zopakování základních informací o ekvivalencích (definice, třídy, třídy ekvivalence tvoří rozklad)
- Srovnávání mohutnosti
- Definice pomocí prostých zobrazení: "množiny x,y mají stejnou mohutnost", "množina x má mohutnost menší nebo rovnou mohutnosti y" (x je subvalentní y), "množina x má menší mohutnost než y"
- Relace "mít stejnou mohutnost" je ekvivalence; relace subvalence je reflexivní a tranzitivní, ale ne slabě antisymetrická; relace "mít stejnou mohutnost" implikuje subvalenci
25.3. (samostatné studium)
[BS] kapitola I, 5.48-5.51, [T++]
- Cantorova–Bernsteinova věta, důkaz s využitím lemma o pevném bodě monotónního zobrazení na potenční množině [T++]
- Mohutnost kartézského součinu dvou kopií přirozených čísel je stejná jako mohutnost množiny přirozených čísel (zatím definované intuitivně)
- Mohutnost kartézského součinu se nezmění změnou pořadí "činitelů", jiným uzávorkováním, ani přechodem k jiným "činitelům" stejné mohutnosti
- Mají-li x,y stejnou mohutnost, pak i jejich potenční množiny mají stejnou mohutnost
- Mohutnost potenční množiny x je rovna mohutnosti množiny zobrazení z x do 2
- Jak lze definovat "x je konečná množina"?
1.4. (samostatné studium)
[BS] kapitola I, 6.1-6.2, 6.4, 6.3 (i), 6.3 (ii) 1. část, 5.29-5.31, 6.3 (ii) 2. část, [T++]
- Konečné množiny
- Tarského definice konečné množiny: x je konečná, pokud každá neprázdná podmnožina P(x) má maximální prvek vzhledem k inkluzi
- Množina x je konečná právě tehdy, když každá neprázdná podmnožina P(x) má minimální prvek vzhledem k inkluzi
- Dedekindovsky konečná množina: taková, která má větší mohutnost než každá její vlastní podmnožina [T++]
- Každá konečná množina je i dedekindovsky konečná [T++]. Poznámka, že v ZF nelze dokázat obrácená implikace.
- V konečné uspořádané množině má každá neprázdná podmnožina maximální i minimální prvek
- Každé lineární uspořádání na konečné množině je dobré
- Izomorfismus tříd A,B vzhledem k relacím R, S, počátkové vnoření množiny A do množiny B vzhledem k uspořádáním R, S [T++]
- Každá dvě počátková vnoření A do B vzhledem k dobrým uspořádáním R, S jsou porovnatelná inkluzí [T++]
- Mezi každými dvěma dobře uspořádanými množinami existuje počátkové vnoření, které je izomorfismem jedné z množin na dolní podmnožinu druhé [T++]
- Na konečné množině jsou každá dvě lineární uspořádání izomorfní
8.4. (samostatné studium)
[BS] kapitola I, 6.5-6.14, 2.25, 6.15-6.16, [T++]
- Konečnost se zachovává při přechodu k podmnožině, množině stejné mohutnosti, množině menší mohutnosti
- Sjednocení dvou konečných množin je konečná množina [T++]
- Princip indukce pro konečné množiny [T++]
- Potenční množina konečné množiny je konečná (důkaz indukcí)
- Kartézský součin konečných množin je konečná množina
- Sjednocení konečně mnoha konečných množin je konečná množina [T++]
- Každá konečná množina je srovnatelná co do mohutnosti se všemi množinami
- Přirozená čísla
- Von Neumannova definice přirozených čísel jednotlivě, alternativy [T++]
- Induktivní množina
- Axiom nekonečna
- Množina přirozených čísel jako průnik všech induktivních množin, je to (nejmenší) induktivní množina
- Poznámka o nestandardních modelech přirozených čísel [T++]
15.4. (samostatné studium)
[BS] kapitola I, 6.17-6.23 (i), [T++]
- Funkce následníka
- Princip indukce pro přirozená čísla [T++]
- Prvky přirozeného čísla jsou opět přirozená čísla [T++]
- Relace náležení je na množině přirozených čísel tranzitivní a antireflexivní, a tedy ostré uspořádání [T++]
- Každé přirozené číslo je konečná množina
- Množina x je konečná právě tehdy, když existuje přirozené číslo n, které má stejnou mohutnost jako x
- Množina přirozených čísel a tedy i každá induktivní množina je nekonečná
- Na přirozených číslech jsou relace náležení a vlastní podmnožiny totožné
- Relace náležení je na přirozených číslech trichotomická, a tedy lineární uspořádání
- Relace náležení je na přirozených číslech dobré (ostré) uspořádání
22.4. (samostatné studium)
[BS] kapitola I, 6.23 (ii), 6.24-6.27, 6.28 (a), (b), 6.29-6.30, 6.35-6.36, 6.32, [T++]
- Charakterizace dobrých uspořádání izomorfních přirozeným číslům s relací náležení
- Spočetné množiny
- Množina spočetná, nejvýše spočetná, nespočetná
- Shora omezené podmnožiny přirozených čísel jsou konečné, shora neomezené nekonečné a spočetné; podmnožina spočetné množiny je konečná nebo spočetná
- Lexikografické a maximo-lexikografické uspořádání na množině uspořádaných dvojic přirozených čísel [T++]
- Sjednocení dvou spočetných množin je spočetné, kartézský součin dvou spočetných množin je spočetný
- Důsledky: spočetnost množin celých a racionálních čísel, konečných sjednocení a kartézských součinů spočetných množin, Dirichletův princip pro konečná sjednocení a rozklady
- Poznámka, že v ZF nelze obecně dokázat spočetnost spočetného sjednocení spočetných množin, ani existenci spočetné podmnožiny v každé nekonečné množině [T++]
- Cantorova věta a reálná čísla
- Znění Cantorovy věty: potenční množina x má vždy větší mohutnost než x; jednodušší část důkazu (existence prostého zobrazení x do potenční množiny x)
29.4. (samostatné studium)
[BS] kapitola I, 6.32-6.34, 6.42-6.43, 6.45, (6.46), 6.47, 7.1-7.5, 4.38-4.40, 4.42-4.44, [T++]
- Těžší část důkazu Cantorovy věty, dokonce neexistuje zobrazení z x na potenční množinu x (diagonální metodou) [T++]
- Důsledky: potenční množina přirozených čísel je nespočetná, univerzální třída není množina
- Množina reálnách čísel má stejnou mohutnost jako potenční množina přirozených čísel (mohutnost kontinua) [T++]
- Množina reálných algebraických čísel je spočetná (za předpokladu spočetnosti množiny konečných posloupností přirozených čísel)
- Hypotéza kontinua
- Axiom výběru
- Problém existence prostého zobrazení g z Rng(f) do Dom(f) pro obecnou funkci f, splňujícího f(g(y))=y (tj. g je zprava inverzní k f)
- Princip výběru: každý rozklad množiny má výběrovou množinu (transverzálu) [T++]
- Axiom výběru (AC): na každé množině existuje selektor [T++]
- Příklady tvrzení ekvivalentních AC, příklady důsledků AC v různých oborech matematiky [T++]
- Indexovaný soubor množin
- Sjednocení, průnik a kartézský součin souboru množin [T++]
13.5. (samostatné studium)
[BS] kapitola I, 7.6, 7.7 (b), 7.8-7.10, 7.12 [T++], (7.13), 7.14, 7.15 (a), (7.16), 7.21, (7.22), 7.23, (7.24)
- Ekvivalentní tvrzení: princip výběru; axiom výběru; existence funkce, která je podmnožinou dané množinové relace a má stejný definiční obor; kartézský součin neprázdného souboru neprázdných množin je neprázdný
- (AC) Sjednocení spočetného souboru (nejvýše) spočetných množin je (nejvýše) spočetná množina
- Poznámka, že bez AC lze bezesporně předpokládat, že množina reálných čísel je spočetné sjednocení spočetných množin
- Princip maximality (PM), také nazývaný Zornovo lemma [T++]
- Princip trichotomie (PT) - relace subvalence je trichotomická (tj. libovolné dvě množiny lze porovnat podle mohutnosti)
- Odvození PT z PM
- (PT) Každá nekonečná množina má spočetnou podmnožinu (tedy je dedekindovsky nekonečná)
- Princip dobrého uspořádání (WO)
- Odvození AC z WO
20.5. (samostatné studium)
[BS] kapitola II, 1.1-1.16, 1.18-1.21, 1.26-1.29, 2.1-2.8, [T++]
- Ordinální čísla [T++]
- Tranzitivní třída, příklady: přirozená čísla, množina všech přirozených čísel, univerzální třída
- Průnik a sjednocení tranzitivních tříd jsou tranzitivní, průnik a suma třídy tranzitivních množin jsou tranzitivní
- Je-li X tranzitivní třída, pak náležení je tranzitivní na X právě tehdy, když každý prvek X je tranzitivní množina (důkaz jako cvičení)
- Ordinální číslo (ordinál), příklady: přirozená čísla a množina všech přirozených čísel
- Třída On, je to tranzitivní třída
- Náležení je antireflexivní na On, průnik ordinálů je ordinál, náležení a ostrá inkluze jsou na On stejné relace (důkaz jako cvičení)
- Náležení je dobré ostré uspořádání na On; dokonce každá neprázdná podtřída On má nejmenší prvek (důkaz této části jako cvičení)
- On je vlastní třída
- Je-li X tranzitivní vlastní třída, dobře ostře uspořádaná náležením, pak X=On (důkaz jako cvičení)
- Značení ordinálů řeckými písmeny, relace < na On
- Množina ordinálů je ordinál právě tehdy, když je tranzitivní
- Průnik neprázdné třídy ordinálů je její nejmenší prvek, suma množiny ordinálů je její supremum v (On,<)
- Množina všech přirozených čísel (omega) je supremum omega v (On,<) (důkaz jako cvičení)
- Následník a předchůdce, izolované a limitní ordinály
- Věta o existenci a jednoznačnosti izomorfismu dobře uspořádané množiny s ordinálem (bez důkazu), typ dobrého uspořádání
- Princip transfinitní indukce, dvě verze
- Věta o konstrukci transfinitní rekurzí, několik verzí, bez důkazu
- Příklad aplikace transfinitní rekurze při odvození WO z AC (náznak důkazu)