Teorie množin (NAIL063), LS 2018/2019

Přednáška se koná ve čtvrtek v 12:20 v S4 na Malé Straně.
Záznam v SISu, sylabus

Na případných konzultacích se můžeme domluvit osobně nebo e-mailem (kyncl zavináč kam.mff.cuni.cz).

Doporučená literatura:

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

• 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 - 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:

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

28.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í

7.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
• Relace
• (Binární) relace, n-ární relace

14.3.

• 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í
• 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í

21.3.

• 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
• Dedekindovy řezy na množině racionálních čísel jako definice reálných čísel
• Dobré uspořádání, každé dobré uspořádání je lineární
• Zopakování základních informací o ekvivalencích
• 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

28.3.

• Cantorova–Bernsteinova věta, důkaz s využitím lemma o pevném bodě monotónního zobrazení na potenční množině
• 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"?

4.4.

• 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
• Každá konečná množina je i dedekindovsky konečná. 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

11.4.

• Každá dvě počátková vnoření A do B vzhledem k dobrým uspořádáním R, S jsou porovnatelná inkluzí
• 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é
• Na konečné množině jsou každá dvě lineární uspořádání izomorfní
• 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
• Princip indukce pro konečné množiny
• Potenční množina konečné množiny je konečná (důkaz indukcí)

18.4.

• 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
• 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ě
• 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
• Funkce následníka
• Princip indukce pro přirozená čísla
• Prvky přirozeného čísla jsou opět přirozená čísla

25.4.

• Relace náležení je na množině přirozených čísel tranzitivní a antireflexivní, a tedy ostré uspořádání
• 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í

2.5.

• 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
• 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ě
• 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)

9.5.

• Těžší část důkazu Cantorovy věty, dokonce neexistuje zobrazení z x na potenční množinu x (diagonální metodou)
• 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 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)
• Axiom výběru (AC): na každé množině existuje selektor
• Příklady tvrzení ekvivalentních AC, příklady důsledků AC v různých oborech matematiky
• Indexovaný soubor množin
• Sjednocení, průnik a kartézský součin souboru množin

16.5.

• 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
• 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
• Princip dobrého uspořádání (WO)

23.5.

• Odvození AC z WO
• Ordinální čísla
• Tranzitivní třída, např. 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), např. přirozená čísla a množina všech přirozených čísel, třída On
• On je 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)