Axióma výberu, transfinitná indukcia

[Martin Sleziak]

Niektorí z vás ste vyjadrili záujem o veci týkajúce sa axiómy výberu a transfinitnej indukcie, ktoré už nestihnem odprednášať. Ponúkol som, že by som o tom mohol spraviť pár prednášok počas skúškového. Tu by som napísal, čo by o tom mohol povedať. (A čo z nejakých aplikácií by mohlo byť zaujímavé pre študentov učiteľstva resp. pre študentov z filozofickej fakulty.) Podľa toho sa azda bude dať lepšie rozhodnúť, či sa na nejaké takéto veci budete chcieť pozrieť. Ak bude jasné, kto má záujem, tak by sme sa pokúsili dohodnúť na termíne.

V podstate sa dá povedať, že by som išiel z časti podľa poznámok na stránke (mám tam aj nejaké slajdy k veciam, z ktorých som v minulosti aspoň niektoré stihol). Ale v súvislosti s transfinitnou indukciou sa možno budem držať skôr tohoto textu. Mám na stránke ešte nejaké poznámky k Zornovej leme, tam sú však skôr dokázané nejaké veci, ktoré si vyžadujú vedieť pomerne veľa z matiky.

Čo by som chcel spraviť:

• Ako prípravu možno ešte zopakovať veci o dobre usporiadaných množinách, ktoré sme už mali.
• Ukázať tri ekvivalentné formulácie axiómy výberu (AC, WO - princíp dobrého usporiadania, ZL - Zornovu lemu). A aspoň sčasti (tie veci, kde dôkaz je ľahký) ukázať aj, že sú naozaj ekvivalentné.
• Ukázať nejaké aplikácie axiómy výberu.
• Povedať niečo o ordinálnych číslach a transfinitnej indukcii.
• Ukázať nejaké konkrétne aplikácie transfinitnej indukcie.

Aplikácie axiómy výberu, z ktorých niektoré by sme si mohli ukázať:

• Hamelova báza a Cauchyho funkcionálna rovnica. (Toto by mohla byť zaujímavá téma pre študentov učiteľstva, keďže funkcionálne rovnice sú typicky téma, ktorá sa vyskytuje na olympiádach. Táto téma si vyžaduje vedieť nejaké veci z lineárnej algeby.)
• Existencia nemerateľnej množiny.
• Ekvivalencia rôznych definícií spojitosti s tým, že by sme zdôraznili, kde sa tam využíva AC. (Toto by opäť bolo asi zaujímavé skôr pre študentov učiteľstva, ktorí to preberali na analýze.)
• Niečo o čiastočne usporiadaných množinách (existencia linearizácie, alebo existencia maximálneho antireťazca. (Tieto veci sú vhodná ukážka použitia Zornovej lemy - netreba tam žiadne prerekvizity, stačí vedieť niečo o čiastočných usporiadaniach.)
• Existencia voľných ultrafiltrov. (S nimi ste sa asi dosť často stretli na predmete teória množín a matematická logika - preto by toto mohlo byť zaujímavé pre filozofov.)

Aplikácie transfinitnej indukcie:

• Dôkaz, že pre nekonečné kardinály platí $a^2=a$.
• Existencia nejakých patologických podmožín roviny. Napr. silno Darbouxovská funkcia - tvrdenie 7.6.5 v poznámkach. Alebo existencia Mazurkiewiczovej množiny - množiny v rovine, ktorá pretína každú priamku práve v dvoch bodoch.)
• Dôkaz AC $\Rightarrow$ ZL.

[Martin Sleziak]

A azda som ešte mohol napísať, že v podstate podobné veci sa budú preberať na predmete Aplikácie teórie množín, ktorý beží v letnom semestri. Ide však o predmet určený pre študentov matematiky (odporúčaný pre magisterské štúdium), čiže väčšinou tam ako aplikácie budeme ukazovať nejaké veci z pokročilejšej matematiky. Čiže tam bude dosť veľa vecí, ktoré sa bez základov z matematiky budú dať ťažko sledovať. (Prinajlepšom by to človek, ktorý nemá potrebné základy z matematiky, mohol robiť tak, že niektoré časti by si tam len odsedel a sledoval by len niektoré časti, kde by sa vysvetľovali základy, ekvivalencia rôznych foriem axiómy výberu, ako funguje transfinitná indukcia alebo aj zopár aplikácií, kde sú potrebné iba minimálne prerekvizity.)

[Martin Sleziak]

Zatiaľ je ako návrh termínu, že by to mohlo bývať utorky večer. (Napríklad cca 17.00.)
Prvý utorok cez skúškové je štátny sviatok, takže ak sa dohodneme na utorkoch, tak by sme asi začali od druhého týždňa. (Alebo prvý týždeň by to bolo iný deň.)

[Martin Sleziak]

Zatiaľ je ako návrh termínu, že by to mohlo bývať utorky večer. (Napríklad cca 17.00.)
Prvý utorok cez skúškové je štátny sviatok, takže ak sa dohodneme na utorkoch, tak by sme asi začali od druhého týždňa. (Alebo prvý týždeň by to bolo iný deň.)

Ešte sme sa nedohodli na miestnosti.
Ak bude táto miestnosť voľná, tak budeme v M-126.
Ak by nebola, tak skúsime nájsť nejaké akvárium. (O tomto čase by nemal byť problém nájsť voľnú miestnosť.)
V prípade, že by sme namiesto M-126 museli ísť niekde inde, u mňa na dverách by som nechal odkaz kde sme.

[Martin Sleziak]

Dnes som stihol sformulovať Zornovu lemu a ukázať nejaké jej aplikácie.

Konkrétne sme dokázali tieto veci:

Antireťazce

Každá čiastočne usporiadaná množina obsahuje maximálny antireťazec. Spomeniem, že toto tvrdenie sa niekedy volá Kurepov princíp a je ekvivalentné s axiómou výberu. (Dôkaz tejto ekvivalencie je napríklad v H. Herrlich: Axiom of Choice, Theorem 2.4 s.11; DOI: 10.1007/11601562. My sme sa však venovali iba tomu, ako sa toto tvrdenie dá dokázať pomocou Zornovej lemy.)

Potom sme ešte ukázali aj to, že každá nekonečná čiastočne usporiadaná množina obsahuje nekonečný reťazec alebo nekonečný antireťazec. Dôkaz tohoto druhého tvrdenia (azda o čosi zrozumiteľnejšie zapísaný, než som ho hovoril ja) sa dá nájsť v P. Komjáth, V. Totik: Problems and Theorems in Classical Set Theory, s. 274

Porovnateľnosť
Dokazoval som, že ľubovoľné dve kardinálne čísla sú porovnateľné. Dôkaz by mal byť spísaný tu: http://msleziak.com/vyuka/2014/temno/temno20150113.pdf (časť 6.2.4).

Rozklad $\mathbb R^+$
Ako príklad tvrdenia, ktoré pôsobí trochu kontraintuitívne, sme dokázali, že $\mathbb R^+$ sa dá rozložiť na dve disjunktné množiny, ktoré sú uzavreté na sčitovanie. Ja som dôkaz robil spôsobom, ako je uvedený v P. Komjáth, V. Totik: Problems and Theorems in Classical Set Theory, s. 310. Veľmi podobný dôkaz sa dá nájsť aj tu: http://math.stackexchange.com/questions/244456/ (resp. na tej stránke nájdete aj ďalšie linky na dôkazy toho istého tvrdenia).

Kedy sa hodí ZL
Trochu som sa snažil hovoriť aj o tom, ako sa dá zbadať, že pre daný problém môže byť vhodným prostriedkom na dôkaz Zornova lema. (A trúfol by som si povedať, že v podobných situáciách sa často dá použiť aj transfinitná indukcia.)
Viac sa dá o tom pozrieť v How to use Zorn's lemma na blogu Tima Gowersa a na Tricki.

********************

Plán nabudúce:

Mali by sme pokračovať o týždeň v rovnakom čase a na rovnakom mieste.

Niečo by som chcel povedať o niektorých ekvivalentoch axiómy výberu. (Aspoň niektoré implikácie, ktoré sú ľahké alebo na ktoré už máme pripravený aparát aj dokázať.) Chcel by som ukázať existenciu nemerateľnej množiny a aspoň bez dôkazu spomenúť, čo hovorí Banach-Tarskiho paradox.
Potom (to možno už nebude nabudúce) by som sa rád dostal k dobre usporiadaným množinám a transfinitnej indukcii.

[Martin Sleziak]

Chcem dať dopredu vedieť, že 3.2. budem mať iné povinnosti, takže vtedy prednáška (stretnutie, seminár - neviem ako to mám nazvať) nebude.
(Dúfam, že to nezabudnem pripomenúť aj dnes večer.)

[Martin Sleziak]

Veci, ktoré sme stihli dnes sa dajú nájsť v tomto texte: http://msleziak.com/vyuka/2014/temno/temno20150113.pdf (Samozrejme aj na mnohých iných miestach.)

* Ukázali sme si, že z axiómy výberu vyplýva existencia nemerateľnej množiny (Tvrdenie 6.2.19). V súvislosti s tým sme spomenuli aj Banach-Tarskiho paradox.
* Preformulovali sme axiómu výberu pomocou selektora (výberovej funkcie). (Tvrdenie 6.1.2.)
* Spomenuli sme, že s axiómov výberu sú ekvivalentné (v ZF) aj Zornova lema (ZL) a princíp dobrého usporiadania (WO).
* Naznačili sme dôkaz ZL $\Rightarrow$ AC
* Povedali sme si definíciu dobre usporiadanej množiny a tiež to, prečo platí WO $\Rightarrow$ AC.
* Ukázali sme si vetu o indukcii na dobre usporiadaných množinách. (Veta 3.4.3.)

Plán čo ďalej: Chceli by sme si povedať viac o dobre usporiadaných množinách (nejaké príklady, nejaké ich vlastnosti), ordinálnych číslach a dostať sa k transfinitnej indukcii.

Niečo o tom je v texte, na ktorý som dal linku vyššie. Ja sa budem však asi držať skôr toho, čo je spísané tu: http://thales.doa.fmph.uniba.sk/sleziak ... nsfind.pdf

[Martin Sleziak]

Dobre usporiadané množiny: Prešli sme nejaké základné vlastnosti dobre usporiadaných množín. Konkrétne:

• Ak $f\colon A \to A$ je monotónne injektívne, tak $f(a)\le a$ pre všetky $a\in A$.
• V dobre usporiadanej množine existuje nasledovník (pre prvok, ktorý nie je najväčší), suprémum (pre množinu, ktorá je ohraničená).
• Každý prvok dobre usporiadanej množiny je buď najmenší, alebo nasledovník nejakého prvku alebo suprémum množiny prvkov od neho menších.

Tento výsledok o monotónnych injektívnych zobrazeniach sme ukázali dvoma spôsobmi, jeden z nich bola indukcia na dobre usporiadaných množinách. (To je vlastne zatiaľ jediná vec, ktorú sme dokázali indukciou.)

Ordinálne čísla: Ordinálne čísla ako typy dobre usporiadaných množín. (T.j. nerobím s axiomatickou definíciou ordinálnych čísel, iba s naivnou.) Zatiaľ sme si iba povedali, ako je definovaná nerovnosť medzi ordinálnymi číslami a že takto definovaná nerovnosť je nám vlastne dáva lineárne usporiadanie. (Tu sme dôkazy nerobili, aj keď som aspoň trochu naznačil, ako sa tieto veci dajú dokázať.)

Nabudúce: Budúci utorok nemôžeme, teda by sme sa najbližšie stretli 10. februára. Najprv budem potrebovať ešte niečo povedať o ordináloch a sformulovať transfinitnú indukciu už pomocou ordinálov. Hlavne by som sa chcel ale dostať k tomu, že ukážem aj nejaké aplikácie transfinitnej indukcie. Konkrétne by som chcel ukázať, že z axiómy výberu vyplýva Zornova lema a tiež to, že $|A\times A|=|A|$ pre ľubovoľnú množinu. Ak by zvýšil čas, tak by sme mohli ešte ukázať nejaké zaujímavé podmnožiny $\mathbb R^2$; konkrétne napríklad množinu $\mathbb R^2$ pretínajúcu každú priamku v dvoch bodoch - Mazurkiewiczova množina; alebo tiež reálnu funkciu, ktorá na každom intervale nadobúda všetky reálne hodnoty. (Taká funkcia sa dá zostrojiť aj rôznymi inými spôsobmi, nielen pomocou transfinitnej indukcie. Rôzne dôkazy existencie takejto funkcie môžete nájsť napríklad tu, tu alebo tu. )

[Martin Sleziak]

Začali sme s tým, že sme si povedali (bez dôkazu) viaceré vlastnosti ordinálov ktoré potrebujeme (alebo sa nám aspoň hodia na to, aby nám niekedy zjednodušili život.)

• Pre každý ordinál existuje nasledovník $\alpha+1$.
• Každá množina ordinálov má suprémum.
• Každá množina ordinálov je dobre usporiadaná.
• Pre každý ordinál nastane niektorá z možností: $\alpha=0$, $\alpha=\beta+1$, t.j. je to nasledovník nejakého ordinálu; $\alpha=\sup\{\beta\in\mathrm{On}; \beta<\alpha\}$
• Ordinál $\alpha$ je presne ordinálny typ dobre usporiadanej množiny $\{\beta\in\mathrm{On}; \beta<\alpha\}$.

Potom sme sa už dostali k transfinitnej indukcii a najmä ku konštrukcii transfinitnou indukciou.

Ukázali sme existenciu funkcie, ktorá na každom intervale nadobúda všetky reálne hodnoty. (Taká funkcia sa dá zostrojiť aj rôznymi inými spôsobmi, nielen pomocou transfinitnej indukcie. Rôzne dôkazy existencie takejto funkcie môžete nájsť napríklad tu, tu alebo tu.)
Mala to byť do istej miery ukážka dôkazu, kde vlastne vieme, aké podmienky chceme splniť a postupne konštruujeme nejaký objekt tak, aby tieto podmienky splnil. Niečo o dôkazoch takéhoto typu sa dá nájsť aj na tomto blogu.

Potom sme ešte ukázali, že z Axiómy výberu vyplýva Zornova lema.

Už som nestihol dokázať rovnosť $|A\times A|=|A|$ pre nekonečné množiny. Takisto som nestihol porozprávať niečo viac o ordináloch (a ich konštrukcii v ZFC). Do značnej miery som sa držal tohoto textu: http://thales.doa.fmph.uniba.sk/sleziak ... nsfind.pdf

Dnes padla otázka, či sa dá nejako ukázať aj implikácia (WO) $\Rightarrow$ (ZL). (Ostatné implikácie sme buď dokazovali, alebo aspoň stručne spomenuli, ako sa dá dôkaz urobiť.)
Takýto dôkaz sa dá nájsť napríklad v Komjáth-Totik: Problems and Theorems in Classical Set Theory, Problem 14.1 (zadanie je na s.65 a riešenie na s.309.