Nekonečné množiny (NMAI074), ZS 2018/2019
Wednesdays at 10:40 in the corridor on the 2nd floor. If there is at least one student who does not understand Czech, the lectures will switch to English; but students may still ask questions in Czech during the lectures.
Jan Kynčl, KAM (kyncl zavináč kam.mff.cuni.cz)
Přednáška se koná ve středu v 10:40 na chodbě ve 2. patře na Malé Straně.
Záznam v SISu, sylabus, literatura
Přednáška navazuje na úvodní přednášku Teorie množin (NAIL063). V první části se zaměříme na ordinální a kardinální aritmetiku; ve druhé části zejména na kombinatorické vlastnosti nekonečných množin a grafů a důsledky axiomu výběru v kombinatorice a geometrii. Přitom si ukážeme některá kombinatorická tvrzení, jejichž platnost závisí na zvolených axiomech (axiom nekonečna, axiom výběru).
Na případných konzultacích se můžeme domluvit osobně nebo e-mailem.
Doporučená literatura (bude aktualizována v průběhu semestru):
Další zdroje:
- Do nekonečna a ještě dál...... - seriál Matematického korespondenčního semináře, vcelku. K přednášce je tematicky nejbližší 3. díl:
- Díl třetí - Síla volby - axiom výběru, Zornovo lemma, Cauchyho rovnice, kardinální čísla, příklady na transfinitní rekurzi
- Karel Hrbacek, Thomas Jech: Introduction to Set Theory, 3. edition, Marcel Dekker, 1999
- Thomas Jech, Set theory, Springer, 2003 (Part I)
-
Transfinite recursion as a fundamental principle in set theory - ekvivalence transfinitní rekurze a axiomu nahrazení
- A simple proof of Zorn's lemma, Zorn's lemma - důkazy Zornova lemmatu bez transfinitní rekurze a ordinálních čísel
- Zornovo lemma na proofwiki - 2 důkazy, bez rekurze i s rekurzí
- L. Kirby and J. Paris, Accessible Independence Results for Peano Arithmetic - důkaz věty o Goodsteinových posloupnostech a o hydře, nedokazatelnost v Peanově aritmetice s využitím externích výsledků z logiky
- Will Sladek, The Termite and the Tower: Goodstein sequences and provability in PA - Goodsteinovy posloupnosti, rychle rostoucí hierarchie funkcí, ekvivalence Peanovy aritmetiky a teorie konečných množin
- Cantor's_Attic - encyklopedie nekonečen: velká ordinální a kardinální čísla, hierarchie funkcí
- How to write aleph by hand
- B. Bukh, Walk through Combinatorics: Compactness principle - princip kompaktnosti pro obarvování hypergrafů
- B. Osofsky and S. Adams, Problem 6102 and solution - netriviální kombinace rotací o 180 a 120 stupňů kolem os svírajících úhel 45 stupňů nikdy není identita
Příklady k procvičení
Témata přednášek:
3.10.
- Úvodní informace, opakování některých pojmů, axiomů a tvrzení z teorie množin
- Důkaz věty o typu dobrého uspořádání
10.10.
- Princip transfinitní indukce (znění)
- Věta o konstrukci transfinitní rekurzí i s důkazem
- Princip dobrého uspořádání (znění), poznámka o zobecnění na třídy
- Princip maximality (Zornovo lemma) i s důkazem transfinitní rekurzí; včetně verze, kde místo řetězců stačí dobře uspořádané podmnožiny
17.10.
- Ordinální aritmetika
- Ordinální funkce (rostoucí, neklesající)
- Rostoucí ordinální funkce roste aspoň tak rychle jako identita
- Ordinální typ podmnožiny B množiny A je menší nebo roven ordinálnímu typu A (i pro vlastní podmnožinu může nastat rovnost typů)
- Uzavřená třída ordinálů, spojitá rostoucí ordinální funkce (normální ordinální funkce)
- Základní vlastnosti normálních funkcí
- Věta o pevných bodech normální funkce
- Ordinální součet a součin, základní vlastnosti, příklady nekomutativnosti
- Monotonie součtu
24.10. (samostatná četba [BS, str. 154-159, 3.16-3.32])
- Monotonie součinu, distributivita násobení zleva
- Existence rozdílu "zprava"
- Dělení se zbytkem
- Spojitost (normalita) součtu a součinu
- Ordinální mocniny - rekurzivní definice, základní vlastnosti, monotonie, spojitost, násobení a sčítání v exponentu
- Věta o rozvoji ordinálního čísla v mocninách omega, alternativní rozklady ordinálu
31.10.
- Ordinál epsilon_0
- Hydra a Herkules
- Goodsteinovy posloupnosti, Goodsteinova věta, formální důkaz bez ověření všech vzorečků
7.11.
- Hierarchie rychle rostoucích funkcí: fundamentální posloupnost limitního ordinálu, Hardyova hierarchie, rychle rostoucí hierarchie
- Vyjádření Goodsteinovy funkce pomocí funkcí z rychle rostoucí hierarchie (bez důkazu)
- Kardinální čísla (v ZF)
- Kardinální čísla jako podtřída ordinálních čísel, mohutnosti dobře uspořádaných množin, konečné a spočetné kardinály
- Třída Cn všech kardinálních čísel je uzavřená
- Ke každému kardinálu existuje větší kardinál, a tedy třída Cn je vlastní
14.11.
- Následník a předchůdce kardinálu, limitní kardinál
- Funkce alef číslující nekonečné kardinály
- Mohutnost kartézského součinu alef_alfa x alef_alfa je alef_alfa
- Kardinální součet a součin a jeho výpočet
- Příklady rozkladů kardinálů na podmnožiny, (ne)zobecnitelnost Dirichletova principu
- Kofinální množina, kofinál ordinálního čísla, příklady ordinálů s kofinálem omega
21.11.
- Regulární a singulární kardinál
- Kofinál limitního ordinálu je vždy regulární kardinál
- Poznámka o bezespornosti tvrzení "alef_0 je jediný regulární kardinál" v ZF
- Kardinál kappa je singulární právě tehdy, když je sumou méně než kappa množin mohutnosti menší než kappa (doplněn a opraven důkaz zpětné implikace z [BS])
- Důsledek: zobecněný Dirichletův princip pro regulární kardinály
- V ZFC je má sjednocení nejvýše alef_alfa množin mohutnosti nejvýše alef_alfa mohutnost nejvýše alef_alfa (důkaz jako cvičení)
- Důsledek: V ZFC je alef_{alfa+1} vždy regulární kardinál
- Slabě nedosažitelný kardinál, je pevným bodem funkce alef (ale ne nejmenším), poznámka o nedokazatelnosti jeho existence v ZFC, nedosažitelný kardinál
- Hypotéza kontinua, poznámka o možných hodnotách alfa, pro které je bezesporné tvrzení 2^{alef_0}=alef_alfa
- Zobecněná hypotéza kontinua
28.11.
- Kardinální aritmetika (v ZFC)
- Kardinální mocnina a její základní vlastnosti
- Mohutnost kontinua, příklady (počet otevřených podmnožin reálných čísel, počet spojitých funkcí mezi reálnými čísly)
- (Nekonečný) součet a součin souboru kardinálních čísel
- Mohutnost množiny lambda-prvkových podmnožin a množiny podmnožin muhutnosti menší než lambda
- Výpočet (nekonečného) součtu kardinálních čísel, charakterizace singulárních kardinálů pomocí nekonečného kardinálního součtu
- Nerovnost mezi kardinálním součtem a součinem, začátek důkazu
5.12.
- Důkaz nerovnosti mezi kardinálním součtem a součinem aspoň dvou kardinálních čísel
- Königova nerovnost
- Důsledky pro kardinální aritmetiku, možné hodnoty funkce 2^{alef_alfa}
- Nekonečná kombinatorika
- Strom jako uspořádaná množina, kde množiny předchůdců jsou dobře uspořádané, příklady stromů
- Königova věta (v ZFC): strom výšky omega, jehož každá hladina je konečná, má kofinální větev
- Poznámka o zobecněních Königovy věty na stromy větších výšek a "šířek"
12.12.
- Princip kompaktnosti pro částečné selektory na systému konečných množin, důkaz z principu maximality
- Důsledek pro obarvování nekonečných hypergrafů, nekonečná Hallova věta
- Nekonečné ramseyovské věty
- Homogenní množina pro rozklad množiny r-tic nebo pro funkci z množiny r-tic
- Rozkladová šipka jako zkrácený zápis ramseyovských vět
- Konečná Ramseyova věta (znění), nekonečná Ramseyova věta pro spočetné množiny
19.12.
- Věta Parise a Harringtona zesilující Ramseyovu větu, důkaz z nekonečné Ramseyovy věty pomocí principu kompaktnosti
- Důsledek nekonečné Ramseyovy věty pro řetězce a antiřetězce v nekonečných uspořádaných množinách
- Sierpinského věta o neexistenci nespočetné homogenní množiny při obarvování dvojic reálných čísel
- Zobecnění Sierpinského věty pro následníky nekonečných kardinálů (bez důkazu)
- Věta Erdőse a Rada zobecňující Ramseyovu větu pro následníky nespočetných kardinálů (bez důkazu)
- Protipříklad na zobecnění Ramseyovy věty pro obarvování spočetných podmnožin
- Slabě kompaktní kardinál, Ramseyův kardinál, náznak důkazu, že alef_0 není Ramseyův
- Barevnost nekonečných grafů
- Problém určení chromatického čísla roviny
- Příklad vzdálenostního grafu G na reálných číslech, který má v ZFC barevnost 2
- Spočetný axiom výběru a axiom měřitelnosti
9.1.
- Náznak definice Lebesgueovy míry na reálných číslech, její vyjádření pomocí pokrytí otevřenými intervaly
- Barevnost grafu G v ZF + AC_{alef_0} + LM je nespočetná
- Paradoxní rozklady
- Shodnost, přeskládatelnost pomocí n částí, základní vlastnosti
- Zobecnění Cantorovy–Bernsteinovy věty pro přeskládatelnost
- Jednotková sféra lze pomocí 2 částí přeskládat na doplněk své spočetné podmnožiny
- Existence dvou "nezávislých" rotací sféry o 180 a 120 stupňů (bez důkazu)
- Banachův–Tarského paradox: jednotková koule lze pomocí 10 částí přeskládat na dvě disjunktní jednotkové koule