Matematické Fórum

philber · 17. 01. 2009 16:06

mohli byste mi někdo poradit ak na důkaz toho, že relace R na množině X je tranzitivní, právě když platí $http://www.sitmo.com/gg/latex/latex2png.2.php?z=100&eq=R\circ%20R%20\subseteq%20R$ vůbec si s tím nevím rady děkuju moc

Kondr · 17. 01. 2009 23:35

Zkus si přečíst http://www.proofwiki.org/wiki/Transitiv … _with_Self
a pokud se tím neprolouskáš, tak se ozvi.

philber · 18. 01. 2009 13:18

Kondr děkuju moc to je přesně to co sem hledal,.. já sem měl akorát tu první část že sem předpokládal že je tranzitivní a nebylo mi to uznáno, už vím proč

bobik · 22. 01. 2009 16:13

ahojte mam podobny problem ako uviedol philber

mohli by ste mi niekto poradiť ako na dôkaz toho, že relácia R na množine X je relácia ekvivalenice <=> $(R\circ R^{-1}) \cup id_x = R$

Kondr · 23. 01. 2009 00:45

Dokázat že ekvivalence to splňuje je celkem lehké. Protože je symetrická, rovná se své inverzi. R o R^(-1) je proto rovno R o R. To je ale pro ekvivalenci rovno R (jedna inkluze viz odkaz, druhá plyne z toho, že id je podmožina R, takže R o R je podmnožina R o id = R). Po sjednocení s identitou dostaneme opět R. Rovnost platí.

Teď předpokládejme, že to platí a ukažme, že R je ekvivalence.
Složení R a inverze je určitě symetrické, viz
http://www.proofwiki.org/wiki/Composite … _Symmetric
po sjednocení s identitou je to reflexivní. Proto i pravá strana rovnice (tj. R) je symetrická a reflexivní. Protože R je symetrická a reflexivní,
R o R^(-1) je rovno R o R, navíc sjednocení R o R s identitou je stále R o R (protože R obsahuje celou identitu R o R také). Tím dostáváme opět rovnost, kterou psal CL, a z ní i kýženou tranzitivitu.

bobik · 23. 01. 2009 13:46 — Editoval bobik (23. 01. 2009 13:46)

↑ Kondr:zdravim

tak ak som to pochopil spravne je to nejak takto?
relácia R na množine X je relácia ekvivalenice <=> $(R\circ R^{-1}) \cup id_x = R$

"=>"
R je relacia ekvivalencie => je Symetrická $(1): R^{-1}\subseteq R$ , Reflexívna na X $(2): id_x \subseteq R$ , Tranzitívna $(3): R \circ R \subseteq R$ ,
potom z (1) $(R^{-1})^{-1} \subseteq R^{-1} => R \subseteq R^{-1} => R^{-1} = R$

$R \circ R^{-1} =_{(1)} R \circ R \subseteq_{(3)} R = R \circ id_x =_{(2)} R$
a teda $(R \circ R^{-1}) \cup id_x = R$

rovnosť teda platí je to správne?

"<="
z definície inverznej relácie platí $(4): (a,b) \in R => (b,a) \in R^{-1}$

$(a,b) \in R \circ R^{-1} => \exists z \in X (a,x) \in R & (x,b) \in R^{-1} =>_{(4)} \exists z \in X (x,a) \in R^{-1} & (b,x) \in R => (b,a) \in R \circ R^{-1}$
teda
$(5): (a,b) \in R \circ R^{-1} => (b,a) \in R \circ R^{-1}$

potom
$R \circ R^{-1}$ je symetrické a $R \circ R^{-1} \cup id_x$ je to reflexívne, lebo $R \circ R^{-1} \subseteq R$ potom $R \circ R^{-1} \cup id_x => id_x \subseteq R$
z toho ale potom dostávame, že aj R je reflexívna a symetrická a teda $R \circ R^{-1} = R \circ R$
a $(R \circ R^{-1}) \cup id_x = R$ teda dostávame aj tretiu vlastnoť a to tranzitivitu

je to dobre?