Prednášky LS 2021/22 - teória množín

[Martin Sleziak]

V tomto vlákne budem pravidelne dopĺňať, čo sa stihlo prebrať na jednotlivých prednáškach. (Napríklad to môže byť užitočné pre ľudí, ktorí z nejakého dôvodu nemohli prísť na prednášku - aby si mohli pozrieť, čo si treba doštudovať.)

Ak budete mať otázky k niečomu, čo odznelo na prednáškach, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)

Ak sa chcete pozrieť na to ako to vyzeralo minule:
viewtopic.php?t=1636
viewtopic.php?t=1492 a viewtopic.php?t=1503
viewtopic.php?t=1392
viewtopic.php?t=1203
viewtopic.php?t=1024
(A nájdete tu niečo podobné aj z predošlých rokov - to však bolo ešte podľa predošlej akreditácie, čiže tento predmet vyzeral o dosť inak.)

[Martin Sleziak]

1. týždeň (14.2.)
Na začiatku bol nejaký stručný pokec - nejaký historický úvod a k čomu by to vlastne malo celé smerovať. Stručne sa to dá zhrnúť tak, že sa plánujeme dostať k pojmu kardinalita množiny - t.j. niečo podobné ako počet prvkov množiny, ale zmysluplne to funguje aj pre nekonečné množiny. Ako konkrétny príklad sme si povedali niečo o algebraických číslach. Časom ukážeme, že táto množina je spočítateľná. To znamená, že kardinalita množiny algebraických čísel je menšia ako kardinalita reálnych čísel. A teda existujú aj trancedentné čísla. Tiež sme spomenuli, že $|\mathbb N|<|\mathbb R|$ sa dá ukázať Cantorovou diagonálnou metódou.
Všetky veci, ktoré sme v tomto úvode iba spomenuli alebo naznačili prečo platia budeme na konci semestra schopní dokázať a zdôvodniť.

Potom sme zopakovali, ako vieme overovať tautológie. (Reálne sme si odskúšali $p\land (q\lor r) \Leftrightarrow (p\land q)\lor (p\land r)$ a obmenu implikácie $(p\Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$.)
Zaoberali sme sa trochu výrokmi s kvantifikátormi. (Pozreli sme sa konkrétne na $\neg[(\forall x)P(x)] \Leftrightarrow (\exists x) \neg P(x)$ a tiež na to, či platí $(\exists x)P(x)\land Q(x) \Leftrightarrow (\exists x)P(x) \land (\exists x) Q(x)$ resp. $(\exists x)P(x)\lor Q(x) \Leftrightarrow (\exists x)P(x) \lor (\exists x) Q(x)$.)
Zadefinovali sme rovnosť množín a inklúziu. Ako príklady tvrdení o množinách sme ukázali, že $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$. (Pomocou pravdivostnej tabuľky a aj pomocou Vennových diagramov.) Tiež sme ukázali, že z $A\subseteq B$ a $B\subseteq C$ vyplýva $A\subseteq C$.
Na konci sme sa ešte chceli pozrieť na asociatívnosť pre symetrickú diferenciu $A\triangle(B\triangle C)=(A\triangle B)\triangle C$. Tento príklad sme už nakoniec nespravili (kvôli technickým problémom na mojej strane).

Ak chcete, môžete sa zamyslieť nad tým, ako by vyzerali Vennove diagramy pre viac než 3 množiny: viewtopic.php?t=57
K dôkazu tranzitívnosti inklúzie pridám túto linku: viewtopic.php?t=62 (Ako som upozornil priamo na hodine, v dôkaze ktorý sme robili ešte stále treba niečo dokončiť.)

Prvá hodina bola online, v MS Teams sa dá pozrieť video a je tam aj linka na Whiteboard. (A obsah tabule je vyexportovaný aj ako SVG, PNG, PDF.)
Tu je linka na SharePoint.

[Martin Sleziak]

2. týždeň (21.2.)
Rektorské voľno.

3. týždeň (28.2.)

Zjednotenie a prenik systému množín. Zadefinovali sme zjednotenie a prienik ľubovoľného (neprázdneho) systému množín. Pozreli sme sa na pár príkladov a ako ukážku dôkazu nejakej vlastnosti sme sa pozreli $B\cap (\bigcup\limits_{i\in I} A_i)=\bigcup\limits_{i\in I} (B\cap A_i)$.

Funkcie. Definícia zobrazenia. Pripomenuli sme pojem injekcie, surjekcie, bijekcie. (Tie už poznáte z nižších ročníkov.) Povedali sme si, čo je vzor a obraz zobrazenia a overili sme nejaké rovností, v ktorých vystupujú. Konkrétne sme videli dôkaz, že $f[A\cap B] \subseteq f\left[A\right] \cap f\left[B\right]$ a pre injekcie platí rovnosť. (Ale na príklade sme videli, že vo všeobecnosti rovnosť platiť nemusí.) A tiež sme sa pozreli na dôkaz toho, že $f^{-1}\left[\bigcup\limits_{i\in I}B_i\right]=\bigcup\limits_{i\in I}f^{-1}[B_i]$.

Kvantifikátory. Na konci sme sa pozreli aj na to, že
$$(\forall x\in A)P(x) \overset{\mathrm{def}}\Leftrightarrow (\forall x) (x\in A \Rightarrow P(x));\\ (\exists x\in A)P(x) \overset{\mathrm{def}}\Leftrightarrow (\exists x) (x\in A \land P(x)).$$

[Martin Sleziak]

4. týždeň (7.3.)
Karteziánsky súčin množín. Definícia. Overili sme, že $A\times (B\cap C)=A\times B \cap A\times C$.
Karteziánsky súčin funkcií. Definícia. Súčin injekcií, surjekcií, bijekcií.
Kardinalita. Zadefinovali sme, kedy pre dve množiny platí $|X|=|Y|$ a $|X|\le|Y|$. Povedali sme si základne vlastnosti rovnosti a nerovnosti kardinálnych čísel. Z nich vlastne jediný náročnejší dôkaz bol dôkaz Cantor-Bernsteinovej vety. (V poznámkach nájdete dva dôkazy tejto vety, ktoré sú do istej miery podobné - ja som robil iba jeden z nich.)
Tento dôkaz bol asi najkomplikovanejší z toho, čo sme robili doteraz - ako som spomínal, ukázať nejaký trochu iný dôkaz (a prejsť ho detailnejšie) je jedna z možných tém v tej druhej (nepovinnej) časti semestra: viewtopic.php?t=1266 viewtopic.php?t=1275

Pridám sem aj stručnú rekapituláciu jednotlivých krokov dôkazu:

• Máme injekcie $f\colon X\to Y$ a $g\colon Y\to X$, chceme nejako dostať bijekciu $h\colon X\to Y$.
• Pracujeme so zobrazením $F\colon\mathcal P(X)\to\mathcal P(X)$ definovaným ako $F(A)=X\setminus g[Y\setminus f[A]]$.
• Ukážeme, že $F$ je monotónne, t.j. $A\subseteq B$ $\Rightarrow$ $F(A)\subseteq F(B)$.
• Teraz vezmeme $\mathcal S=\{B\subseteq X; B\subseteq F(B)\}$ a položíme $C=\bigcup\mathcal S$.
• O tejto množine ukážeme, že $F(C)=C$.
• Teraz pomocou množiny $C$ už zostrojíme $h$ tak, že na množine $C$ použijeme zobrazenie $f$ a na množine $X\setminus C$ použijeme (otočené) zobrazenie $g$.

Ešte sme sa pozreli na nejaké úlohy o inklúziách, zjednoteniach a podobne. Konkrétne sme prešli veci, ktoré sa využívali v dôkaz Cantor-Bernsteinovej vety. T.j. videli sme, že:
* Z $A\subseteq B$ vyplýva $f[A]\subseteq f\left[B\right]$.
* $A\subseteq B$ $\Rightarrow$ $C\setminus A \supseteq C\setminus B$.
* Pre každé $A\in\mathcal S$ platí $A\subseteq\bigcup\mathcal S$.
* Ak pre každé $A\in\mathcal S$ platí $A\subseteq D$, tak platí aj $\bigcup \mathcal S \subseteq D$.

Na konci sme sa ešte vrátili na chvíľu aj k dôkazu tranzitívnosti: viewtopic.php?t=62

Pre tých, ktorí dnes nemohli byť na prednáške, napíšem to, že aspoň dôkaz Cantor-Bernsteinovej vety dnes pribudol medzi videami, ktoré máte k dispozícii: viewtopic.php?t=1503

[Martin Sleziak]

5. týždeň (14.3.)
Nervonosť medzi kardinalitami. Ešte sme sa vrátili k nerovnosti kardinálnych čísel a ukázali, že je dobre definovaná (a vysvetlili, čo to vlastne znamená). Zadefinovali sme sčitovanie, násobenie a umocňovanie kardinálov. Zatiaľ sme nedokazovali, že tieto operácie sú dobre definované. (Pre sčitovanie to zostalo ako nepovinná d.ú., ale aspoň sme si vysvetlili, že bez predpokladu o disjunktnosti by to nefungovalo. Pre násobenie a umocňovanie to ukážeme neskôr.)
Spomenuli sme si, že porovnateľnosť kardinálnych čísel (t.j. fakt, že pre ľubovoľné dve množiny platí $|X|\le|Y|$ alebo $|Y|\le|X|$) by sa dal použitím axiómy výberu. My takúto vec nebudeme dokazovať - vyžiadalo by si to ešte veľa vecí, ktoré by sme museli zadefinovať a dokázať.

Kardinálna aritmetika. Ukázali sme, že $|\mathcal P(X)|=2^{|X|}$. Začali sme dokazovať niektoré základné vlastnosti operácií s kardinálnymi číslami. Zatiaľ sme stihli dokázať viaceré vlastnosti sčitovania kardinálov.
Dokázali sme, že platí $\aleph_0+\aleph_0=\aleph_0$.
Ukázali sme, že $\aleph_0+a=\aleph_0$ pre ľubovoľné $a\ge\aleph_0$.
Identita $\aleph_0+\aleph_0=\aleph_0$ a niektoré ďalšie identity týkajúce sa kardinálneho čísla $\aleph_0$ sa dajú porozprávať aj menej formálne pre stredoškolákov - Hilbertov hotel: viewtopic.php?t=467
My sme o tomto kardinálnom čísle stihli ukázať, že $\aleph_0+\aleph_0=\aleph_0$ a $\aleph_0\cdot\aleph_0=\aleph_0$. Dali by sa vymyslieť aj iné možnosti ako nájsť bijekciu medzi $\mathbb N$ a $\mathbb N\times\mathbb N; Wikipédia: Pairing function.

Prázdna množina, kvantifikátory, zobrazenia medzi prázdnymi množinami. Pozreli sme sa na to, že $(\forall x\in\emptyset)P(x)$ je vždy pravda a $(\exists x\in\emptyset)P(x)$ je vždy nepravda, bez ohľadu na výrok $P(x)$. Wikipédia: Vacuous truth.
Čomu sa rovná $0^0$, $a^0$, $0^a$. Niečo k tomu nájdete aj tu: viewtopic.php?t=343

Tu na fóre nájdete niečo o rozdiele kardinálnych čísel - možno toto môže pomôcť vyjasniť čo to znamená, že nejaká operácie nie je dobre definovaná: viewtopic.php?t=1237

Prvá hodina bola online, v MS Teams sa dá pozrieť video a je tam aj linka na Whiteboard. (A obsah tabule je vyexportovaný aj ako SVG, PNG, PDF.)
Tu je linka na SharePoint.

[Martin Sleziak]

6. týždeň (21.3.)
Kardinálna aritmetika. Pripomenuli sme definície sčitovania, násobenia a umocňovania kardinálov.
Vlastnosti násobenia kardinálnych čísel. Pozreli sme sa na niektoré jednoduché vlastnosti, ako $2\cdot a=a+\cdot a$, $a\cdot b=b\cdot a$, $a\cdot(b\cdot c)=(a\cdot b)\cdot c$, $a\cdot(b+c)=a\cdot b+a\cdot c$.
Vlastnosti umocňovania kardinálnych čísel.
Pripomenuli sme, čomu sa rovná $0^0$, $a^0$, $0^a$. Opäť pridám aj túto linku: viewtopic.php?t=343
Pozreli sme sa stručne na $a^2=a\cdot a$.
Ukázali sme, že umocňovanie je dobre definované. Ukázali sme, že $a\le b$ $\Rightarrow$ $a^c\le b^c$, (Dôkaz tejto vlastností sme zatiaľ preskočili: $a^2=a\cdot a$, $a\le b$ $\Rightarrow$ $c^a\le c^b$ (pre $c\ne0$).)
Ukázali sme, že umocňovanie kardinálnych čísel je dobre definované.
Dokázali sme: $(a^b)^c=a^{bc}$. (A trochu sme sa pozreli aj na obrázok, ktorý ilustruje intuíciu za týmto dôkazom.)
Dôkazy týchto dvoch vlastností nebudeme robiť: $a^{b+c}=a^b\cdot a^c$, $(ab)^c=a^c\cdot b^c$. (V prípade záujmu sa dajú pozrieť v poznámkach.)

[Martin Sleziak]

7. týždeň (28.3.)
Dá sa definovať rozdiel kardinálnych čísel? Pozreli sme sa trochu na to, že pokusy nejako rozumne definovať rozdiel kardinálnych čísel narážajú na problémy. Jednak v súvislosti s tým, čo znamená dobre definovaná operácia pre kardinálne čísla - a trochu aj v súvislosti s nejakými chybami, ktoré sa vyskytli v odovzdaných d.ú. Opäť pridám tú istú linku: viewtopic.php?t=1237
Kardinálna aritmetika - horný odhad pre mocninu. Ukázali sme (dokonca dvoma spôsobmi), že pre kardinálne čísla platí $a\le2^a$ a $a^b\le 2^{ab}$.
Cantorova veta. Cantorova veta: $a<2^a$ resp. $|A|<|\mathcal P(A)|$. Ukázali sme si všeobecný dôkaz, potom sme si ho ešte raz ilustrovali na príklade $A=\mathbb N$, aby bolo jasnejšie, prečo sa metóde dôkazu hovorí Cantorova diagonálna metóda.
Z Cantorovej vety vidno aj to, že neexistuje najväčšie kardinálne číslo. (Súvisiaci článok na Wikipédii: Cantor's paradox.)
Spočítateľné a nespočítateľné množiny. Zjednotenie spočítateľne veľa spočítateľných množín je opäť spočítateľné.
Ešte som nedokázal $|\mathbb Q|=\aleph_0$. (Ale s vecami, ktoré sme sa učili by to nemalo byť ťažké - rozmyslíme si to nabudúce.) V d.ú., ktorú som dnes zverejnil, sa tento fakt môže používať. Takisto aj to, že $|\mathbb R|=\mathfrak c$. (Do termínu odovzdania budeme mať obe tieto veci aj dokázané.)

Potom sme sa pozreli na výpočty niektorých konkrétnych kardinálnych čísel - konkrétne $\aleph_0\cdot 2^{\aleph_0}=2^{\aleph_0}$, $\aleph_0^{\aleph_0}=2^{\aleph_0}$ a $\aleph_0^{\mathfrak c}=2^{\mathfrak c}$. Rovnosť $\mathfrak c^{\aleph_0}=\mathfrak c$ som nechal na rozmyslenie pre Vás.

Keďže sme vlastne videli úlohu, kde sme porovnávali $a^b$ a $b^a$ pre nekonečné kardinály (konkrétne $\aleph_0$ a $\mathfrak c$) ako malú odbočku som spomenul, že sa môžete zamyslieť nad tým, ako to je pre reálne čísla: viewtopic.php?t=1249

[Martin Sleziak]

8. týždeň (4.4.)
Spočítateľné. Množina racionálnych čísel $\mathbb Q$ je spočítateľná. (Nerobil som dôkaz, že ľubovoľná množina disjunktných netriviálnych intervalov na priamke musí byť spočítateľná.)

Kardinalita množiny $\mathbb R$:
Dokázali sme, že $|\mathbb R|=\mathfrak c$. (Dôkaz som robil trochu inak ako v texte k prednáške - robil som v desiatkovej sústave, nie v dvojkovej. Navyše som nedokazoval, že čísla s konečným rozvojom sú jediný prípad, kedy má číslo nejednoznačný zápis. Pre dyadický - dvojkový - zápis je táto vec v texte k prednáške dokázaná detailne.)
Ukázal som ešte iný dôkaz, že množina reálnych čísel je nespočítateľná, ktorý je založený na diagonálnom argumente (príklad 3.5.5 v texte k prednáške).
Dôkaz, že množina všetkých spojitých zobrazení z $\mathbb R$ do $\mathbb R$ má kardinalitu $\mathfrak c$, sme preskočili. (Možno sa k nemu niekedy vrátime.)
Existenčné dôkazy.
Ukázali sme, že algebraických čísel je spočítateľne veľa, a teda existujú aj transcendentné čísla. (V dôkaze sme používali fakt, že polynóm stupňa $n$ má nanajvýš $n$ koreňov. Tento fakt by ste mali vedieť z algebry ešte z bakalárskeho štúdia, ale ak si chcete pripomenúť dôkaz, môžete sa pozrieť aj sem: http://msleziak.com/forum/viewtopic.php?t=1349.)
Ukázali sme, že vypočítateľných funkcií (=funkcií, pre ktoré existuje algoritmus resp. program) je len spočítateľne veľa, a teda existujú aj nevypočítateľné funkcie.
Ďalší podobný dôkaz bol, že existujú body resp. vzdialenosti v rovine, ktoré sa nedajú zostrojiť pomocou pravítka a kružidla. Niečo k tejto téme je stručne napísané aj tu: viewtopic.php?t=1532

Videli sme viacero dôkazov ktoré boli existenčné (nie konštruktívne). Dôkazy podobné tým, ktoré sme videli tu - kde ukážeme že nejaká množina je v istom zmysle väčšia ako jej podmnožina a preto musí byť niečo v rozdiele - sa vyskytujú v matematike často. Podobne ako sme to urobili mi, často sa využíva kardinalita. Ale niekedy sa používajú aj iné spôsoby, ako sa meria to, že niektorá z množín je väčšia. Niečo k existenčným dôkazom sa dá prečítať tu: viewtopic.php?t=856 (Pravdepodobne ste sa však s niektorými pojmami, ktoré sa tam vyskytujú, na učiteľskom štúdiu nestretli.)

Čo sa týka zvyšku semestra:
V tomto okamihu máme prebraté veci, ktoré vám treba vedieť, aby ste vedeli riešiť úlohy, ktoré odovzdávate.
Nabudúce by som porozprával ešte niečo o Cantor-Bernsteinovej vete a o nejakých veciach, ktoré s ňou súvisia: viewtopic.php?t=1275
A ešte máme viacero tém, o ktorých by sa dalo niečo porozprávať: viewtopic.php?t=1266

[Martin Sleziak]

9. týždeň (11.4.)
Na začiatku sme sa pozreli na nerovnosť $x^y>y^x$ pre reálne čísla: viewtopic.php?t=1249

Iný dôkaz Cantor-Bernsteinovej vety.
Ako som kedysi sľúbil, ešte sme sa vrátili ku Cantor-Bernsteinovej vete: viewtopic.php?t=1275
Najprv sme sa pozreli na viacero, konkrétnych príkladov, potom sme pomocou nich urobili nejaký dôkaz Cantor-Bernsteinovej vety. (A aspoň stručne sme ho porovnali s dôkazom, ktorý sme mali predtým.)

Dohodli sme sa, že nabudúce (o dva týždne) môžem porozprávať niečo o veciach súvisiacich s axiómou výberu..

[Martin Sleziak]

18.4. Veľkonočný pondelok

11. týždeň (25.4.)
Axióma výberu.
Sformulovali sme axiómu výberu (AC).
Ukázali sme pomocou AC:
* Existenciu jednostrannej inverznej funkcie pre surjekciu.
* Ekvivalenciu Cauchyho a Heineho definície spojitosti (t.j. spojitosti a sekvenciálnej spojitosti).

Medzi dôležité dôsledky axiómy výberu patria napríklad:
* Existencia bázy pre ľubovoľný vektorový priestor.
* Princíp dobrého usporiadania pre každú množinu existuje dobré usporiadanie.
* Počas semestra sme spomenuli niektoré dôsledky pre kardinálne čísla (konkrétne porovnateľnosť a tiež $a+b=a\cdot b= \max\{a,b\}$.

Ako nepríjemné dôsledky axiómy výberu sme spomenuli Banach-Tarského paradox (bez dôkazu) a neexistenciu translačne invariantnej miery na $\mathbb R$. (Tu sme uvideli aj dôkaz, ktorý sa opiera o Vitaliho konštrukciu.)

Veci, o ktorých sme hovorili sa dajú nájsť:
* V slajdoch na stránke: 06choice.pdf.
* V poznámkach k tomuto predmetu podľa starej akreditácie: https://msleziak.com/vyuka/2014/temno/
* Veľa ďalších vecí týkajúcich sa AC sa dá nájsť v poznámkach k predmetu Aplikácie teórie množín.