Page 1 of 1

Prednášky LS 2020/21

Posted: Fri Feb 12, 2021 3:49 pm
by 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=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.)

Dohodli sme sa, že budeme hodiny nahrávať. Videá by sa mali dať nájsť tu: https://web.microsoftstream.com/group/c ... 7d2619bb45 (A tiež sa budem snažiť udržiavať tab s videami, ktorý som pridal v kanáli Prednášky.)

Veci, ktoré som počas hodiny písal, by sa mali dať nájsť medzi súbormi v kanáli Prednášky: Teams, Sharepoint

Re: Prednášky LS 2020/21

Posted: Mon Feb 22, 2021 12:53 pm
by Martin Sleziak
1. týždeň (17.2.)
Na začiatku bol nejaký stručný pokec - nejaký historický úvod a k čomu by to vlastne malo celé smerovať.
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.) Ukázali sme aj asociatívnosť pre symetrickú diferenciu $A\triangle(B\triangle C)=(A\triangle B)\triangle C$. Tiež sme ukázali, že z $A\subseteq B$ a $B\subseteq C$ vyplýva $A\subseteq C$.

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

Re: Prednášky LS 2020/21

Posted: Mon Feb 22, 2021 6:07 pm
by Martin Sleziak
2. týždeň (22.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_{A\in\mathcal S} A)=\bigcup\limits_{A\in\mathcal S} (B\cap A)$.

Karteziánsky súčin. Zadefinovali sme usporiadanú dvojicu a karteziánsky súčin.

Funkcie. Definícia zobrazenia. Pripomenuli sme pojem injekcie, surjekcie, bijekcie. Zloženie bijekcií (injekcií, surjekcií) je bijekcia (injekcia, surjekcia). Definícia inverzného zobrazenia, $f^{-1}$ existuje p.v.k. $f$ je bijekcia. (Tieto veci 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[\bigcap\limits_{i\in I}B_i\right]=\bigcap\limits_{i\in I}f^{-1}[B_i]$.
Spomeniem aj to, že viacero úloh o vzore a obraze nájdete vyriešených aj tu na fóre, medziiným aj o vzore prieniku, t.j. presne to čo sme robili na prednáške: viewtopic.php?t=94

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

Re: Prednášky LS 2020/21

Posted: Mon Mar 01, 2021 6:29 pm
by Martin Sleziak
3. týždeň (2.3.)
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$.

Prázdna množina, kvantifikátory, prienik a zjednotenie. 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.
Z toho sme dostali, že zjednotenie prázdneho systému je prázdna množina. Prienik prázdneho systému by bolo "všetko" - s tým sú problémy, takže ten nedefinujeme. (K tomu, prečo tam je problém, sa ešte niekedy vrátime, ale pridám aspoň linku na Wikipédiu: Russellov paradox,)

Re: Prednášky LS 2020/21

Posted: Tue Mar 09, 2021 10:14 pm
by Martin Sleziak
4. týždeň (8.3.)
Kardinálna aritmetika. 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. Ukázali sme, že násobenie kardinálnych čísel je dobre definované. (Pre sčitovanie to zostalo ako nepovinná d.ú., umocňovanie ukážeme neskôr.)
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 nabudúce sa dostaneme k rovnosti $\aleph_0\cdot\aleph_0=\aleph_0$.)
Ukázali sme, že že $|A|=|B|$ $\Rightarrow$ $|\mathcal P(A)|=|\mathcal P(B)|$ resp. že $|A|\le|B|$ $\Rightarrow$ $|\mathcal P(A)|\le|\mathcal P(B)|$.
Spoiler:
Z druhej časti vlastne vyplýva prvá, vďaka Cantor-Bernsteinovej vete.
Vlastne ide o overenie, že ak $f\colon A\to B$ je injekcia, surjekcia, bijekcia, tak aj zobrazenie $\varphi \colon \mathcal P(A) \to \mathcal P(B)$ definované ako $\varphi(C)=f[C]$ je injekcia, surjekcia, bijekcia; my sme sa zaoberali iba injektívnosťou.
Tu šlo v podstate overenie, že pre injekciu platí $f[C_1]=f[C_2]$ $\Rightarrow$ $C_1=C_2$.
Pri tom sme ukázali, že $C\subseteq f^{-1}[f[C]]$ platí pre ľubovoľné zobrazenie a pre injektívne zobrazenie nastane rovnosť.
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

Re: Prednášky LS 2020/21

Posted: Mon Mar 15, 2021 8:25 pm
by Martin Sleziak
5. týždeň (15.3.)
Kardinálna aritmetika.
Vlastnosti násobenia kardinálov.
Ukázali sme, že $\aleph_0\cdot\aleph_0=\aleph_0$.
Ukázali sme, že umocňovanie kardinálnych čísel je dobre definované.
Čomu sa rovná $0^0$, $a^0$, $0^a$.
Vlastnosti kardinálneho umocňovania: Ukázali sme, že $a\le b$ $\Rightarrow$ $a^c\le b^c$,
Dôkazy týchto vlastností sme zatiaľ preskočili: $a^2=a\cdot a$, $a\le b$ $\Rightarrow$ $c^a\le c^b$ (pre $c\ne0$).
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.)

Re: Prednášky LS 2020/21

Posted: Mon Mar 22, 2021 8:35 pm
by Martin Sleziak
6. týždeň (22.3.)
Kardinálna aritmetika.
Ukázali sme, ž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.
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é. Množina racionálnych čísel $\mathbb Q$ je spočítateľná.
Ľubovoľná množina disjunktných netriviálnych intervalov na priamke musí byť spočítateľná.
Potom sme sa pozreli na výpočty niektorých konkrétnych kardinálnych čísel - konkrétne $\aleph_0^{\aleph_0}=2^{\aleph_0}$, $\mathfrak c^{\aleph_0}=\mathfrak c$, $\aleph_0^{\mathfrak c}=2^{\mathfrak c}$ a $(2^{\mathfrak c})^{2^{\mathfrak c}}=2^{2^{\mathfrak c}}$.

Dokázali sme, že $a\le b$ $\Rightarrow$ $c^a\le c^b$ (pre $c\ne0$).
Dokázali sme, že $a\cdot a=a^2$

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

Re: Prednášky LS 2020/21

Posted: Tue Mar 30, 2021 10:14 am
by Martin Sleziak
7. týždeň (29.3.)
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: 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

Re: Prednášky LS 2020/21

Posted: Fri Apr 16, 2021 9:29 pm
by Martin Sleziak
5. apríla hodina odpadla - štátny sviatok.

9. týždeň (12.4.)
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.)

Ešte sme sa vrátili k niektorým príkladom s domácich úloh:$\newcommand{\abs}[1]{|#1|}$
* Zobrazenie $f\colon X\to Y$ je injekcia p.v.k. pre ľubovoľné $A,B\subseteq X$ platí $A\subseteq B \Leftrightarrow f[A] \subseteq f\left[B\right]$.
* Ak $A$, $B$ sú ľubovoľné množiny, tak platí $$\abs{A}+\abs{B}=\abs{A\cup B}+\abs{A\cap B}.$$ (Množiny $A$, $B$ môžu byť aj nekonečné.)
* Ak $f$ je surjektívne, tak $\varphi$ je surjektívne. (Kde $\varphi$ je definované ako $\varphi(g)=g\circ f.$
(K týmto príkladom niečo nájdete aj v topicu, ktorý je venovaný domácim úlohám.)

Re: Prednášky LS 2020/21

Posted: Wed Apr 21, 2021 10:56 am
by Martin Sleziak
10. týždeň (19.4.)
Hľadanie pevných bodov. Pozreli sme sa na nejaké veci o pevných bodoch, ako sa dajú hľadať pomocou iterácií a tiež na to ako sa takéto iterácie dajú nakresliť.
Dokázali sme Banachovu vetu o pevnom bode.
Ukázali sme si babylonskú metódu hľadania druhej odmocniny.

Stručne sme spomenuli aj to, že aj na prvý dôkaz Cantor-Bernsteinovej vety sa dá pozerať ako na hľadanie pevného bodu. (Potrebovali sme tam množinu takú, že $F(C)=C$.) Rozdiel je ale ten, že nepracujeme s reálnou funkciou ale s $\mathcal P(X)\to\mathcal P(X)$.
Obe situácie sa dajú nejako zovšeobecniť na úplné zväzy. Konkrétne dôkaz, ktorý sme robili na dôkaz existencie množiny s vlastnosťou $F(C)=C$, by sa dal s malými zmenami upraviť na dôkaz Knaster-Tarského vety.

Okrem toho som ešte stručne povedal niečo o témach, na ktoré sa dá pozrieť vo zvyšku semestra: viewtopic.php?t=1266