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

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

Přednáška se koná ve středu v 17:20 v S6 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í
• 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
• 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