Apliktm - prednášky LS 2022/23

[Martin Sleziak]

Sem budem priebežne písať, čo sme stihli na jednotlivých prednáškach. Občas pridám aj nejaké linky na veci týkajúce sa toho, čo sme práve prebrali.

Toto vlákno by som chcel rezervovať naozaj iba na to, že tu budem písať obsah prednášok. Keď budete chcieť na fórum napísať nejakú vec k nejakej konkrétnej veci, ktorá bola na prednáške, založte na to nový topic.

Ak sa chcete pozrieť na to, čo som stihol prebrať po minulé roky:
viewtopic.php?t=1639
viewtopic.php?t=1144
viewtopic.php?t=1026
viewtopic.php?t=594

[Martin Sleziak]

1. prednáška (16.2.):
Snažil som sa aspoň trochu na začiatku povedať niečo o tom, na aké veci sa Zornova lema a transfinitná indukcia dajú použiť. Ako príklad som použil Cauchyho funkcionálnu rovnicu.

Trochu som si pomáhal analógiou s tým, ako to funguje, keď sa človek začína učiť používať matematickú indukciu ako dôkazovú metódu. Keďže som medziiným spomenul Cauchyho indukciu, tak pridám linku na iný topic na fóre, kde sa takýto typ indukcie spomína: viewtopic.php?t=1642

Dám sem ešte linky na dva články z blogu Tima Gowersa, ktoré sa týkajú zhruba toho, kedy sa dá použiť Zornova lema (a je tam niečo aj o transfinitnej indukcii).

• How to use Zorn's Lemma: blog, tricki
• Just-do-it proofs: blog, tricki

K tomu, že som si ako úvodný príklad vybral práve Cauchyho rovnicu, ma inšpiroval práve tento blog.

Dobre usporiadané množiny. Definícia dobre usporiadanej množiny a to, že na nich funguje indukcia.
V dobre usporiadanej množine pre každý prvok (s výnimkou najväčšieho) existuje nasledovník. Nemusí ale existovať predchodca.
Ukázali sme si pár príkladov dobre usporiadaných množín. (Nerobil som lexikografický súčin dobre usporiadaných množín - ale niekedy sa k nemu asi vrátime.)

[Martin Sleziak]

2. prednáška (23.2.):
Ekvivalenty axiómy výberu. Prešli viacero podmienok, o ktorých je jednoduché ukázať, že sú ekvivalentné s axiómou výberu. (Dokázali sme existenciu selektora a jednostranný inverz k surjekcii, ostatné sme len spomenuli.)
Okrajovo som spomenul aj súvis medzi spojitosťou a sekvenciálnou spojitosťou: viewtopic.php?t=1656 (K nemu sa možno ešte niekedy vrátime.)
Potom sme sformulovali viacero ďalších ekvivalentných tvrdení, ktoré sú tiež ekvivalentné s axiómou výberu, ale tu už budú dôkazy náročnejšie. Konkrétne sú to princíp dobrého usporiadania, Zornova lema a princíp maximality. (Princípom maximality sa však nebudeme veľmi zaoberať.)
Ukázali sme, že z WO vyplýva AC. (To bol vcelku ľahký dôkaz.)
Potom sme ukázali, že zo ZL vyplýva AC. (Čo bola vlastne prvá ukážka typického dôkazu pomocou Zornovej lemy, na ktorú sme narazili na tejto prednáške.)
Keďže dôkaz je iný ako v texte, tu je aspoň stručný sumár.

Spoiler:

$\newcommand{\mc}[1]{\mathcal{#1}}$Pracovali sme s čiastočne usporiadanou množinou $(\mc P,\subseteq)$, kde
$$\mathcal P=\{A\subseteq\bigcup\mathcal S; (\forall S\in\mc S) |A\cap S|\le 1\},$$
t.j. s množinami, ktoré vyberajú jeden prvok aspoň z niektorých množín systému $\mathcal S$.

Overili sme, že pre každý reťazec $\mathcal R$ v $\mc P$ je jeho zjednotenie $\bigcup\mc R$ opäť prvkom $\mc P$. (Trochu som sa na tomto mieste snažil zdôrazniť, že sme naozaj v dôkaze využili, že $\mc R$ je reťazec.)
Tým sú overené predpoklady Zornovej lemy, a teda existuje nejaký maximálny prvok $V$ v čiastočne usporiadanej množine $(\mc P,\subseteq)$. Ukázali sme, že $V$ potom už musí byť výberová množina, t.j. má s každý $S\in\mc S$ jednoprvkový prienik. (Ukazovali sme to sporom. Ak by pre niektoré $S_0$ bol prienik prázdny, tak by sme vedeli dostať $V'=V\cup\{x_0\}$ také, že $V'\in\mc P$, čo je spor s maximalitou.)

Na konci sme hovorili niečo o tom, či sme v dôkazoch na mieste, kde sme si vybrali (značili) konkrétny prvok $x_0$ s nejakou vlastnosťou používali AC, alebo pri jednom výbere sa dá bez nej aj zaobísť: viewtopic.php?t=1948
(Aj keď o tomto sme hovorili naozaj iba veľmi stručne.)

[Martin Sleziak]

3. prednáška (2.3.):
Ekvivalenty axiómy výberu.
Zaoberali sme sa trochu tým, ako je to s AC, WO, ZL pre prázdnu množinu. (Poučenie, ktoré si treba odniesť: Pri používaní Zornovej lemy si treba dať pozor aj na to, či je neprázdna. Inými slovami, či aj prázdny reťazec má horné ohraničenie.)
Ešte raz sme ukázali, že ZL $\Rightarrow$ AC. (Tentokrát pomocou selektorov.)
Na chvíľu som sa vrátil aj k téme z konca predošlej prednášky - o tom, že ak "vyberáme" jeden prvok, tak vlastne AC nepoužívame: viewtopic.php?t=1948
Ukázali sme, že ZL $\Rightarrow$ WO. (Dôkaz, že z axiómy výberu vyplýva Zornova lema urobíme, keď budeme mať k dispozícii ordinály a transfinitnú indukciu.)
Dobre usporiadané množiny. Videli sme, že lexikografický súčin DUM je opäť DUM. (A spomenul som, že podobne by sa dal urobiť súčet dobre usporiadaných množín.)
Pripomenul som text P. Zlatoš: O dobrom usporiadaní a axióme výberu (ktorý ste videli na inom predmete) - kde je tiež definovaná lexikografická suma.
Spomenul som, že do03 je taká, kde sa dá použiť Zornova lema (na dôkaz porovnateľnosti kardinalít ľubovoľných dvoch množín).

[Martin Sleziak]

4. prednáška (9.3.):
Na začiatku sme sa trochu rozprávali o dôkaz AC $\Rightarrow$ ZL - s tým, že teraz sme ho iba naznačili a poriadne ho spravíme, keď budeme mať k dispozícii transfinitnú indukciu. (V texte sú aj nejaké zdroje, kde sa dá nájsť dôkaz Zornovej lemy bez použitia ordinálov a transfinitnej indukcie.)

Dokázali sme Hahn-Banachovu vetu.

Ako ukážku použitia ZL niekedy zvyknem robiť aj Alexandrovu vetu o subbáze. (Pomocou nej sa dá dokázať Tichonovova veta.) Tento dôkaz ste však videli na predmete Všeobecná topológia, tu sme ho teda preskočili.

Viaceré ďalšie výsledky, ktoré sa dajú dokazovať pomocou Zornovej lemy, sú spomenuté tu: viewtopic.php?t=620

Existencia nemerateľnej množiny. (Vitaliho konštrukcia.)

V súvislosti s existenciou nemerateľných množín je azda vcelku zaujímavý aj Banach-Tarského paradox.

[Martin Sleziak]

5. prednáška (16.3.):
Vrátili sme sa k dobre usporiadaným množinám. Ukázali sme, že pre monotónne injektívne zobrazenie $f\colon X\to X$ platí $x\le f(x)$ a z toho nejaké dôsledky o jednoznačnosti izomorfizmov. Nakoniec sme sa dostali k základnej vete o dobre usporiadaných množinách: Pre ľubovoľné dve d.u.m. platí, že niektorá z nich je izomorfná s počiatočným úsekom druhej. (V podstate sme spravili časť 5.1 z apliktm.pdf. Keďže sa často odvolávam na tento text, tak spomeniem, že celá kapitola o ordinálnych číslach by si zaslúžila poriadnejšie prepísať a zreorganizovať a veľa vecí tam zatiaľ úplne chýba. Ale potiaľto sa asi vcelku dá čítať, akurát s tým, že dôkaz vety 5.1.5 tam napísaný nie je.)

Povedali sme si tiež, ako pomocou základnej vety o dobre usporiadaných množinách a WO dostaneme porovnateľnosť kardinalít pre ľubovoľné dve množiny. (T.j. vždy platí $|A|\le|B|$ alebo $|B|\le|A|$.) To isté sa dá dokázať nie moc ťažko aj pomocou ZL. (Je to jedno z cvičení v texte a súčasne jedna z domácich úloh, ktoré sa dajú odovzdávať.)

Ukázali sme si ešte izomorfizmus medzi dobre usporiadanou množinou $(A,\le)$ a $(\{A_a; a\in A\}, \subseteq)$. (Spomenuli sme, ako to súvisí s reprezentáciou čiastočne usporiadaných množín.)

[Martin Sleziak]

6. prednáška (23.3.):
Spomenul som Banach-Tarského paradox. (O ktorom som nestihol ni4 povedať, keď sme dokazovali existenciu nemerateľných množín.)

Spojitosť a sekvenciálna spojitosť: viewtopic.php?t=1656
T.j. ukázali sme si, kde sa v dôkaze využíva AC a tiež sme si ukázali, ako že pre globálnu spojitosť vieme túto ekvivalenciu dokázať aj bez použitia axiómy výberu.

Ordinálne čísla:
Veci, ktoré sme preberali dnes, síce nie sú v texte s poznámkami k prednáške - ale snáď sa to aspoň trochu dá sledovať na základe slajdov: 52ordnaiv.pdf.

Ak $(A,\le)$ je dobre usporiadaná množina, tak pre každé $a\in A$ nastane niektorá z možností:

• $a=\min A$ (t.j. $a$ je najmenší prvok množiny $A$)
• $a=S(b)$ pre nejaké $b\in A$ (t.j. $a$ je nasledovník nejakého prvku);
• $a=\sup\{b\in A; b<a\}$

Popritom sme spomenuli, že nasledovník $S(b)$ existuje - ak $b$ nie je maximálny prvok. A že každá zhora ohraničená podmnožina v d.u.m. má suprémum.

Ukázali sme ešte raz - teraz indukciou na dobre usporiadanej množine - že pre monotónnu injekciu $A\to A$ máme $(\forall a\in A)a\le f(a)$.

Každý ordinál má nasledovníka.
Ak máme množinu dobre usporiadaných množín, tak existuje d.u.m., do ktorej sa všetky dajú vnoriť ako počiatočné úseky. (Z toho dostaneme, že pre každú množinu ordinálov existuje suprémum.)
Konštrukcia, ktorú sme urobili, je špeciálny prípad induktívnej limity. (Tu sme ale vynechali veľa detailov.)
To isté ešte ukážeme inak - na základe výsledku, ktorý sme stihli dokázať ako posledný: Nech $(A,\le)$ a $(B,\le)$ sú dobre usporiadané množiny, pričom $A$ je izomorfná s nejakou podmnožinou množiny $B$. Potom $A$ je izomorfná s počiatočným úsekom množiny $B$.

[Martin Sleziak]

7. prednáška (30.3.):
Ordinálne čísla:
Zadefinovali sme $\sum\limits_{i\in I} (A_i,\le_i)$ pre dobre usporidané množiny $(I,\le)$ a $(A_i,\le_i)$ (lexikografická suma).
Pomocou nej sme ešte raz ukázali, že systém dobre usporiadaných množín vieme vložiť do jednej d.u.m. ako podmnožiny - a teda aj ako počiatočné úseky. Potrebovali sme tu však dobré usporiadanie na indexovej množine $I$ - jedna možnosť by bola použiť WO; ako sa to dá urobiť bez AC som nechal ako cvičenie: du04.pdf.
Vieme teraz ukázať, že aj pre ľubovoľný systém ordinálov máme nejakú množinu, do ktorého ho môžeme vnoriť.
Z toho sme napríklad už vedeli dostať:
* Každá množina ordinálov má suprémum.
* Každá množina ordinálov je dobre usporiadaná.
* Ordinály tvoria vlastnú triedu. (Wikipédia: Burali-Forti paradox)

Kardinalita počiatočných vlastných úsekov.
Dokázali sme: Pre ľubovoľnú dobre usporiadanú množinu $(A,\le)$ máme dobré usporiadanie $\le^*$ také, že počiatočné úseky majú kardinalitu menšiu ako množina $A$.
Na konci som povedal ešte niečo o taktomto príklade: Chceme podmnožinu $A\subseteq\mathbb Q\times\mathbb Q$ takú, že všetky vertikálne rezy budú konečné a horizontálne nekonečné.
Dá sa urobiť aj o čosi viac - mal som to radšej sformulovať takto: $\mathbb Q\times\mathbb Q$ vieme rozdeliť na zjednotie dvoch disjunktných množín $V$ a $H$ tak, jedna z nich bude mať konečné všetky vertikálne a druhá všetky horizontálne rezy. (To je vlastnše úloha 6.1.2 v poznámkach k prednáške).
Túto verziu som opäť dal ako úlohu na stránku: du05.pdf.
Robil som to ako ukážku toho, že aj pri konštrukcii matematickou indukciou sa niekedy hodí to, že v každom kroku indukcie sme použili menej objektov než je kardinalita celej množiny. To sa trochu podobá na vetu, ktorú sme práve videli - a pri dôkazoch transfinitnou indukciou sa takéto niečo vyskytne viackrát.

Ešte drobné poznámky:
Pridám sem zatiaľ linku na post, kde sú zhrnuté nejaké vlastnosti ordinálov (a je tam aj niečo k von Neumannovej konštrukcii): viewtopic.php?t=1175
Nabudúce sa už chceme dostať k transfinitnej indukcii a transfinitnej rekurzii.
Niekedy sa ešte ale budem chcieť aspoň stručne vrátiť aj k porovnaniu tejto (naivnej) definície ordinálov s von Neumannovou definíciou. (Tú určite nechceme robiť detailne - stačí nám, že sme ordinály dostali jedným spôsobom. Ale patrilo by sa o nej aspoň niečo spomenúť.)
Aj dnes platí to, že to čo sme preberali nie je spísané v poznámkach, ktoré sú na stránke. (Ale sú tam aspoň slajdy - na ich základe si človek možno môže trochu pripomenúť čo sa robilo.)
Transfinitná indukcia a jej aplikácie už v poznámkach sú aspoň nejako. (Samozrejme, aj tam by sa dalo kadečo podopĺňať a poupravovať.)

[Martin Sleziak]

6.4 bolo rektorské voľno.

8. prednáška (13.4.):
Von Neumannova konštrukcia ordinálov.
My sme robili iba naivný (neaxiomatický) prístup k ordinálnym číslam. V ZFC by sme mohli použiť von Neumannovu definíciu ordinálnych čísel, pri ktorej platí priamo rovnosť $\alpha=\{\beta\in\mathrm{Ord}; \beta<\alpha\}$; t.j. každý ordinál sa rovná množine ordinálnych čísel od neho menších.
Povedal som niektoré veci súvisiace s takýmto prístupom - viacero súvisiacich vecí je napísaných tu: viewtopic.php?t=1175
Stručne som povedal aj niečo o tom, že konečné ordinály by nám dali definíciu prirodzených čísel v ZFC. Z $\mathbb N$ vieme potom dosť jednoducho dostať $\mathbb Q$. Z racionálnych čísel vieme dostať reálne čísla napríklad pomocou Dedekinových rezov alebo ako zúplnenie metrického priestoru $(\mathbb Q,d)$ (pomocou cauchyovských postupností).
Wikipédia: Construction of the real numbers

Transfinitná indukcia. Veta o transfinitnej indukcii. Veta o transfinitnej rekurzii. (Nehovoril som o verzii tejto vety pre vlastné triedy - vrátim sa k nej nabudúce.)

Silno darbouxovské funkcie.
Ukázali sme existenciu podmnožiny v $\mathbb R\times\mathbb R$, kde zvislé rezy sú jednoprvkové a vodorovné rezy sú husté.
Nabudúce ešte stručne poviem niečo o darbouxovských a silno darbouxovských funkciách: viewtopic.php?t=1678
Podmnožina $\mathbb R^2$, ktorej existenciu sme minule ukázali, nám dáva graf silno darbouxovskej funkcie.)

[Martin Sleziak]

9. prednáška (20.4.):
Silno darbouxovské funkcie.
Povedali sme si niečo o darbouxovských a silno darbouxovských funkciách: viewtopic.php?t=1678
Podmnožina $\mathbb R^2$, ktorej existenciu sme minule ukázali, nám dáva graf silno darbouxovskej funkcie.

Kardinálna aritmetika. Ukázali sme, že pre nekonečné kardinály platí $\kappa\cdot\kappa=\kappa$. (T.j. pre každú nekonečnú množinu platí $|A\times A|=|A|$.)
Ako dôsledok dostávame, že pre kardinály $a,b\ge\aleph_0$ platí $a+b=ab=\max\{a,b\}.$
Tiež sme spomenuli, že výsledok o $|A\times A|=|A|$ je v ZF ekvivalentný s AC. Wikipédia: Tarski's theorem about choice.
Pritom sme spomenuli, že existuje viacero spôsobov, ako sa dá definovať nekonečná množina, pričom v ZF nie sú nutne ekvivalentné. Wikipédia: Dedekind-infinite set a Finite set § Set-theoretic definitions of finiteness

Kardinály ako iniciálne ordinály
Kardinálne čísla môžeme definovať ako iniciálne ordinály. (T.j. najmenší ordinál s danou kardinalitou. Inak povedané, sú to ordinálne typy takých DUM, kde pre počiatočné úseky neexistuje bijekcia s celou množinou.)
Wikipédia: Von Neumann cardinal assignment.