msleziak.com

Našlo sa zopár ľudí, čo mali záujem o niečo takéto, tak skúsim túto informáciu rozšíriť aj medzi ďalších potenciálnych záujemcov.
Skúsil by som porozprávať niečo o Zornovej leme a prípadne tiež o ordináloch a transfinitnej indukcii.
Dohodli sme sa na termíne v piatok o 9.50. (Pravdepodobne v akváriu M-II alebo v seminárke M-126. Ak by niekto s tým termínom chcel ešte hýbať, tak sa skúsime v rámci možnosti dohodnúť - ale pre tých, s ktorými som zatiaľ hovoril, vyzeral piatok asi najlepšie. Takéto veci sa už budú asi ľahšie riešiť keď sa naozaj stretneme priamo s tými, čo tam plánujú chodiť.)

V podstate by to znamenalo povedať si o oboch veciach čo to vlastne je a ukázať si zopár aplikácií. Oboje (ZL aj transfinitná indukcia) sú vcelku užitočné dôkazové techniky, ktoré sa v matematike často využívajú. (Prinajmenšom s Zornovou lemou sa takmer určite na matfyze párkrát stretnete.) Na čo všetko sa dajú použiť sa dá pozrieť napríklad tu viewtopic.php?t=25 alebo v tomto texte.

Nebol by to oficiálny predmet - čiže za to nie sú kredity. Ale na druhej strane, keď to bude bežať len takto neoficiálne, má to aj nejaké výhody. Ak to pomôže rozhodovaniu či áno alebo nie, tak časť 1.2 v texte k predmetu Aplikácie teórie množín sa podobá na to, čo by som chcel hovoriť ako úvod. (Dá sa možno z toho získať nejaká hrubá predstava o čom to chce byť.)

Prekryv s inými predmetmi
Keďže padla aj otázka, či tu vlastne nebudem hovoriť veci ktoré sa aj tak dozviete inde, tak skúsim napísať nejaký stručný komentár aj k tomu. S Zornovou lemou sa na matfyze určite párkrát stretnete. (Ale skôr tak jednorázovo -že na niektorých predmetoch sa za celý semester vyskytne jeden či dva výsledky, kde treba použiť Zornovu lemu; a potom už tam o nej nebudete počuť.) Možno máte o čosi menšiu šancu sa stretnúť s transfinitnou indukciou.

Keď sa pozrieme na predmety, čo majú v názve teóriu množín, tak prof. Zlatoš učí predmet Teória množín a matematická logika 1 a 2. Nie je toho až tak veľa, v čo by ste počuli tu aj tam. (Možno ak si zapíšete TMML po tomto, tak tam budete mať miernu výhodu, že ste už narazili na niektoré veci, čo sa tam používajú. Zhruba rovnako by to asi bolo v obrátenom poradí.)

Na to, čo tu chcem robiť, by sa dalo asi pozerať ako na light verziu predmetu Aplikácie teórie množín (alebo aspoň jeho prvej časti). Tento predmet je zaradený na magisterskom štúdiu, čiže keď sa naň niekto prihlási, tak môžem počítať s tým, že ovláda veci z bakalárskeho štúdia. Toto sa teda bude odlišovať tak, že budeme vyberať také príklady použitia Zornovej lemy a transfinitnej indukcie, kde vám stačí to, čo viete v druhom ročníku, alebo sa chýbajúce veci dajú nie moc ťažko doplniť. (Ak by niekto chodil sem a potom si na magisterskom zapísal tento predmet Aplikácie teórie množín, tak už nejako individuálnou dohodou skúsime vyriešiť to, aby ste nemuseli znovu počúvať veci, ktoré ste už raz počuli.)

Azda to už definitívne zostane v M-126 v piatky 9.50.

Sem budem občas písať, o čom sme hovorili - hlavne kvôli tomu, že ak budem mať nejaké súvisiace linky tak ich sem môžem ľahko pridať.

Dnes som sa snažil aspoň trochu na príklade ukázať, ako vlastne môže vyzerať použitie Zornovej lemy a transfinitnej indukcie. Ako príklad som použil Cauchyho funkcionálnu rovnicu. Vlastne som o tom povedal najprv taký neformálny pokec. A potom som ešte napísal, čo vlastne hovorí Zornova lema a ako by sme existenciu netriviálnych riešení ukázali pomocou nej. (Stále som tam preskočil nejaké detaily, ale toto sa už mohli blížiť poriadnemu dôkazu. Keď si ukážeme nejaké veci o Hamelovej báze, tak to celé budeme vedieť zdôvodniť jednoduchšie.) Vlastne okrem toho poriadneho dôkazu sú tieto úvodné veci aj napísané časti 1.2.2 a 1.2.3 v týchto poznámkach. (Keďže dnes bol vlastne len taký úvod, kde som chcel aspoň nejako zhruba ukázať čo vlastne ZL je, veci čo budú nabudúce sa dajú bez problémov sledovať aj ak ste dnes neboli.)

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. Ešte sme si ukázali pár príkladov dobre usporiadaných množín.
Axióma výberu, ZF a ZFC. Aspoň nejako stručne som povedal čosi o axiómach. Hlavný zámer bol nejako vás presvedčiť o tom, že je nejaký rozdiel medzi dôkazmi bez použitia AC a dôkazmi s jej použitím. A tiež že vedieť o nejakom výsledku, že sa nedá dokázať v ZF (t.j. bez axiómy výberu) nám dáva o tomto výsledku aspoň trochu zaujímavú informáciu.
Ekvivalenty axiómy výberu. Prešli viacero podmienok, o ktorých je jednoduché ukázať, že sú ekvivalentné s axiómou výberu. (Konkrétne existenciu selektora.)
Okrem toho pokecu o ZF a ZFC sa veci, ktoré boli dnes dajú nájsť v apliktm.pdf v častiach 4.1 a na začiatku 4.2. (S tým rozdielom, že pri veciach o dobre usporiadaných množinách som iba nakreslil nejaké obrázky, v tom texte je spravený aj formálny dôkaz vecí o lexikografickom súčine.)

Ekvivalenty axiómy výberu. Dnes som začal s tým, že v ZF sú ekvivlentné: Axióma výberu (AC), Princíp dobrého usporiadania (WO) a Zornova lema (ZL). Postupne aj dokážeme jednotlivé implikácie. (Teraz sme si ukázali WO $\Rightarrow$ AC, ktorá je ľahká. Implikácie ZL $\Rightarrow$ AC aj ZL $\Rightarrow$ WO si ukážeme ako príklady použitia Zornovej lemy. Zostáva ešte implikácia AC $\Rightarrow$ ZL - tú dokážeme až keď budeme mať k dispozícii transfinitnú indukciu.)

Aplikácie Zornovej lemy. Ako prvé dve aplikácie sme si ukázali ZL $\Rightarrow$ AC a porovnateľnosť kardinálov. (T.j. pre ľubovoľné dve množiny $A$, $B$ existuje injekcia $A\to B$ alebo injekcia $B\to A$.) Trochu som pri tom hovoril aj o tom, že ak vlastne použijeme neprázdnosť nejakej množiny na to, že vieme o existencii objektu s nejakou vlastnosťou, tak sme iba použili pravidlá logiky o narábaní s kvantifikátormi a netreba axiómu výberu. Toto bude možno jasnejšie keď sa neskôr bude učiť o nejakom formálnom systéme kde budete pracovať s predikátovou logikou - často sa používa napríklad Hilbertov systém. Pridám linku aj na konkrétne pravidlo, ktoré sa týka toho o čom sme hovorili: existential instantiation. Situácia by bola úplne iná, keby sme niečo podobné chceli robiť pre nekonečne veľa množín, nie iba pre jednu - vtedy naozaj používame AC.

Tieto dva príklady použitia sú podobné v tom, že sme robili s nejakou množinou funkcií a usporiadanie bolo také, že $f\le g$ ak $g$ rozširuje $f$. (T.j. vlastne inklúzia, ak zobrazenia chápeme ako množiny usporiadaných dvojíc.) Ako som spomenul, použitie Zornovej lemy často vyzerá podobne. Iný dôležitý príklad tvrdenia, ktorá sa dá ukázať tak že z Zornovej lemy ukážeme existenciu vhodného zobrazenia takýmto spôsobom je Hahn-Banachova veta.
Ešte si chceme ukázať nejaké príklady, kde nepracujeme s funkciami a usporiadanie je inklúzia - zatiaľ som začal s jedným, ale nestihol som ho dokončiť.

Ultrafiltre. Zadefinoval som pojem filtra, ultrafiltra a centrovaného systému. Začal som s dôkazom, že každý centrovaný systém je obsiahnutý v nejakom ultrafiltri (ultrafilter lemma). Nestihol som ho dokončiť - zatiaľ som ukázal, že Zornova lema zaručí existenciu maximálneho centrovaného systému. (Zostáva ukázať, že to je ultrafilter, K tejto téme chcem vrátiť nabudúce - dokončiť dôkaz, povedať ešte inú ekvivalentnú definíciu ultrafiltra a ako príklad použitia ultrafiltrov ukázať niečo o limite postupnosti pozdĺž ultrafiltra. S ultrafiltrami sa stretnete na viacerých predmetoch - jednak na Všeobecnej topológii a veľa s nimi budete robiť aj na predmete Teória množín a matematická logika, kde sa veľmi často vyskytne ultrasúčin a ultramocnina.

Ultrafiltre a F-limity. Dnes sme väčšinu času strávili s ultrafiltrami a F-limitami. Zopakoval som definície pojmov, ktoré používame a dokončil dôkaz z minula, že každý centrovaný systém je obsiahnutý v nejakom ultrafiltri.
Zadefinoval som F-limitu a ukázal niektoré vlastnosti. Dôležitý je hlavne výsledok, že ak máme ultrafilter, tak F-limita existuje pre každú ohraničenú postupnosť. (Dá sa to zovšeobecniť na kompaktné topologické priestory.) Ukázali sme, že F-limita dá rozšírenie obvyklej limity, ktoré má rozumné vlastnosti. Už som len stručne spomenul, že iné rozšírenie limity s peknými vlastnosťami je Banachova limita. Jej existencia sa tiež dá ukázať pomocou ultrafiltrov. Veci, ktoré som hovoril dnes sa dajú nájsť v apliktm.pdf v časti 6.3 Ultrafiltre.

Ďalšie aplikácie Zornovej lemy.
Určite ešte chcem ukázať implikáciu ZL$\Rightarrow$WO; pretože rôzne ekvivalentné formy AC sú jedna z vecí, ktoré nás zaujímajú. (A navyše aspoň raz chcem použiť Zornovu lemu v prípade, kde použité čiastočné usporiadanie nie je priamo inklúziu.
Ďalšie aplikácia Zornovej lemy, na ktorú určite stačia vedomosti čo máte teraz, je existencia Hamelovej bázy. (T.j. báza existuje v ľubovoľnom vektorovom priestore, nie iba v konečnorozmerných.) Veci o bázach sú tiež zhrnuté v apliktm.pdf ako Problém 4.3.1. Aj ak nebudem robiť dôkaz, o tomto by som aspoň niekedy stručne spomenul základné veci.

Dobré usporiadanie. Ukázali sme pomocou Zornovej lemy, že na každej množine existuje dobré usporiadanie (Well-ordering theorem). Vlastne to bol prvý prípad, kde sme použili Zornovu lemu a čiastočné usporiadanie použité v dôkaze (=čiastočné usporiadanie na množine na ktorú sme ZL aplikovali) nebola priamo inklúzia.

Hamelova báza. Povedali sme si, že v každom vektorovom priestore existuje báza. (Dokonca pre každú lineárne nezávislú množinu existuje báza, ktorá ju obsahuje.) Bez dôkazu sme spomenuli, že aj tu platia niektoré fakty, ktoré sme sa naučili v prvom ročníku pre konečnorozmerné vektorové priestory:

• Ak predpíšeme hodnoty v bázových vektoroch, je tým jednoznačne určené lineárne zobrazenie.
• Ľubovoľné dve bázy toho istého priestoru majú rovnakú kardinalitu. (Teda sa dá zmysluplne hovoriť o dimenzii.)

Tiež sme si spomenuli, ako sa báza $\mathbb R$ ako vektorového priestoru nad $\mathbb Q$ použiť na zdôvodnenie existencie nespojitých riešení Cauchyho funkcionálnej rovnice.
Ak by sa niekto chcel pozrieť detailnejšie na veci okolo bázy, tak sú zhrnuté v Probléme 4.3.1 v apliktm.pdf.

Spomenul som niečo také, že sa nedá veľmi očakávať mať Hamelovu bázu popísanú úplne explicitne. (Určite nie pre každý vektorový priestor. Alebo napríklad ani bázu $\mathbb R$ nad $\mathbb Q$.) Viac sa dá prečítať tu: viewtopic.php?t=1165

Ešte napíšem niečo ak k iným veciam, čo sa dajú dokazovať pomocou ZL - ak by si niekto chcel vyskúšať nejaké dôkazy aj sám:

Na začiatku sme hovorili o niektorých dobre usporiadaných podmnožinách $(\mathbb R,\le)$. (V súvislosti s tým, akú máme predstavu o dobre usporiadaných množinách. Spomenul som, že takto sa dajú reprezentovať spočítateľné dobre usporiadané množiny - toto je presne úloha 4.1.7* v apliktm.pdf.)
V súvislosti s tým, o čom sme hovorili, som spomenul dva fakty: Množina je dobre usporiadané p.v.k. nemá nekonečný klesajúci reťazec. Ak sme v dobre usporiadanej množine $(X,\le)$, tak každý prvok je buď nasledovník nejakého prvku alebo platí $a=\sup\{b\in X; b<a\}$. (Tento prípade zahŕňa aj $a=\min X$.)
Potom sme sa vrátili 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 je asi napísaný zbytočne zložito.)
Ešte sme si povedali, že vlastne teraz máme pohľad na ordinály ako ordinálne typy dobre usporiadaných množín a vieme definovať kedy platí $\alpha=\beta$ a $\alpha\ne\beta$, pričom z toho čo už vieme, vidíme že $=$ aj $\le$ sa správa rozumne. (Konkrétne so základnej vety o d.u.m. dostávame, že ľubovoľné dva ordinály sú porovnateľné.)

Dnes sme začali tým, že sme ukázali platnosť rovnosti $|A\times A|=|A|$ pre nekonečné množiny. (Dôkaz využíva AC. Ako dôsledok máme, že pre nekonečné kardinály funguje sčitovanie a násobenie veľmi jednoducho: $a+b=ab=\max\{x,b\}$.)
Ukázali sme si, že každý ordinál $\alpha$ je ordinálny typ množiny $\{\beta\in\mathrm{On}; \beta<\alpha\}$. (Na to sa hodí použiť izomorfizmus medzi dobre usporiadanou $(A,\le)$ a $(\{A_a; a\in A\}, \subseteq)$.)
Sformulovali sme princíp dôkazu transfinitnou indukciou. (A aj dokázali - je to však vlastne priamy dôsledok vety o indukcii na dobre usporiadaných množinách.)
Ako prvý príklad dôkazu transfinitnou indukciou sme si ukázali, že pre $A=\{\beta\in\mathrm{On}; \beta<\alpha\}$ a monotónnu injekciu $f\colon A\to A$ máme $\beta\le f(\beta)$. (Dá sa povedať, že sme vlastne zložitejšie ukázali niečo, čo sme už predtým dokázali iným spôsobom na dva riadky. Ako prvý príklad však možno nevadí jednoduché tvrdenie. A súčasne sme aspoň na jednom jednoduchom príklade videli to, čo sa veľmi často stane v dôkazoch transfinitnou indukciou; zvyčajne treba iný spôsob použiť na dôkaz pre prípad $\beta=0$, pre prípad že $\beta$ je nasledovník a pre prípad, že $\beta$ je limitný ordinál.

Niektoré užitočné vlastnosti ordinálov - z ktorých sme zatiaľ spomenuli iba niektoré - sú zhrnuté tu: viewtopic.php?t=1175

Dnes sme sa najprv trochu rozprávali o tom, že všetky dobre usporiadané množiny sa dajú vnoriť do $\mathbb R$ s obvyklým usporiadaním. (To isté platí aj pre $\mathbb Q$. Navyše sa dá ukázať aj to, že každá dobre usporiadaná podmnožina $\mathbb R$ resp. $\mathbb Q$ je spočítateľná, čiže to môžeme brať ako charakterizáciu.) Dôkaz sa dal urobiť obvyklou indukciou. (Chvíľu sme skúšali aj či sa dá vymyslieť nejaký jednoduchý dôkaz transfinitnou indukciou, ale v to, čo sme zatiaľ stihli spraviť by bolo treba dotiahnuť detaily.)
Triedy. Na začiatku som niečo máličko spomenul o triedach - len preto, že som chcel jednoduchšie (s využitím triedových funkcií) sformulovať princíp transfinitnej rekurzie. Z prvého ročníka viete, že množiny tvoria vlastnú triedu. (Neexistuje množina všetkých množín.) Bez dôkazu sme spomenuli, že to isté platí pre ordinály.
Transfinitná rekurzia. Sformulovali sme, čo znamená transfinitná rekurzia (definícia transfinitnou indukciou) a stručne sme ukázali dôkaz.
Silno darbouxovská funkcia.Ukázali sme, že existuje funkcia $f\colon\mathbb R\to\mathbb R$ taká, že pre každý netriviálny interval platí $f\left[I\right]=\mathbb R$. (Tento dôkaz je v apliktm.pdf ako tvrdenie 5.7.6.)Spomenuli sme aj to, že takéto niečo sa dá brať ako zosilnenie podmienky z definície darbouxovskej funkcie. Spomeniem aj to, že by sa dali nájsť aj explicitné príklady silno darbouxovských funkcií (napr. linky nižšie) - náš dôkaz využíval AC. Každopádne trik urobený v tomto dôkaze - že niečo môžem konštruovať ak mám $\mathfrak c$ bodov z ktorých vyberám a v každom kroku mám menej ako $\mathfrak c$ "zakázaných" bodov - sa dá využiť pri mnohých podobných dôkazoch. Zornova lema.Ukázali sme, ako pomocou axiómy výberu a transfinitnej indukcie môžeme ukázať Zornovu lemu. Tento dôkaz sa dá opäť nájsť v apliktm.pdf. Pridám aj túto linku - sčasti aj preto, že sú tam odkazy na iné dôkazy (nevyužívajúce transfinitnú indukciu): Zorn's Lemma And Axiom of Choice. (V dôkaze sme využili to, že by sme dostali bijekciu medzi ordinálmi, ktoré tvoria vlastnú triedu, a nejakou množinou - čo je spor. Ale aspoň stručne som sa ku koncu snažil vysvetliť, že by sme to nejako vedeli obísť aj bez použitia faktu že ordinály tvoria vlastnú triedu - ktorý sme zatiaľ nedokazovali.)

Nejaké veci, z ktorých niektoré by sa dali robiť nabudúce:

Borelovské funkcie a Bairove triedy. Najmenšiu $\sigma$-algebru obsahujúcu danú množinu sme popísali pomocou transfinitnej indukcie. Zistili sme, že stačí iterovať po ordinál $\omega_1$. Z toho sme vedeli ukázať, že borelovských množín v $\mathbb R^n$ bude iba $\mathfrak c$, teda existujú aj množiny, ktoré nie sú borelovské.
Stručne som povedal niečo o Bairových triedach a tiež povedal to, že pre $\mathbb R^n$ takto dostaneme presne borelovské funkcie. Z dôkazu som len trochu naznačil jednu implikáciu. (Nerobil som to, že borelovské funkcie sú uzavreté na bodové limity. Povedal som, že ľubovoľnú uzavretú množinu viem dostať ako prienik otvorených: $E=\bigcap B(E,1/n)$, kde $B(E,1/n)=\{y\in X; (\exists x\in E)d(x,y)<1/n\}$. A ak som v situácii, že $E\subseteq U$, kde $E$ je uzavretá a $U$ je otvorená, tak mám spojitú funkciu $f(x)=\frac{d(x,U^c)}{d(x,E)+d(x,U^c)}$ takú, že $f[E]=1$, $f[U^c]=0$. S takýmito funkciami by som vedel bodov dokonvergovať k $\chi_E$. Ak by som ešte ukázal, že trieda funkcií s ktorými robím je vektorový priestor, tak potom už nejako viem dostať aj všetky charakteristické funkcie borelovských množín a z nich aj všetky borelovské funkcie - robil by som vždy nejaké lineárne kombinácie a bodové limity.)

Dnes sa viackrát vyskytlo to, že pre ľubovoľnú množinu ordinálov máme suprémum - tak som veľmi stručne naznačil, ako sa to dá urobiť pri naivnej definícii ordinálov.
Tiež sa dnes vyskytol najmenší nespočítateľný ordinál $\omega_1$ (resp. najmenší nespočítateľný kardinál $\aleph_1$): viewtopic.php?t=597