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
Další zdroje:
- 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
Průběh přednášky bude podobný jako minule.
Příklady k procvičení
Témata přednášek:
4.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í
11.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
18.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
25.10.
- 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 (náznak důkazu), alternativní rozklady ordinálu, rozklady podle libovolného základu
- Ordinál epsilon_0
1.11.
- 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
8.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í
22.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
- Poznámka o bezespornosti tvrzení "kofinál každého limitního ordinálu je omega" v ZF
- 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
29.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" 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
6.12.
- 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 mohutnosti 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
- Königova nerovnost
- Důsledky Königovy nerovnosti pro kardinální aritmetiku: cf(kappa^lambda)>lambda, lambda^{cf(lambda)}>lambda
- Možné hodnoty funkce 2^{alef_alfa} (informativně)
13.12.
- 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"
- Princip kompaktnosti pro barevnost nekonečných grafů (zatím jen znění)
- Princip kompaktnosti pro částečné selektory na systému konečných množin (zatím jen znění)
- Důsledek pro obarvování nekonečných hypergrafů
20.12.
- Princip kompaktnosti pro částečné selektory na systému konečných množin, důkaz z principu maximality
- Nekonečná Hallova věta (cvičení)
- 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
- Dirichletův princip pro regulární a singulární kardinál jako speciální případ ramseyovské věty
- Konečná Ramseyova věta (znění), nekonečná Ramseyova věta pro spočetné množiny
- Věta Parise a Harringtona zesilující Ramseyovu větu, důkaz z nekonečné Ramseyovy věty pomocí principu kompaktnosti
3.1.
- Důsledek nekonečné Ramseyovy věty pro řetězce a antiřetězce v nekonečných uspořádaných množinách (cvičení)
- 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
- Spočetný axiom výběru a axiom měřitelnosti
- Náznak definice Lebesgueovy míry na reálných číslech, její vyjádření pomocí pokrytí otevřenými intervaly
- Příklad vzdálenostního grafu G na reálných číslech, který má v ZFC barevnost 2 a v ZF + AC_{alef_0} + LM nespočetnou
10.1.
- 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