Matematické Fórum

↑ misaH:
Podle šipek poznám, že je relace reflexivní, není symetrická, je antisymetrická a je tranzitivní. Na první otázku bych odpověděl třeba R={[b,d], [b,b] ,[b,c], [a,b], [e,b]} (všechny binární relace, kde je vrchol B). Lineární uspořádání znamená, že je to pod sebou, ne? Tak bych řekl 6. A na tu ekvivalenci bych odpověděl ne, protože relace není symetrická. Myslím to dobře? Ze školy jsem nepochopil naprosto nic a učil jsem se to všechno sám podle skript a internetu, ale té matematické mluvě moc nerozumím, proto si v tom nejsem vůbec jistý.

Díky moc za odpovědi.

1) OK, proč to dělat složitější. :)

2) Trošku mě mate ta definice lineárního uspořádání, ty prvky teda musí být srovnatelné, tj. musí být v grafu pod sebou? Nebo můžou být i vedle sebe, když jsou spojené šipkou (takže se vlastně podle té definice rovnají - např [e,b])? A co relace se dvěma stejnými prvky (např. [a,a])?
K tomu řešení: pokud bych to bral tak, že ty, co jsou vedle sebe nebo jsou stejné, jsou lineární uspořádání, vyjde mi, že mohu nalézt lineární uspořádání tvořené asi z patnácti jednotlivých relací - [a,a],...,[e,e]+[a,b],[a,c],[b,c],[b,d],[c,d],....[e,a],[e,b]. Těch dvojprvkových teda bude 15 nad dvěma, tříprvkových 15 nad třema atd.?


3) Je ta relace tranzitivní? Nějak mi ty pojmy pořád nedávají smysl. A jak tuto konkrétní pak prosím rozdělit na třídy? To by existovala jen jedna třída stejných prvků?

Ad 3) Relace S je tranzitivní, jestliže platí . Vágně řečeno, vede-li šipka od x k y a od y k z, pak vede i šipka od x k z. V případě R={[a,a]} máme a=x=y=z a implikace je platí, tedy R je tranzitivní. Zkus si sám rozmyslet, jestli jsou relace (i) {[a,a],[a,b]}, (ii) {[a,a],[b,b]}, (iii) {[a,a],[a,b],[b,b]}, (iv) {} (prázdná relace), tranzitivní.

Ad 2) Za prvé, relace {[a,a]} obsahuje jeden prvek. Šipka od a k b znamená, že prvek [a,b] patří do relace, pokud je touto relací uspořádání, pak to znamená, že . To, že je něco pod sebou, sem teď nepleť, zřejmě si to pleteš s hasseovými diagramy.

byk7 napsal(a):

Lineární uspořádání pak znamená, že každé dva prvky jsou srovnatelné

Tedy, uvažme třeba množinu {a,b,c}, pak {[a,a],[a,b],[a,c],[b,b],[c,c]} je relací uspořádání, ale není lineární (neumím srovnat prvky b a c). Naopak {[a,a],[a,b],[a,c],[b,b],[b,c],[c,c]} už lineárním uspořádáním je.

A k tvému řešení -- to je úplně blbě. Ty srovnáváš prvky množiny , ale máš srovnávat prvky množiny . Jinak řečeno, pokud např. (kde je nějaké uspořádání), pak .

Řekněme, že chceme "uspořádat jeden prvek". Dostaneme tak relace {[a,a]}, {[b,b]}, ..., {[e,e]}. Jsou tyto relace reflexivní, antisymetrické a tranzitivní? Jedná se o uspořádání? Jedná se o lineární uspořádání?

Teď budeme chtít lineární uspořádání na dvou prvcích. Dostáváme tak relace tvaru {[x,x],[x,y],[y,y]}, kde .

Chceme (lineárně) uspořádat tři prvky. To už přenechám tobě, jen zmíním, že trojúhelník abc (mám tím na mysli relaci {[a,a],[a,b],[a,c],[b,b],[b,c],[c,c]}) je lineárním uspořádáním, ale trojúhelník acd ne.

Nakonec probrat uspořádání čtyř a pěti prvků.

Filoman napsal(a):

Chápu to dobře?

Jo.

ad acd -- např. to není tranzitivní (neobsahuje to [a,d]). Abych to trošku zobecnil, antisymetrie ti v uspořádání zabraňuje vzniku cyklů. Pokud je např. , tak z tranzitivity máme a z antisymetrie pak dostaneme . Tj. pokud relace obsahuje orientovaný cyklus, nejedná se o uspořádání.