1. přednáška a cvičení 20. 2. 2017. (A.
Pultr): Úvod do relací a relačních systémů, práce s nimi. Homomorfismy.
(M. Klazar) Důsledky axiomu výběru: existence neměřitelné množiny
(Vitali, 1905) a existence věštce, který pro každou funkci f z R do R a
pro každé a z R, kromě nejvýše spočetně mnoha výjimek a, ze zúžení f na
(-oo, a) uhádne hodnotu f(a) (Hardin a Taylor, 2008). O souvisejícím
Banachově--Tarského paradoxu to dopovím příště.
Text ke cvičení/přednášce (anglicky).
2. přednáška a cvičení 27. 2. 2017. (A.
Pultr) Relace, součiny, univerzalita produktů, definice částečného
uspořádání. (M. Klazar): Věštec se mýlí jen na řídké množině, její
definice. Zmínka o
knize Hardina a Taylora
o "generalized hat problems". Příklad takového kloboukového problému
jako úloha --- Alice dostane na hlavu červený či zelený klobouk, totéž
Bob, na svůj klobouk si nikdo nevidí, ale vidí klobouk druhého a oba
mají současně hádat barvu svého klobouku. Nesmějí spolu samozřejmě
mluvit, ale předem si mohou dohodnout společný postup/strategii. Mohou
si Alice a Bob domluvit takový postup, aby vždy alespoň jeden z jejich
dvou tipů barvy vlastního klobouku byl správný? Důkaz Tvrzení 3 z
minula.
Banachův--
Tarského paradox
v R^3 (vygooglete si článek L. Picka Hrášek a sluníčko). Další úloha
(dětská verze B.-T. paradoxu): pro každé dvě omezené množiny A, B v R^d
s neprázdnými vnitřky existuje n (konečně mnoho) množin X_1, ..., X_n v
R^d a n posunů t_1, ..., t_n prostoru R^d, že platí X_1U...UX_n = A a
t_1(X_1)U...Ut_n(X_n) = B (z nějakých n kousků nasjednocuji A a z
jejich posunů nasjednocuji B). Úloha: ukažte, že pro omezenou A a
neomezenou B se to udělat nedá a vymyslete další příklady, kdy to po
vynechání předpokladů omezenosti a neprázdnosti vnitřku nejde. Tarski
dokázal, že se B.-T. paradox nedá provést v R^2 a hned se v r. 1925
otázal, zda jsou kruh K a čtverec C v R^2 a se stejnou plochou konečně
ekvirozložitelné pomocí izometrií prostoru R^2 (tj. jestli existuje
puzzle s
konečně mnoha kousky, z nichž se jedním způsobem složí K a jiným se složí C), to je tzv.
Tarského problém kvadratury kruhu. Jde to! - a stačí kousky puzzle jen posouvat, jak v r. 1990 dokázal
M. Laczkovich, který T. problém vyřešil. Nejnověji bylo dokázáno
zde, že existuje puzzle řešící T. problém složený pouze z
borelovských
kousků (ležících velmi nízko, na třetí či snad čtvrté úrovni borelovské
hierarchie). Takové kousky už by se skoro daly vystřihovat z papíru,
nicméně Dubins, Hirch a Karush již v r. 1964 dokázali
zde,
že to pomocí topologických disků nejde (D je top. disk, když D = f(K),
kde f z R^2 do R^2 je oběma směry spojitá bijekce): neexistuje n
top. disků D_1, ..., D_n a n izometrií t_1, ..., t_n prostoru R^2, že
platí D_1U...UD_n = K a t_1(D_1)U...Ut_n(D_n) = C, přičemž v obou
sjednoceních mají množiny po dvou disjunktní vnitřky (překrývat se
mohou jen hranice disků). Úloha: dokažte to pro rovinné mnohoúhelníky
místo disků (tj. pro top. disky, jejichž hranice jsou lomené čáry).
Triviální? Dokažte to pro top. disky, jejichž hranice jsou po
částech C^1 křivky (až na konečně mnoho výjimek má hranice definovanou
spojitě se měnící tečnu). Takové kousky puzzle už lze snad doopravdy
vystřihovat z papíru ... ale už to k ničemu není.
Text ke cvičení (anglicky).
3. přednáška a cvičení 6. 3. 2017. (A.
Pultr): ... . (M. Klazar): Důkaz věty, že axiom výběru (existence
výběrové funkce na potenci X bez prázdné množiny) implikuje dobré
uspořádání množiny X.
Hypotéza hranové rekonstrukce a homomorfismy grafů. Mullerova
věta: dva grafy s n vrcholy a m > n.log_2n hranami (přesná hranice
je v textu ke cvičení) a stejnými sadami (podgrafů s jednou smazanou
hranou) jsou izomorfní, dokončení důkazu příště.
Text ke cvičení (anglicky) .
4. přednáška a cvičení 13. 3. 2017. (A. Pultr): ... . (M. Klazar): Dokončení důkazu
Mullerovy
věty. Důkaz Cantorovy--Bernsteinovy věty (existence injekcí z X do Y a
z Y do X implikuje bijekci mezi oběma množinami) pomocí
Tarského--Knasterovy věty o pevném bodu pro úplné svazy.
Text ke cvičení (anglicky).
5. přednáška a cvičení 20. 3. 2017. (A.
Pultr): ... . (M. Klazar): Grafový důkaz Cantorovy--Bernsteinovy věty.
Kalmárova věta o existenci neprohrávající strategie, důkaz opět
Tarského--Knasterovou větou o pevném bodu. Modulární svazy a jejich
charakterizace zakázanou konfigurací (pěticyklus C_5), dokončení důkazu
příště.
Text ke cvičení (anglicky).
6. přednáška a cvičení 27. 3. 2017. (A.
Pultr): ... . (M. Klazar): Svaz je modulární <=> neobsahuje
podsvaz C_5. Distributivní svazy. Svaz je distributivní <=>
neobsahuje ani podsvaz C_5 ani podsvaz D_3.
Text ke cvičení (anglicky).
7. přednáška a cvičení 3. 4. 2017. (M. Klazar, př. i cvič.):
Text k přednášce i cvičení (anglicky).
8. přednáška a cvičení 10. 4. 2017. (A. Pultr): ... . (M. Klazar):
Text ke cvičení (anglicky).
17. 4. 2017 - Velikonoční pondělí.
9. přednáška a cvičení 24. 4. 2017. (A. Pultr): ... . (M. Klazar):
Text ke cvičení (anglicky).
1. 5. 2017 a 8. 5. 2017 - státní svátky (Svátek práce a Den vítězství).
10. přednáška a cvičení 15. 5. 2017. (A. Pultr): ... . (M. Klazar):
Text ke cvičení (anglicky).
11. přednáška a cvičení 22. 5. 2017. (A. Pultr): ... .
květen 2017