Informace o přednášce a cvičení z Matematických struktur (NMAI064, vyučují A. Pultr a M. Klazar), LS 2017/18

Sylabus a anotace. Viz SIS.

Doba a místo. Přednáška je v pondělí 9-10:30 v S8 na Malé Straně a cvičení v úterý 15:40-17:10 v S9 na Malé Straně . 

Literatura. Skripta prof. A. Pultra jsou zde .

Konzultační hodiny. Po dohodě. Pracovna A. Pultra i M. Klazara je v malostranské budově ve 2. patře, místnost č. 224.

Zápočet. Za vyřešení alespoň 1/2 úloh zadávaných na přednášce/cvičení.
Zkouška. Zkouškové termíny budou uvedeny v SISu. Požadavky ke zkoušce z NMAI064.  Zde je pár dalších konkrétních zkouškových otázek ode mne.  1. Věty o pevných bodech v uspořádaných množinách a jejich použití. 2. Dokažte, že existuje neměřitelná množina (např. podmnožina jednotkové kružnice) a popište paradox věštce pro reálné funkce (budete-li znát důkaz, tím lépe, ale nepožaduji ho). 3. Vyslovte a dokažte Müllerovu větu o rekonstrukci grafů. 4. Pro okruh R a ideál I v něm dokažte, že R/I je obor integrity (resp. těleso), právě když I je prvoideál (resp. maximální ideál).  5. Uveďte oddělovací axiomy topologických prostorů a některé související výsledky. 6. Uveďte vlastnosti kompaktních topologických prostorů (a některé dokažte). 7. Uveďte vlastnosti souvislých topologických prostorů (a některé dokažte).
1. přednáška/cvičení úterý 6. 3. 2018. 7.3 (Tarského-Knasterova věta o pevném bodu) skript prof. Pultra - 7.4.2 (stabilita her). Čtyři úlohy: 1. Proč je zobrazení F v důkazu 7.4.1 isotonní? 2. Dokažte Cantorovu--Bernsteinovu větu pomocí teorie grafů. 3. Proč je zobrazení Phi_{A,B} v důkazu 7.4.2 isotonní? 4. Ve Faktu v důkazu 7.4.2 doplňte důkazík toho, že strategie S_I je vytrvalá. Odevzdejte mi je prosím e-mailem do půlnoci 15. 3.
2. přednáška/cvičení pondělí 12. 3. 2018. 7.1 (Bourbakiho věta o pevném bodu) a 7.2 (První Kleeneho věta o rekurzi) skript prof. Pultra. Axiom výběru a dva z něj plynoucí paradoxy: nelze změřit délku úplně každého oblouku kružnice (Vitaliho věta z r. 1905 o existenci neměřitelné množiny) a pro každou funkci f z R do R a každé číslo a z R lze z hodnot f(x) s x < a skoro vždy (až na nejvýše spočetně mnoho a) správně uhádnout hodnotu f(a) (Hardin a Taylor, 2008), důkaz jsem bohužel nestihl dokončit. Čtyři úlohy: 1. Proč je zobrazení f v důkazu 7.1 isotonní? 2. Dokažte, že tyto dvě formulace axiomu výběru jsou ekvivalentní: (i) pro každé zobrazení f z A na B existuje zobrazení g z B do A, že f(g) je identické zobrazení z B do B (formulace ve skriptech) a (ii) pro každý systém {M_i | i v I} neprázdných množin existuje zobrazení f z I do sjednocení všech M_i, že pro každé i v I prvek f(i) leží v M_i. 3. Dokažte, že relace ~ (pro a, b dva body jednotkové kružnice a ~ b znamená, že b přejde v a nějakou racionální rotací) je relace ekvivalence. 4. Dokažte, že každá dobře uspořádaná množina reálných čísel (vzhledem k obvyklému uspořádání reálné osy) je nejvýše spočetná. Odevzdejte mi je prosím e-mailem do půlnoci 21. 3.
3. přednáška/cvičení úterý 20. 3. 2018. Zornovo lemma je tento axiom: má-li v uspořádané množině X každý řetězec (lin. uspořádaná podmnožina) horní mez, pak má X maximální prvek (k němuž neexistuje větší), dokonce nad každým prvkem X leží maximální prvek. Je ekvivalentní axiomu výběru. Úloha 1: odvoďte z Zornova lemmatu, že každou množinu X lze dobře uspořádat.  Probíráme kapitolu 2 Modulární a distributivní svazy, hlavně důkazy dvou charakterizačních vět: 1) L je modulární <=> L neobsahuje C_5 a 2) L je distributivní <=> L neobsahuje ani C_5 ani D_3, dokončení důkazu druhé věty příště. Loni jsem to dělal takto a takto. Další dvě (tři) úlohy: 2. (poznámka 2.1.1 ve skriptech) Dokažte, že když a <= c, pak  a spojeno (b průsek c) <= (a spojeno b) průsek c. 3. (prof. A. Pultr) Dokažte, že když svaz obsahuje C_5, pak není modulární. 4. (tuto jsem asi na přednášce  jasně neřekl, ale přesto ji tady uvedu) Dokažte, že ve svazu z duální distributivity plyne distributivita. Odevzdejte mi je prosím e-mailem do půlnoci 30. 3.
4. přednáška/cvičení úterý 27. 3. 2018. Dokončení důkazu druhé věty charakterizující distributivní svazy dvěma zakázanými obrázky. Problém hranové rekonstrukce grafů. Rekonstrukční hypotéza (Harary, 1964): mají-li grafy G a H alespoň 4 hrany a shodné sady S(G) a S(H) podgrafů vzniklých smazáním jedné hrany, jsou G a H izomorfní. Dokážeme Müllerovu větu (z r. 1977): platí to, mají-li G a H n > 5 vrcholů a m > 1 + n(log_2(n) - 1) hran. Čtyři úlohy: 1. Vysvětlete přesně argument s permutováním prvků a, b, c v důkazu věty o distributivních svazech (ve skriptech: 2.6. věta, str. 52 nahoře). 2. Vysvětlete přesně argument se záměnou průseku a spojení v důkazu věty o distributivních svazech (tamtéž). 3. Dokažte vzorec Principu inkluze a exkluze pomocí počítání dvěma způsoby (tj. nalezněte množinu dvojic tak, že kardinalita spočítaná seskupením podle 1. složky dá jednu stranu PIE a  seskupením podle 2. složky druhou). 4. Dokažte rekonstruční hypotézu pro grafy se čtyřmi hranami. Odevzdejte mi je prosím e-mailem do půlnoci 5. 4.
5. přednáška/cvičení úterý 3. 4. 2018. Důkaz Müllerovy věty. Viz tento a tento můj loňský text. Čtyři úlohy: 1. Co jsou přesně X a X_1, ..., X_n v aplikaci PIE v důkazu (vzorec pro inj_D(G, H))? 2. Jak se přesně sečtením dostane vzorec pro inj_d(G, H)? 3. Proč z neizomorfismu G a H plyne, že inj(G, H) = 0? 4. Proč přesně platí, že sum_{d=0}^m inj_d(G, H) = sum_{d=0}^m inj_d(H, H) = n! ? (H označuje H s pruhem, doplněk grafu H.) Odevzdejte mi je prosím e-mailem do půlnoci 12. 4.
6. přednáška/cvičení úterý 10. 4. 2018. Probírali jsme oddíl IV.9 skript - poznámky o některých speciálních algebrách. Nebudu to zde už vše připomínat, pouze úlohy. 1. Dokažte Základní větu aritmetiky ve tvaru: multiplikativní monoid přirozených čísel (N, krát, 1) je izomorfní volnému monoidu  (F(P), +, prázdná množina) konečných multimnožin  prvočísel (např. {3, 3, 2} + {5, 3, 2, 5} = {2, 2, 3, 3, 3, 5, 5}). 2. Dokažte, že monoid (Z_m^*, krát, 1) (zbytkové třídy modulo m, nesoudělné s m) je (komutativní) grupa. 3. Dokažte, že pro každou (ne nutně normální) podgrupu N (ne nutně komutativní) konečné grupy G jsou {aN | a je v G} i {Na | a je v G} stejně velké rozklady G (tj. se stejným počtem bloků) na bloky velikosti |N|, takže |N| dělí |G|. 4. Každý konečný obor integrity už je těleso. Odevzdejte mi je prosím e-mailem do půlnoci 29. 4.
7. přednáška/cvičení úterý 17. 4. 2018. Pokračovali jsme v probírání oddílu IV.9 skript - poznámky o některých speciálních algebrách, věnoval jsem se ideálům v okruzích, zejména jsem dokázal, že 1) I je prvoideál v R iff R/I je obor integrity a 2) I je maximální ideál v R iff R/I je těleso. Dále jsem zhruba vyložil  konstrukci konečných těles: je-li a=a(x) ireducibilní polynom stupně k v okruhu polynomů Z_p[x] (koeficienty jsou zbytkové třídy modulo prvočíslo p), je faktorokruh Z_p[x]/I, kde I = (a) je hlavní ideál generovaný a (česky řečeno, všechny násobky a), konečně těleso s p^k prvky. Existuje ale vždy takový a? Ano, máme pro jejich počet dokonce vzorec: počet ireducibilních a monických (vedoucí koeficient je 1) polynomů stupně k v Z_p[x] se rovná (1/k)sum_{d dělí k}mju(d)*p^{k/d} (což je vždy >0), kde mju(n) je Möbiova funkce  (má hodnoty +-1 a 0) - bohužel jsem neměl čas tento vzoreček dokázat. Úlohy jsem na přednášce dal myslím jen tři, ale zde dám podle tradice čtyři. 1. Dokažte, že jednotky v okruhu tvoří grupu. 2. Dokažte, že pro každou podmnožinu M okruhu R existuje (vzhledem k inkluzi) nejmenší ideál obsahující M (značí se <M> - ideál generovaný M). 3. Dokažte, že každý vlastní ideál okruhu je obsažený v maximálním ideálu. 4. (To jsem na přednášce určitě nezmínil, ale zadávám to zde.) Dokažte, že pro Möbiovu funkci je součet sum_{d dělí n}mju(d) rovný 1 pro n = 1, ale jinak je 0. Odevzdejte mi je prosím e-mailem do půlnoci 29. 4.
8. přednáška/cvičení úterý 24. 4. 2018. Oddíl IV.6 skript, definovali jsme pojem volné algebry nad množinou M a sestrojili jsme ji pro finitární typ. Je to konstrukce z "ničeho" jen syntaktickými prostředky. Předsi jen jsem pořádně dokázal, že počet ireducibilních a monických (vedoucí koeficient je 1) polynomů stupně k v Z_p[x] se rovná (1/k)sum_{d dělí k}mju(d)*p^{k/d} (pomocí generujících funkcí a Mobiovy inverze). Tentokrát žádné úlohy.
9. přednáška/cvičení pondělí 30. 4. 2018. Kapitoly V.1 a V.2 skript o topologii (Základní topologické pojmy a Příklady). Úlohy. 1. Topologie je dána systémy okolí a definujeme množinu U jako otevřenou, právě když je okolím každého svého bodu. Dokažte, že tyto U skutečně splňují axiomy (ot1) - (ot3). 2. Topologie je dána otevřenými množinami a definujeme množinu O jako okolí bodu x, právě když existuje otevřená množina U, že x je v U a ta je obsažena v O. Dokažte, že tyto O skutečně splňují axiomy (ok1) - (ok4). 3. Dokažte vlastnosti uzávěru uz(M) množiny M: (1) M je obsažena v uz(M) a uz(prázdná) = prázdná, (2) M je obsažena v N  implikuje uz(M) je obsažen v uz(N), (3) uz(M sjednoceno N) = uz(M) sjednoceno uz(N) a (4) uz(uz(M)) = uz(M). 4. (Zariského topologie) Množinu U obsaženou v C^k (k-tice komplexních čísel) prohlásíme za uzavřenou, rovná-li se množině společných nulových bodů nějaké množiny polynomů z C[x_1, ..., x_k] (polynomy v k proměnných s komplexními koeficienty). Dokažte, že takové U splňují axiomy uzavřených množin (prázdná a vše jsou U a konečná sjednocení a libovolné průniky množin U dávají zase množinu U). Odevzdejte mi je prosím e-mailem do půlnoci 9. 5.
10. přednáška/cvičení úterý 15. 5. 2018. Kapitola V.5 skript o topologii (Několik speciálních požadavků, tj. oddělovací axiomy). Dostali jsme se před 5.8, oddělování a základní konstrukce ještě ne. Tentokrát žádné úlohy.
11. přednáška/cvičení úterý 22. 5. 2018. Kapitola V.6 skript o topologii (kompaktnost): každý komp. H. pr. je normální a každý Lindelöfův reg. pr. je normální. Kapitola V.7 skript o topologii (souvislost).  Žádné úlohy.


květen 2018