pomoc?
pomoc?
nevite si nekdo rady s prikladem: Dokažte, že relace "≤" ("kroucené") na množině {1,2,..10} je částečné uspořádání,jestliže a ≤ b,právě když a = b nebo b > a+2. Určete minimální a maximální prvky tohoto částečného uspořádání. Kolik má toto uspořádání lineárních rozšíření? diky moc za kazdou radu!!
- Martin
- Supermatfyz(ák|ačka)
- Příspěvky: 330
- Registrován: 19. 2. 2005 20:23
- Typ studia: Matematika Ph.D.
Náhodou jsem se podíval, co se tady píše a náhodou znám odpověď. Je to ČUM:
1) reflexivita přímo z definice
2) tranzitivita snadná (napište si podle def. co je to a<b, b<c; chceme a<c; rozoborem celkem čtyř možností to vyjde)
3) jestli máte v def. ČUM nějakou slabou antisymetrii nebo něco, tak to je jasné, protože nemůže být a>b+2 a zároveň b>a+2
Takže je to relace částečného uspořádání. Maximální prvky jsou 8,9,10, minimální jsou 1,2,3. Pokud tomu někdo nevěří, tak ať si tu relaci nakreslí do tabulky.
Poslední část zadání si nejsem jist že chápu správně. Ale pokud je lineární rozšíření relace prostě relace taková, že obsahuje (relace je množina usp. dvojic) tu původní a ještě je to navíc lineární uspořádání, tak potom je to podle mě dost těžké. Asi bych se snažil vycházet z toho, že vždy tři po sobě jdoucí prvky jsou navzájem neporovnatelné (tou relací ze zadání). Takže na nich můžu zadat nerovnost jak se mi zlíbí, aniž bych tím narušil zbytek toho původního uspořádání.
(Dá se to nahlédnout tak, že si tu relaci nakreslíte do takového toho stromu a vždy prvky, které jsou neporovnatelné, dáte na stejnou úroveň. Takhle přesně to nejde, vždy musíte jeden vynechat a mít tam čtyři úrovně. Ale každou úroveň (s výjimkou té, na niž dáte jen jedno číslo) pak lze rozsekat na tři "subúrovně" ve kterých bude v každé jedna číslice. A to prosím tak, že ani jedna čára nebude mířit směrem dolů!)
To můžu udělat vždy pro tři trojice a ten poslední prvek zůstane mezi nimi, tak jak si to žádá běžné uspořádání na {1,...,10}. Jsou celkem 4 možnosti, které trojice mohu zvolit (mohu vynechat pouze 1,4,7 či 10). Na každé trojici existuje 6 možností, jak mohu ty prvky permutovat. Tedy celkem pro každý výběr tří trojic je 6x6x6 možností. Tedy celkem 4x6x6x6 možností. No, neručím za to. A ani tomu moc nevěřím. Ale na první pohled mi to připadá jako možnost. Budu rád, pokud se v tom někdo bude šťourat víc a řekne mi, jak to má opravdu být. No, jsem si skoro jist, že je jich MINIMÁLNĚ 4x6x6x6, ale teď nevím, jestli jsou to už všechny.
1) reflexivita přímo z definice
2) tranzitivita snadná (napište si podle def. co je to a<b, b<c; chceme a<c; rozoborem celkem čtyř možností to vyjde)
3) jestli máte v def. ČUM nějakou slabou antisymetrii nebo něco, tak to je jasné, protože nemůže být a>b+2 a zároveň b>a+2
Takže je to relace částečného uspořádání. Maximální prvky jsou 8,9,10, minimální jsou 1,2,3. Pokud tomu někdo nevěří, tak ať si tu relaci nakreslí do tabulky.
Poslední část zadání si nejsem jist že chápu správně. Ale pokud je lineární rozšíření relace prostě relace taková, že obsahuje (relace je množina usp. dvojic) tu původní a ještě je to navíc lineární uspořádání, tak potom je to podle mě dost těžké. Asi bych se snažil vycházet z toho, že vždy tři po sobě jdoucí prvky jsou navzájem neporovnatelné (tou relací ze zadání). Takže na nich můžu zadat nerovnost jak se mi zlíbí, aniž bych tím narušil zbytek toho původního uspořádání.
(Dá se to nahlédnout tak, že si tu relaci nakreslíte do takového toho stromu a vždy prvky, které jsou neporovnatelné, dáte na stejnou úroveň. Takhle přesně to nejde, vždy musíte jeden vynechat a mít tam čtyři úrovně. Ale každou úroveň (s výjimkou té, na niž dáte jen jedno číslo) pak lze rozsekat na tři "subúrovně" ve kterých bude v každé jedna číslice. A to prosím tak, že ani jedna čára nebude mířit směrem dolů!)
To můžu udělat vždy pro tři trojice a ten poslední prvek zůstane mezi nimi, tak jak si to žádá běžné uspořádání na {1,...,10}. Jsou celkem 4 možnosti, které trojice mohu zvolit (mohu vynechat pouze 1,4,7 či 10). Na každé trojici existuje 6 možností, jak mohu ty prvky permutovat. Tedy celkem pro každý výběr tří trojic je 6x6x6 možností. Tedy celkem 4x6x6x6 možností. No, neručím za to. A ani tomu moc nevěřím. Ale na první pohled mi to připadá jako možnost. Budu rád, pokud se v tom někdo bude šťourat víc a řekne mi, jak to má opravdu být. No, jsem si skoro jist, že je jich MINIMÁLNĚ 4x6x6x6, ale teď nevím, jestli jsou to už všechny.
"Endure. In enduring grow strong."
- Martin
- Supermatfyz(ák|ačka)
- Příspěvky: 330
- Registrován: 19. 2. 2005 20:23
- Typ studia: Matematika Ph.D.
Tak se omlouvám, ta poslední část je špatně. Opravdu to nejsou všechna lineární rozšíření - uvědomil jsem si to včera, než jsem usnul . Můžu totiž taky libovolně prohazovat po sobě jdoucí dvojice, nebo ty dvojice ani nemusí být "sousedé", ale objedno číslo... Jediné, co musím při seřazování těch čísel dodržet je, že když je A aspoň o 3 větší než B, tak už v tom mém uspořádání musí být A nad B. Ale kolik takových permutací je, to opravdu nevím. A nechce se mi to zjišťovat, protože to nepříjemně zavání principem inkluze a exkluze. Pokud někdo zná nějaké pěkné řešení, nechť ho sem napíše. Nebo pokud někdo ví, že tady řeším něco úplně jiného, než se v tom zadání myslí...
Zdar a sílu
Zdar a sílu
"Endure. In enduring grow strong."