Matematické Fórum

pizet · 06. 04. 2011 16:46 — Editoval pizet (06. 04. 2011 16:48)

Ahoj, potreboval by som poradiť ako na tieto úlohy: (presne citujem)

1) Dokážte, že pre ľubovoľnú reláciu R na nejakej množine X je relácia

$T = R \cup R\circ R\cup R\circ R\circ R\cup\dots$ (zjednotenie všetkých mnohonásobných zložení R) tranzitivná.

2) Dokážte, pre ľubovoľnú množinu X je vzťah "byť izomorfný" ekvivalencia na množine všetkých relácií na X.

Ďakujem.

Príspevok č. 300!!!

OiBobik

↑ pizet:

1)
Zkus si jenom nakreslit, jak na základě nějaké relace R vypadá taková relace T na nějaké diskrétní množině, odtud už určitě zjistíš, jak postupovat při dokazování. ; ))

2)
To je důkaz přímo z definice - stačí vědět, že ekvivalence = tranzitivní & reflexivní & symetrická, dále jak je definován isomorfismus a formálně to přepsat - tedy ověřit tyto tři vlastnosti relace "být isomorfní". ; ))

pizet · 06. 04. 2011 20:26

↑ OiBobik: Dík moc, na druhé som prišiel už. Nad 1) ešte premýšľam.

OiBobik

↑ pizet:

supr. ; ))

k tomu prvnímu tedy hint (teda spíš polohint, je to spíš něco jako "správné položení otázky"):
tranzitivita říká:
$xTy \wedge yTz \Rightarrow xTz$

tak vezmi prostě takové x,y,z - libovolné takové, že xTy, yTz. Dobré je uvážit, že tyto dvojice se do relace T dostaly při několikanásobného (řekněme n-násobného a m-násobného) složení relace R. Teď by bylo potřeba na základě toho nějak ukázat, že při nějakém (k-násobném) složení relace se nutně musela do T dostat i dvojice (x,z).

Pozn: Mohlo by se hodit, že skládání relací je asociativní, tedy např. $(R \circ R) \circ (R \circ R)=(((R \circ R) \circ R) \circ R)$ ; ))

pizet · 07. 04. 2011 17:38

↑ OiBobik: Ale neviem si to trocha ešte predstaviť. Rozumiem (polo)hintu ale čo keď napr. množina X = {1,2,3}, R = {(1,2)}. Nebude potom T = {(1,2)} a netranzitivné? Alebo som niečo zle pochopil?

OiBobik

↑ pizet:

Jednoprvková relace (tedy relace, ve které je jen jedna dvojice, tedy tebou uvažovaný případ) je vždy tranzitivní

Následuje skrytá chyba:

Autor skryl část textu. Zobrazit/skrýt!

konec chyby

Jinak řečeno, aby relace nebyla tranzitivní, musí platit

$\exists x,y,z \in X \text{ (množina, na níž uvažujeme relaci)}: (x,y) \in T \wedge (y,z) \in T \wedge (x,z) \not\in T$

Což v jednoprvkové relaci triviálně nemůže nastat.

pizet · 07. 04. 2011 18:14

↑ OiBobik:

Jáj. Idem na to. (:

Mimochodom ešte ke tej druhej. Pre istotu len stručne spíšem svoju myšlienku (nematematické vyjadrenie si nevšímaj).

Keď chceme dkázať, že dve relácie R, S sú izomorfné, musíme (podľa definície) nájsť bijekciu $f:X\rightarrow X$ , takú, že pre každé $x,y\in X: xRy \wedge f(x)Sf(y)$ .

Na to, aby som overil reflexivitu som som musel ukázať, že každá relácia je isomorfná sama so sebou, tak som definoval funkciu $f$ s predpisom $f(x) = x$ .

Aby som overil symetrickosť, som musel ukázat, že ak relácia R je izomorfná s reláciou S, tak aj relácia S je isomorfná s reláciou R. Definofal som fciu g, tak, aby platilo $xRy, f(x)Sf(y), g(f(x))Rg(f(y))$ . Teda g(f(x)) = x a g(f(y)) = y. Funkciu f nemusím definovať, lebo je prapoklad, že R,S sú izomorfné, teda, že takáto fcia existuje.

No a tranzitivitu, som dal tak, že ak R je izomorfná s S a S je izomorfná s T, tak R je izomorfná s T. Platí $xRy, f(x)Sf(y), g(f(x))Sg(f(y))$ . Musíme nájsť funkciu h, takú, že bude platiť xRy a súčasne h(x)Th(y). Je zrejmé, že $h = g\circ f$ . Funkcie f a g nemusíme definovať, lebo je prapoklad, že R,S a S,T sú izomorfné, teda, že takéto funkcie exitujú.

Dík moc za prekontrolovanie úvah.

OiBobik

Mrknu na to, teď jen OPRAVA: ta část

$(1,2) \in T \wedge (1,2) \in T \Rightarrow (1,2) \in T$

je nesmyslná, (resp. nesmyslná co se kontextu týče - vůbec to neodpovídá té podmínce pro tranzitivitu) to druhé platí. psal jsem to ve spěchu. zatím

OiBobik

↑ pizet:

Jo, super, to je přesně ono. Podle mě to je dokonce i přesně matematicky. Zkrátka pro reflexivitu stačí uvážit funkci identita, pro symetrii inverzní funkci, která u bijekce vždy existuje (to je předpoklad, který jsi explicitně nevyslovil, ale je nezbytný - musíš mít tu funkci g zkrátka dobře definovanou, což by nenastalo tehdy, kdyby funkce f nebyla prostá), pro tranzitivitu složení funkcí a z jejich vlastností vyplyne to, co potřebujem. ; ))

Pozn: Stejně tak jsou v tom skryty ještě předpoklady, jako že složení bijekcí je bijekce apod., dodávám tak pro úplnost.

pizet · 07. 04. 2011 21:40 — Editoval pizet (07. 04. 2011 21:48)

Jáj. No veď jasné. Základná myšlienka je, že ak je R trazitivná, tak určite aj T je. Ak R nie je trazitivná, tak z podmienky netrazitivnosti, $\exists x,y,z \in X \text{ (množina, na níž uvažujeme relaci)}: (x,y) \in R \wedge (y,z) \in R \wedge (x,z) \not\in R$ , je jasné, že (x,z) sa bude nachádzať v R o R a zjednostením dostaneme reláciu t trazitivnú. Príklad: X = {1,2}, R = {(1,2),(2,1)} netrazitívna, R o R = {(1,1),(2,2)}. T = {(1,1),(2,2),(1,2),(2,1)} a je tranzitívna.

Mimochodom dávam ti zaslúžené +. (:

OiBobik

↑ pizet:

Má to jednu vadu:
takovýmto "elementárním" složením odstraníš jednu "vadu" tranzitivity. Musíš ještě dodat, že po konečeném počtu kroků (tedy v několikerém složení R) odstraníš libovolnou takovou vadu.
Příklad:
$R=\{(1,2)(2,3)(3,4)(4,5)(5,6)\}$
$R \circ R = \{(1,3)(2,4)(3,5)(4,6)\}$
$R \cup (R \circ R)=\{(1,2)(1,3)(2,3)(2,4)(3,4)(3,5)(4,5)(4,6)(5,6)\}$

Lze nahlédnout, že T stále není tranzitivní (a např. ani po trojném složení a sjednocení ještě nebude).

(podstata problému spočívá v tom, že složením relací ti přibudou prvky, které se mohou dále podílet na "kazení tranzitivity". No a kdyby se toto dělo třeba do nekonečna - stačí uvážit to, co jsem naznačil na množině {1..6}, tedy relaci "je přímým předchůdcem", na množině přirozených čísel - tam už začíná člověk uvažovat o nekonečnech a jestli to je tranzitivní, když po každé této operaci mi zbude něco kazícího tranzitivitu, nebo ne... bezpečnější je o tom uvažovat asi spíš tak, jak píšu níže; tvůj postup by nicméně určitě fungoval na končených množinách)

Podle mě o něco jednodušeji zformulovatelný (tedy se i lépe myšlenkově kontroluje) důkaz: uvážím libovolnou dvojici prvků relace T tvaru $(x,y),(y,z)$ a budu se zkrátka snažit dokázat, že nutně $(x,z) \in T$ .
Dvojice $(x,y)$ se poprvé objevila řekněme v r-násobném složení relace R, dvojice $(y,z)$ řekněme v s-násobném složení R
(tedy r,s jsou minimální čísla taková, že $(x,y)\in R^r, (y,z) \in R^s$ , kde $R^i$ značí i-násobné složení relace R).
Pak stačí uvážit $R^{(r+s)}=(\text{díky asociativitě})=R^r \circ R^s$ , zřejmě tedy v $R^{(r+s)}$ do T přibyla dvojice (x,z), nebyla-li tam už dříve.