Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Zdravím kolegy,
jako přípravu na blížící se zkoušku si cvičně dokazuji tvrzení, která jsou v mém sešitě nebo v Kapitolách z diskrétní matematiky. Prosím o kontrolu:
1. Každá konečná částečně uspořádaná množina má minimální prvek.
Důkaz zcela vymyšlený mnou, dost krkolomný. Nevím, jestli v něm není nějaký kruh.
Sporem: nechť je konečná částečně uspořádaná množina, která nemá žádný minimální prvek, tj. , kde je ostrá verze . Nechť tedy je zobrazení v takové, že . Označme . Zřejmě je nerostoucí posloupnost přirozených čísel, existuje tedy taková , že . Protože k-prvkových podmnožin je jen konečně mnoho, existují taková , že . Z toho plyne, že je bijekce (permutace) na množině . Existuje tedy takové a , že , jelikož permutace vždy obsahuje cyklus (na požádání dokážu :-) ). Protože ale zobrazí každý prvek na nějaký ostře "menší", platí , což je spor s tím, že .
2. Pro každé částečné uspořádání na konečné množině existuje lineární uspořádání takové, že , tj. každé částečné uspořádání lze na konečné množině zúplnit na lineární.
V mém sešitě je důkaz proveden indukcí podle velikosti , a tak jsem ji zvolil také.
1. Pro zřejmé (každé uspořádání na 1 prvku je lineární).
2. Víme pro , chceme pro . Nechť je nějaký minimální prvek v uspořádání . Označme Jelikož , existuje podle indukčního předpokladu lineární uspořádání tak, že . Uspořádání definujeme jako . Jde zřejmě o lineární uspořádání s nejmenším prvkem . Zbývá ověřit . Nechť , . Pokud , pak , protože . Pokud a , je podle definice . Alternativa , nemůže nastat, protože je minimální prvek. Konečně pokud , je platnost zřejmá.
Dost pravděpodobně přidám brzy ještě další důkazy.
Offline
↑ Olin: Oba důkazy vypadají OK. Nebylo by i to první rychlejší indukcí?
Pro |X|=1 platí.
Pro |X|=k+1 vybereme prevek a, uspořádání redukované na má dle IP minimální prvek b. Pokud je a<b, je a minimální prvek na X, pokud je b<a nebo jsou a,b neporovnatelné, je b minimální prvek na X.
Offline
↑ Kondr:
No jo, samozřejmě že je to tak jednodušší. Úvaha byla: "Je přece blbost, aby nějaká ČUMa neměla minimální prvek. Blbosti vedou ke sporu."
Teď jdu na důkaz věty "o dlouhém a širokém".
Offline
Tak posílám ten "slibovaný" důkaz.
3. Nechť je částečné uspořádání, značí délku maximálního antiřetěžce (nezávislosti, velikost max. nezávislé množiny) a délku maximálního řetězce v tomto uspořádání. Pak platí .
Indukcí podle :
1. .
2. . Nechť je množina všech minimálních prvků z . Jde zřejmě o antiřetěz, protože z minimality všech prvků plyne pro : . Označme . Platí , protože odebráním všech minimálních prvků jsme všechny maximální řetězy v zkrátili o jeden prvek. Podle IP je . Rozebereme dva případy:
i) . Potom je , takže .
ii) . Potom je , takže .
Offline
↑ Kondr:
Díky, já taky ne, jen jsem to opět dělal možná zbytečně složitě - je zbytečné diskutovat velikost množiny , protože vždycky musí platit .
Každopádně teď jsem se vrátil ze zkoušky z diskrétky a snad by to měl být plný počet bodů, takže už asi další důkazy posílat nebudu. Na druhou stranu, kolega Halogan je průkopníkem nového žánru - skripta jako téma na fóru. Že bych se přidal? :-)
Offline
Stránky: 1