Nekonečné množiny (NMAI074), ZS 2024/2025

Jan Kynčl, KAM (kyncl zavináč kam.mff.cuni.cz)

Přednáška se koná ve středu v 17:20 v S11 na Malé Straně.

Stránka 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

• [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. Bude pokrývat zhruba první dvě třetiny semestru.
• S. Shelah and A. Soifer, Axiom of choice and chromatic number of the plane - příklad "vzdálenostního" grafu, jehož barevnost závisí na zvolených axiomech
• Carl W. Lee, The Banach-Tarski Paradox: How to Disassemble a Ball the Size of a Pea and Reassemble it into a Ball the Size of the Sun - aneb jak udělat z komára velblouda

• Mirek Olšák, 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
• Mirek Olšák, Esence teorie množin - animovaná videa (ordinální čísla, Zornovo lemma, transfinitní rekurze)
• 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í; vysvětlení, proč můžeme rekurzi formulovat i pro třídové funkce
• The axiom of well-ordered replacement is equivalent to full replacement over Zermelo + foundation - axiom nahrazení pro dobře uspořádané množiny implikuje axiom nahrazení i bez AC
• 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
• M. Loebl, Hercules and Hydra - zesílení věty Kirbyho a Parise: v PA nelze dokázat, že konkrétní strategie MAX je vyhrávající
• M. Loebl and J. Matoušek, Hercules versus hidden Hydra helper - "krátká" Herkulova strategie, která porazí hydru v počtu kroků omezeném věžovitou funkcí; v PA tedy lze dokázat, že je vyhrávající
• Hardy Hirarchy Calculator - výpočet hodnot funkcí z Hardyovy hierarchie, používá trochu jinou definici fundamentální posloupnosti
• Cantor's_Attic - encyklopedie nekonečen: velká ordinální a kardinální čísla, hierarchie funkcí
• How to write aleph by hand
• Dana Scott, A proof of the independence of the continuum hypothesis - elementárnější důkaz nezávislosti hypotézy kontinua modelováním reálných čísel jako náhodných veličin
• 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:

2.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í
• Princip transfinitní indukce (znění)

9.10.

• 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

16.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
• Monotonie součinu
• Distributivita násobení zleva

23.10.

• Existence rozdílu "zprava"
• Dělení se zbytkem
• Spojitost (normalita) součtu a součinu (důkaz jako cvičení)
• 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 (náznak důkazu), alternativní rozklady ordinálu, rozklady podle libovolného základu
• Ordinál epsilon_0

30.10.

• Hydra a Herkules, existence vyhrávajících strategií bez důkazu (cvičení)
• Goodsteinovy posloupnosti, Goodsteinova věta, formální důkaz bez ověření všech vzorečků
• Věta Kirbyho-Parise bez důkazu

6.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í
• Následník a předchůdce kardinálu, limitní kardinál

13.11.

• 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
• Kofinál limitního ordinálu alfa splňuje cf(cf(alfa))=cf(alfa)
• Kofinál limitního ordinálu je vždy kardinál

20.11.

• Regulární a singulární kardinál, příklady
• Kofinál limitního ordinálu je tedy regulární kardinál
• Poznámka o bezespornosti tvrzení "alef_0 je jediný regulární kardinál" a "kofinál každého limitního ordinálu je omega" 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 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
• Zobecněná hypotéza kontinua
• Kardinální aritmetika (v ZFC)
• Kardinální mocnina a její základní vlastnosti
• Výpočet kardinální mocniny v jednoduchých případech
• Mohutnost kontinua