Z poslední přednášky: Dokončili jsme "problém šátnářky", zavedli Latinské obdélníky. Zároveň jsme zadefinovali uspořádání, isomorfismus, vnoření a končili jsme větou s vnořením.

Vrátíme se ještě na chvilinku ke vnoření a isomorfismu. Pokud se blíže pozastavíme nad vnořením, zjistíme, že jediná podmínka oproti isomorfismu je, že vnoření nemusí být na. Dá se ale řící, že každé vnoření je zároveň isomorfismus, nesmíme však uvažovat celé množiny, ale vybrat z množiny obrazů pouze tu část, která bude zároveň na. Ale to je jen na okraj.

Poslední věta z minulé přednášky:
Věta: Pro každou částečně uspořádanou množinu (X,R) existuje množina Y a vnoření f:(X,R) ® (P(Y),S).
Pozn. P(Y) je v tomto případě množina všech podmnožin, běžně psaná psacím P.

Důkaz: Vezměme za množinu Y množinu X.
Definujme f:X->(P(Y),S) předpisem f(X)={y; (y,x) Î R}.
O f dokážeme, že f je na, prosté a splňuje (iii), (iv) z definice isomorfismu (minulá přednáška).
i) a ii) Z definice: x ą y Ţ f(x) ą f(y). Platí x Î f(x) pak x ą y a platí buď (x,y) Î R nebo (y,x) Î R, nemužou platit obě, neboť jde o uspořádanou množinu, nemůže se tedy stát aby (y,x) bylo v uspořádání a (x,y) také pokud si nejsou rovny, což nejsou z definice. A tedy dle definice buď x ą z f(y) nebo y ą z f(x) Ţ f(x) ą f(y).
iii) (x,y) Î R Ţ f(x) Í f(y)
(Platí neboť (z,x) Î R Ţ (z,y) Î R Ţ z Î f(y)).
iv) f(x) ą f(y) Ţ (x,y) Î R
(Platí, neboť x Î f(x) Ţ x Î f(y) Ű (x,y) Î R).
(Zde by se pro názornost hodilo naskreslit uspořádání (X,R). Připadá mi však jednodušší, pokud si něco takového představíte - obyčejný koláč a v něm bod x. Přiřadíme-li bodu x všechny prvky pod ním, což odpovídá uspořádání, pak je již mnohem snažší nahlížet na předchozí důkaz. Je také dobré nezapomenout na definici - f(X) jsou všechny y, která jsou v relaci s daným x).

Definice: (X,R) je částečně uspořádaná množina (jinak také ČUM či poset).
x Î X nazvu minimální jestliže neexistuje y Î X takové, že x ą y a (y,x) Î R (jinými slovy, neexistuje žádný menší prvek, než x)
x Î X nazvu nejmenší jestliže pro každý prvek " y Î X platí (x,y) Î R (jinými slovy, není žádný stejný a všechny jsou větší)
Je třeba dát pozor na nejmenší a minimální - minimálních může být velice mnoho (je vždy aspoň jeden), nejmenší je vždy maximálně jeden (a občas také žádný).

Definice: (X,R) je ČUM (viz výše).
x Î X nazvu maximální jestliže je minimálním prvkem pro relaci (X,R^-1)
x Î X nazvu největší jestliže je nejmenší pro relaci (X,R^-1)
(Opačná relace R^-1 je vlastně relace na druhou stranu, tedy (x,y) Î R^-1 Ű (y,x) Î R. Jinak (R^-1)^-1 = R, to jen pro úplnost.

Věta: Každá konečná, ČUM (X,R), X ą 0 (X není prázdná množina) má minimální prvek. (Pozor na předpoklady - je nutné aby množina byla konečná a jedná se o minimální prvek, nejmenší být nemusí.)
Důkaz: indukcí podle |X| (počtu prvků X)
|X|=1 Ţ (Z def. - neexistuje žádný prvek X, který není x a je s x v relaci (nemůže existovat, když je X je jednoprvková množ., to je asi jasné), takže tento prvek je minimální).
|X|=n ® n+1 Zvolme x.
   Vytvořme X₁ tak že vezmeme všechny y Î X, y ą x a (y,x) Î R (zde pozor - musí být (y,x), tj. všechny y pod vybraným x - je to důležité, jinak by totiž evidentně vůbec nefungovalo. Pod je myšleno jakožto, všechny před x v daném uspořádání, tedy pod ním).
   Zároveň vytvořme relaci R₁ která bude průnikem relace R a kartézského součinu X₁ ´ X₁. Pro představu, velice snadné je to pokud si představíte relaci R jako množinu všech těch šipek, které z toho udělají uspořádanou množinu (částečně či úplně, to je jedno. V našem případě mluvíme o částečně uspořádané, je ale jasné, že minimální prvek bude mít i úplně uspořádaná množina, jen bude mít vždy jen jeden (předpokládám konečnost množiny !!)). Kartézský součin je pak množina šipek "každý s každým". Pokud udělám průnik, zbudou mi jen ty šipky, které byly v R a netýkaly se zvoleného x, neboť to v X₁ není.
   Mám tedy množinu s maximálně n prvky. Pokud je množina X₁ prázdná, pak x je minimální prvek (to plyne z definice - neexistuje žádný prvek v relaxi s vybraným x). A pokud X₁ prázdná není, musí v ní být minimální prvek (plyne z indukčního předpokladu, X₁ má maximálně n prvků, jistě neobsahuje x a neobsahuje všechny prvky "nad" x).

Důsledek: Pro každou konečnou ČUM (X,R) existuje lineární (úplné) uspořádání (X, Ł), tak že R Í Ł.
Důkaz důsledku: Postupovalo se indukcí podle |X|. Pokud jsem to dobře pochopil, jde o to, že si oddělím minimální prvky a zbytek množiny. Minimálním prvkům přiřadím nějaké úplné uspořádání a se zbytkem množiny pracuji jako s celou na začátku, tedy oddělím minimání prvky apod.. jednodušše indukcí.
Pak mám několik množin, kterým jsem přiřadil nějaké úplné uspořádání (tj. Ł, s tím, že minimální prkvy budou =, musím tedy jen rozhodnout o jejich uspořádání) a zbývající množinu, která je již úplným uspořádáním (a pokud není, pak opět vezmu minimální prvky, tedy indukcí pracuji až dokud není úplným uspořádáním (pro |X|=1 je každé ČUM zároveň úplným uspořádáním, to je asi dost zřejmé)).
No a pak již jen stačí poskládat nějakým rozumným předpisem tyto úplné uspořádání do jednoho úplného a je to.

(X, Ł) se nazývá topologické uspořádání - topologic sort

Důsledek: (X,R) je ČUM. |X| Ł a(X,R)* w(X,R), kde a(X,R) je maximální velikost podmnožiny A Í X takové, že žádné dva různé prvky A nejsou v relaci (nejsou porovnatelné) a w(X,R) je maximální lineárně uspořádaná podmnožina (X,R).
Tak a teď česky (nebo slovensky ?) - a(X,R) je v takovém tom hezkém diamantu, kterýžto se nazývá grafem, co vypadá jako špatně nakreslená krychle, největší šířka. Tedy prostě maximum počtu bodů na stejné úrovni, stejném patře.
A w(X,R) je nejdelší řetezec. Podmínkou je, že takový řetězec nemůže jít dolů, tedy proti smyslu uspořádání, to by jste pak neprocházeli uplné uspořádání, ale nějakou hloupost. Je to tedy vlastně výška, počet pater.
No a důsledek říká, že počet prvků v množině je maximálně roven násobku výšky a maximální šířky takové množiny.
Ještě na okraj - podmnožina A se nazývá nezávislá množina nebo také antiřetězec. To je ta, co má pouze vzájemně neporovnatelné prvky.
Důkaz: Definujme rozklad množiny X na množiny X₁, X₂, ..., X_t předpisem
      X₁={x; x je minimální v (X,R)}
      X₂={x; x je minimální v (X-X₁,R')} kde R'=R Ç ((X-X₁) ´ (X-X₁))
      až X_t je pak množina všech x minimálních prvků z relace množiny X bez všech předchozích X_i s relací R' kde R' je relace R v průniku s kartézským součinem toho co zbylo z množiny X s tímtéž.
Buď t takové, že |X_t| ą 0 & |X_t+1| = 0, aby X_tbyla poslední neprázdná množina.
Je zřejmé: že X_i jsou disjunktní. Zároveň jsou nezávislé.
Celé to tu v zápiskách mám složitější - dokázali jsme že existuje řetězec s t prvky, kdy prvky uspořádání jsou vzaty vždy ze sousedních množin a společně tvoří onen řetězec, tedy úplně uspořádanou podmnožinu množiny X. Tj. délka řetezce je t, přičemž to souhlasí s w(X,R).
Celé my to připadá jasné, je asi potřeba si řádně uvědomit, že skutečně existuje řetězec s t členy. To tak nějak vychází z definice minimálního prvku a toho co jsme dělali. Pokud jsem do první množiny vzal všechny minimální prvky X a do druhé všechny minimální prvky X-X₁, pak je jasné, že prvky X₂ musí s prvky X₁ tvořit nějaké řetezce, tedy patřit do relace R, neboť jinak by byly minimální již v X a nikoliv až poté, co jsem všechny minimální prvky odebral. V definici minimálního prvku stojí, že jde o prvky pro které neexistují žádné takové y, které by jako uspořádaná dvojice (y,x) patřila do relace. Tedy pokud jsou prvky z X₂ minimální až po odstranění minimálních prvků (těch co jsou v množině X₁) v prvním kroku, musely s nimi tvořit uspořádanou dvojici patřicí do relace, protože pokud ne, padly by již při prvním kroku do množiny minimálních prvků.
Možná to zní trochu podivně, ale pokud jsou s tím ještě nejasnosti, tak je třeba připomenout, že u uspořádané dvojice záleží na pořadí, tedy je dobré uvědomit si, jaké pořadí je ve kterém místě myšlené (vždy je to (x₁,x₂) kde x₁ je z X₁ apod. - což připomíná podlaží, kde X₁ je přízemí atd.)
Zbytek důkazu už je jen o tom, že za a(X,R) beru maximum z |X_i|. Počet prvků X je tedy určitě menší či rovna násobku největší šířky a počtu "pater".

Spernerův problém: (v učebnici tuším na straně 209)
určit a(P(X),Í), kde P(X) je množina všech podmnožin a |X|=n. Tento problém onačíme s(n) což představuje hodnotu a(P(X),Í)
a(P(X),Í) můžu zespoda omezit jistě 1-čkou. Můžu však dokonce více, jistě jej můžu omezit i třeba n (k vysvětlení se dostanu hned) a zhora omezit 2ⁿ.
A vysvětlení - představím-li si Hasseův diagram, máte jej všichni nakreslený, je to takový ten diamant což je pro systém podmnožin třiprvkové množiny, nebude těžké představit si tento případ. Mám tedy vlastně zadané n. Z diagramu je dosti patrné, že na jednom patře budou podmnožiny se stejným počtem prvků, vím tedy jistě že pro každé n bude určitě na nějakém patře aspoň n těchto podmnožin. A zhora jej omezuji 2ⁿ což je počet všech podmnožin n prvkové množiny. A pokud by tedy všechny byly na stejném "patře", pak to bude právě toto číslo. Je to pouze omezení.
Kolik ale bude maximálně množin na jednom patře ? No pokud tedy dále věříte tomu, že na jednom patře budou vždy množiny se stejným počtem prvků a to dokonce všechny, pak bude právě n+1 pater (nezapomeňte na prázdnou množinu, proto n+1) (to jen na okraj) a v nejširším patře musí být ty množiny co budou mít polovinu prvků X, tedy mohutnost n/2. Proč ? Protože počet k-prvkových podmnožin n-prvkové množiny je n nad k. A to je maximální pro n nad n/2 (z n/2 berte třeba dolní celou část pro případ lichého n).
Na přednášce ještě padlo, že určit onu šířku, je vlastně nalezením systému podmnožin takových, aby pokud vezmu dvě množiny z takového systému nebyly jedna částí druhou (ani rovny). A zároveň, aby byl počet množin v takovém systému co největší. To v již použitém připodobnění znamená najití onoho patra, kde bude nejvíce podmnožin X.

Věta: a(P(X),Í) = (n nad n/2)
Důkaz: ten již v další přednášce i když už vyřčeného je to myslím dosti zřejmé.