Apliktm - prednášky LS 2024/25

[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=1934
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 (27.2.):
Na úvod som spomenul nejaké veci k literatúre (keďže som na to zabudol minule): viewtopic.php?t=1935
Ekvivalenty axiómy výberu. Prešli sme 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. V texte je spomenutých ešte pár ďalších.)
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 a Zornova lema a princíp maximality.
Ukázali sme, že z WO vyplýva AC. (To bol vcelku ľahký dôkaz.)
Tiež 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 (6.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.)
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.)
Spomeniem tu aj text P. Zlatoš: O dobrom usporiadaní a axióme výberu (ktorý ste možno videli na inom predmete) - kde je tiež definovaná lexikografická suma.
Spomenul som, že du03 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 (13.3.):
Keďže teraz sa pozeráme na príklady vecí, ktoré sa dajú dokázať pomocou Zornovej lemy, pridám tu aj nejaký zoznam pár tvrdení, ktoré sa obvykle dokazujú práve pomocou ZL: viewtopic.php?p=1626
Aplikácie Zornovej lemy
Pomocou ZL sme dokázali Alexandrovu vetu o subbáze. (Pomocou nej sa dá dokázať Tichonovova veta.) Spomenuli sme tento výsledok aj na predmete Všeobecná topológia, tam sme ho ale iba vyslovili bez dôkazu.
(Som si vedomý toho, že pre ľudí bez predchádzajúcich znalostí funkcionálnej analýzy či všeobecnej topológie je asi nejasné prečo by mali byť takéto výsledky aj na niečo užitočné. To isté platí ajj o Hahn-Banachovej vete, ktorú dokážeme nabudúce. Súčasne som sa však snažil povedať ich tak, aby boli jasné pojmy, ktoré tu používame. Dali by sa vybrať aj aplikácie, ktoré sú jednoduchšie - ale keďže máte nejaké veci pomocou Zornovej lemy odovzdať aj vy, radšej veci s minimom prerekvizít nechávam medzi týmito úlohami.)
Spojitosť a sekvenciálna spojitosť
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.
Pridám k tomu aj túto linku: viewtopic.php?t=1656

[Martin Sleziak]

5. prednáška (20.3.):
Aplikácie Zornovej lemy
Dokázali sme Hahn-Banachovu vetu. (Úmyselne som použil formuláciu s konvexnou funkciou - takže sa táto veta dá povedať bez priveľa prerekvizít. Stačí poznať pojmy vektorový priestor, lineárna funkcia, konvexná funkcia. Vo funkcionálnej analýze sa asi častejšie stretnete s formuláciou pomocou polonormy alebo pomocou sublineárnej funkcie.)

K dôkazu existencie nemerateľnej množiny (Vitaliho konštrukcia) sa vrátim neskôr - keďže teraz viacero štvrtkov odpadne, chcem sa venovať hlavne dobre usporiadaným množinám a dostať sa k transfinitnej indukcii.

Dobre usporiadané množiny
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.

Vyslovili sme základnú vetu 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.) Dôkaz bude až nabudúce - ten sme už nestihli.

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

[Martin Sleziak]

6. prednáška (27.3.):
Dobre usporiadané množiny

Dokázali sme základnú vetu 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. (Tým sme dokončili č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.)

Ukázali sme, že brať ľubovoľné podmnožiny (nie iba počiatočné úseky) dáva to isté: 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$. (Ale aj tak sú v tomto kontexte z istého pohľadu počiatočné úseky prirodzenejšie. Je však užitočné, že vieme, že tieto dve podmienky sú ekvivalentné)

Ordinálne čísla:
Ordinálne čísla sa dajú definovať aj axiomaticky, najčastejšie sa používa von Neumannova konštrukcia. My použijeme "naivný" prístup - definujeme ich ako ordinálne typy dobre usporidaných množiín.
K veciam z tejto časti je toho pomerne málo v texte s poznámkami k prednáške - ale snáď sa to aspoň trochu dá sledovať na základe slajdov: 52ordnaiv.pdf.

Povedali sme si, ako pre ordinály definujeme $\alpha=\beta$ a $\alpha\le\beta$. (Zodpovedá to izomorfizmu dobre usporiadaných množín resp. tomu, že $(A,\le)$ je izomorfná s počiatočným úsekom $(B,\le)$.)

Na konci sme si ešte ukázali izomorfizmus medzi dobre usporiadanou množinou $(A,\le)$ a $(\{A_a; a\in A\}, \subseteq)$. (Nabudúce sa k tomu vrátim
a poviem, ako to súvisí s reprezentáciou čiastočne usporiadaných množín.)

Zadefinovali sme $\sum\limits_{i\in I} (A_i,\le_i)$ pre dobre usporiadané množiny $(I,\le)$ a $(A_i,\le_i)$ (lexikografická suma).
Pomocou nej sme 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.

Na konci sme si ešte ukázali izomorfizmus medzi dobre usporiadanou množinou $(A,\le)$ a $(\{A_a; a\in A\}, \subseteq)$. (Nabudúce sa k tomu vrátim a poviem, ako to súvisí s reprezentáciou čiastočne usporiadaných množín.)

[Martin Sleziak]

7. prednáška (3.4.):

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.

Každý ordinál má nasledovníka.

Pripomenuli sme vetu o tom, že systém dobre usporiadaných množín vieme vložiť do jednej d.u.m. ako podmnožiny resp. počiatočné úseky.
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 je izomorfná s podmnožinou nejakej dobre usporiadanej množiny.
* Každá množina ordinálov má suprémum.
* Každá množina ordinálov je dobre usporiadaná.
* Pre každý ordinál platí $\alpha=\operatorname{ot}(\{\beta\in\mathrm{On}; \beta<\alpha\})$.
* 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$.

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úť.)

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.

Aj dnes platí to, že to čo sme preberali nie je spísané v poznámkach, ktoré sú na stránke. (Ale máte na webe 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ť.)