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

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

Přednáška se koná v úterý v 17:20 v S10 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

• Jakub Smolík, Infinite Sets

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

30.9.

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

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

14.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
• Přehled základních tvrzení o ordinální aritmetice (podrobnosti jako doporučená samostatná četba [BS, str. 154–159, 3.15–3.34])
  • Monotonie součtu
  • Monotonie součinu
  • Distributivita násobení zleva
  • 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 (Cantorova normální forma) (znění), alternativní rozklady ordinálu, rozklady podle libovolného základu
  • Ordinál epsilon_0

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