Matematické Fórum

Dobře díky moc, ale stejně si to ještě neumim úplně představit, budu to zkoušet. Tady je několik příkladů, které mi radí učebnice:

1) Kolik je symetrických relací nad n-prvkovou množinou?
     - no tak symetrické relace to je zkrátka ta "úhlopříčka", ne? Takže kolik jich tam bude? 2^n?

2) Kolik je antisymetrických relací nad n-prvkovou množinou?
     - antisymetrických bude ten zbytek? Tedy 2^(n^2 - n)

3) Nech? R je relace nad konečnou množinou X. Dokažte, že existují dvě různá
přirozená čísla r a s taková, že R^r = R^s. Značením R^k rozumíme k-násobné
složení relace sama se sebou.
     - chápu, že ten vztah v některých relacích platit může, ale jak ho dokážu... Měl bych vyjít z definice tranzitivity?

4) Najděte příklad relace R nad nějakou množinou X, kde pro každé n ∈ N
platí:  R^n "se nerovná"  R^(n+1 )
     - například relace na N "jedno číslo dělí druhé", ano?

5) Nech? R je relace. Dokažte následující ekvivalenci:
R je tranzitivní ⇐⇒ R ◦ R ⊆ R
     - tady tomu moc nerozumim, tak tedy dobře, zleva doprava: když je R tranzitivní, potom je její složenina sama se sebou stejně velká či menší než původní nesloženina R. To bych dokazoval z definice tranzitivity. Zprava doleva: Když je složenina relace samy se sebou menší nebo rovná původní nesloženině, pak je R tranzitivní, hmm, tady jsem asi mimo.

6) Nech? R a S jsou nějaké dvě relace ekvivalence na množině X. Rozhodněte,
zda následující množiny nutně jsou či nejsou relace ekvivalence na X:
     - R∪S - řekl bych, že ne
     - R ∩ S - ano, zde přece zůstávají dvojice společné oběma množinám, mělo by to platit
     - R \ S - ne, relace R může přijít o některé dvojice takže pak nemusí platit tranzitivita
     - R ◦ S - ano, ale to jen tipuji

Řešil jsem správně? Díky moc.
     -

ad 1., 2.: Zřejmě mám problém s vyjádřením počtu možností: Tak tedy. Představím si onu tabulku. Potom reflexiní relace jsou všechny ty, které jsou na úhlopříčce. Těch by mělo být 2^n, ne? Dále symetrické: Když z tabulky vyberu jeden, musím vybrat i jeho protějšek. Tak např. když (2,4) tak potom taky (4,2). Patří tam ale také třeba (1,1). Tzn. když si do tabulky nakreslím všechny, tabulka bude celá zaplněná. Tedy 2^(n^2).
Nyní antisymetrické. Tady to může dopadnout tak, že bude vyplněné vše pod/nad úhlopříčkou (případně nějak promícháno). Takže tedy. Dvojka je základ (každá relace tam být může či nikoliv). No a na co ji umocním? Tak když je to polovina pod úhlopříčkou tak nejdřív vyberu všechny (n^2), to podělím dvěma a odečtu od toho polovinu úhlopříčky. Tedy: 2^((n^2 - n):2).

Nějak se nedokážu představit složení relace samy se sebou. Mám relaci (=,N). Dostávám (1,1), (2,2), (3,3) ... Když tuhle relaci složím samu se sebou, co získám?

Pro ucely skladani je dobre predstavovat si relace jako puntiky a sipky. Skladani relaci potom probiha tak jako na tomto obrazku:



R a S jou dve relace na mnozine X = {1, 2, 3, 4, 5}, puntiky cislujeme od shora dolu. Treti relace je jejich slozenim. Pokud si to clovek prdstavi takto, je snadne relace skladat, nezavisle na tom, jestliskladam dve ruzne nebo dve stejne relace.

není mi jasné, jak se pracuje s relací:  R \ S, kde R a S jsou libovolne relace ekvivalence na mnozine X

Pokud mam relaci na mnozine s jednoprvkovymi prvky, tak je to jasne. U teto relace se pracuje s usporadanymi dvojicemi? Nebo jeste nejak jinak?

Pokud mam napriklad relaci "ostre mensi" ("<") na množině celých čísel, x<y (a zaroven obe lezi v Z), tak jsou v relaci, tedy: xRy  ... tim chci rict, ze tady vidim, s cim pracuju: vezmu jeden prvek a porovnam ho s jinym.. U R\S mi to uz jasne neni..

"R\S je asi rozdil dvou ekvivalenci ne? Ekvivalence uz to nebude, nebot nebude reflexivni. "

je to rozdil dvou ekvivalenci, ale stejne mi poad neni jasne, jak muzu odecitat nejake dve ekvivalence, muzes to zapsat nejak matematicky?

"Uz z tvych predchozich dotazu je videt, ze bys mel trosku zapracovat ne presnem vyjadrovani problemu."

to bych zrejme mel..

Tak. Spočítal jsem si pár příkladů, snad je mi to jasnější. Ovšem ještě mám něco - částečné uspořádání: R,S jsou relace část. uspořádání. Jejich průnik bude taktéž částečně uspořádaný, rozdíl nebude (není antisymetrický) a složení taky ne (není antisymetrické a snad ani tranzitivní). Je to tak?

A co teprv tohle:
R je množina všech relací nad množinou X. Def. relaci Q nad R (tedy relaci mezi samotnými relacemi): Pro R, S prvky R definujeme R v relaci Q s S právě tehdy, když existuje bijekce f : X --> X splňující pro každé x, y z  X toto: (x, y) jsou prvky R právě tehdy, když (f(x), f(y)) jsou prvky S. Dokažte, že Q je ekvivalence.

Mohl by mi někdo prosím pomoct s postupem, tedy hlavně pochopit relace a hlavně jejich zobrazení? Je to zkoušková otázka a já s tím asi určitě nehnu.
Př. Jsou dány množiny A = |1,2,4| B=|3,6,7|
a relace
ς 1 |(1,6) (1,7) (4,7)|
ς 2 |(1,3) (2,6) (4,7)|
ς 3 |(2,3) (2,7)|
ς 4 |(2,6) (4,6)|
ς 5 |(2,3) (4,3) (4,7)|

- jak se zjiš?uje relace která je zobrazením, zobrazení množiny A na množinu B a prosté zobrazení a jednorázové zobrazení?

Moc děkuju předem za postup, výklad pro lepší pochopení