Matematické Fórum

Kouří se mi v hlavě · 28. 10. 2012 20:46

Ahoj,

mohli byste prosím poradit?

Necht’ R a S jsou relace na konečné množině M a $id_{M}=\{(x,y)|x\in M\}$ je relace identity na M.
Jestliže R ° S = $id_{M}$ , pak R ° S = S ° R. Dokažte.

Rozhodněte, zda uvedená implikace platí i pokud je M nekonečná.

Nebrali jsme bohužel na gymplu důkazy, tak nevím, jak to dokázat. Jak to srozumitelně pak zapsat ?
Ani tedy pořádně nerozumím zadání... :(

Díky za cokoliv, uvítám i literaturu, jiné materiály.

kompik · 28. 10. 2012 21:43 — Editoval kompik (28. 10. 2012 21:45)

Neviem, ci to budem vediet dobre vysvetlit - dost by pomohlo kreslit obrazky. (Mozno sa to da dokazat aj nejako jednoduchsie, ako sa tu snazim vysvetlit.)

V prvom rade treba rozumiet tomu ako funguje skladanie relacii.

Je to podobne ako skladanie funkcii, ten obrazok na Wikipedii dava celkom nazornu predstavu - jednoducho sa pozeras, kam sa mozes z daneho bodu dostat po sipkach. Rozdiel medzi relaciami a funkciami je, ze pre funkcii ide z kazdeho bodu prave jedna sipka, pri relacii ich moze ist viac ale nemusi aj ziadna.

V tomto pripade ide o relacie na mnozine $M$ , co znamena $R\circ S=\{(x,y)\in M\times M; (\exists z) (x,z)\in S \land (z,y)\in R\}$ . (Dva prvky x, y su v zlozenej relacii ak sa cez nejake z viem dostat z x do z po "S-kovej" sipke a zo z do y po "R-kovej sipke").

V zadani mame, ze $R\circ S=id_M=\{(x,x); x\in M\}$ . (Myslim, ze tu mas preklep v tom, co si napisal.) Zname na to teda, ze vsetky dvojice tvaru $(x,x)$ su v zlozenej relacii teda pre kazde x musi existovat nejake z tak, ze $(x,z)\in S \land (z,x)\in R$ .
$(\forall x\in M)(\exists z\in M) (x,z)\in S \land (z,y)\in R$ .

Pre kazde $x\in M$ si oznacme ako $M_x$ mnozinu takych $z$ .
$M_x=\{z\in M; (x,z)\in S \land (z,x)\in R\}$ .
Zatial sme si vsimli, ze kazde $M_x$ je neprazdna mnozina, ma teda aspon jeden prvok.

Skusme sa este zamysliet nad tym, ci pre rozne prvky mozu mat tieto dve mnoziny neprazdny prienik.
Ak by platilo $z\in M_x\cap M_{x'}$ , tak mame $(x,z)\in S$ a sucasne $(z,x')\in R$ . Z toho vyplyva $(x,x')\in R\circ S$ . Lenze zlozena relacia je identita, cize neobsahuje ziadne ine dvojice ako dvojice, kde su obe suradnice rovnake. To teda znamena, ze $x=x'$ .

Prave sme teda ukazali
$M_x\cap M_{x'}\ne\emptyset$ $\Rightarrow$ $x=x'$ ,
inak povedane, pre rozne prvky $x$ a $x'$ su mnoziny $M_x$ a $M_{x'}$ disjunktne.

Mame teda system mnozin $M_x$ , je ich tolko, kolko je prvkov mnoziny $M$ , kazda je neprazdna. Cize z toho vidime, ze kazda takato mnozina musi byt jednoprvkova a spolu pokryju celu mnozinu $M$ . (Tu sme vyuzili, ze mnozina je konecna.)

Teda aj obratene, kazde $z\in M$ sa dostane prave do jednej takej mnoziny; inak povedane, pre kazde $z\in M$ existuje prave jedno $x$ take ze $z\in M_x$ .
Mame teda: $(\forall z\in M)(\exists x\in M)(z,x)\in R \land (x,z)\in S$
To znamena, ze $(z,z)\in S\circ R$ . Vidime teda, ze $id_M\subseteq S\circ R$ .

Ak by do $S\circ R$ patrila nejaka dvojica ineho tvaru, teda nejaka dvojica $(z',z'')$ taka, ze $z'\ne z''$ , znamenalo by to, ze existuje $x\in M$ take, ze:
$(z',x)\in R \land (x,z'')\in S.$
Pre $z'$ mame prave jedno $x'$ take, ze $z'\in M_{x'}$ . Podobne pre $z''$ mame prave jedno $x''$ take, ze $z''\in M_{x''}$ . Toto konkretne znamena:
$(x',z')\in S \land (z',x')\in R$ ;
$(x'',z'')\in S \land (z'',x'')\in R$ .
Kombinaciou tychto veci dostaneme $(x',x)\in R\circ S$ a $(x,z'')\in R\circ S$ ; co znamena $x'=x=x''$ .
Sucasne vieme, ze tieto dva prvky su rozne, $x'\ne x''$ . (Lebo pre kazde $z$ mame prave jedno $x$ .) Dostali sme spor.
Teda ine dvojice tam uz patrit nemozu.

Zaver: $S\circ R=id_M$ .

******

Pre nekonecne mnoziny to nemusi platit, staci zobrat $M=\mathbb Z$ a relacie $R=\{(x,x+1); x\in\mathbb Z\}$ a $S=\{(x+1,x); x\in\mathbb Z\}$ .

Kouří se mi v hlavě · 28. 10. 2012 22:35

↑ kompik:

Mockrát děkuji za tak vyčerpávající odpověď, zkusím si to ve své hlavě přeložit do lehce nematematického jazyka, snad to bude ok :)
Čímž zároveň nechávám prostor pro ostatní, kdyby to chtěli nějakým způsobem přetransformovat a dát jak tady kompikovi, tak i mě jiný pohled na věc :)

jinak skládání relací jsem pochopila tady na tomto příspěvku: http://forum.matweb.cz/viewtopic.php?id=5287 → velmi dobře vysvětleno!

Ještě jednou velké díky!

Pavel Brožek

↑ kompik:

U těch nekonečných množin, nemyslel jsi spíš $M=\mathbb N$ ? Zdá se mi, že pro $M=\mathbb Z$ složením relací dostaneme identitu v obou případech.

kompik · 29. 10. 2012 10:59 — Editoval kompik (29. 10. 2012 11:00)

Pavel Brožek napsal(a):
↑ kompik:

U těch nekonečných množin, nemyslel jsi spíš $M=\mathbb N$ ? Zdá se mi, že pro $M=\mathbb Z$ složením relací dostaneme identitu v obou případech.

Samozrejme, ze je to pravda. Takze druhy pokus, ked vezmem $M=\mathbb N$ a relacie
$S=\{(x,x+1); x\in\mathbb N\}$ a $R=\{(x+1,x); x\in\mathbb N\}$ , tak dostaneme:
$R\circ S=id_M$ (pre kazde x mame $(x,x+1)\in S$ a $(x+1,x)\in R$ ; t.j. x->x+1->x.
Ale v relacii $S\circ R$ nebude dvojica (0,0). (Do nuly sa nemam "ako dostat", nie je ziadne cislo x take, ze $(x,0)\in S$ .)

Dakujem za opravu!

Matematické Fórum

#1 28. 10. 2012 20:46

Relace: důkaz

#2 28. 10. 2012 21:43 — Editoval kompik (28. 10. 2012 21:45)

Re: Relace: důkaz

#3 28. 10. 2012 22:35

Re: Relace: důkaz

#4 29. 10. 2012 01:17 — Editoval Pavel Brožek (29. 10. 2012 01:18)

Re: Relace: důkaz

#5 29. 10. 2012 10:59 — Editoval kompik (29. 10. 2012 11:00)

Re: Relace: důkaz

Pavel Brožek napsal(a):

Zápatí