Matematické Fórum

Sherlock · 21. 11. 2015 20:48

Zdravím, složenou relaci mám definovanou jako:

$R\circ S=\{(x,y)|\exists z:(x,z)\in S\wedge (z,y)\in R\}$
(tedy držím se toho značení, které se používá u složených zobrazení)

Pokud jsou $R$ a $S$ tranzitivní, je jejich složení tranzitivní?

formálně:
$xR\circ Sy\wedge yR\circ Sz\Rightarrow xR\circ Sz$

neboli:
$(x,y)\in R\circ S\wedge (y,z)\in R\circ S\Rightarrow (x,z)\in R\circ S$

Po rozepsání dostanu dvojici podmínek:
$\exists z_{1}:(a,z_{1})\in S\wedge (z_{1},b)\in R$
$\exists z_{2}:(b,z_{2})\in S\wedge (z_{2},c)\in R$

z nich by mělo vyplývat:
$\exists z_{3}:(a,z_{3})\in S\wedge (z_{3},c)\in R$

Což nevyplývá... jak to ale poznám? :) Nikde jsem zatím nevyužil faktu, že $R,S$ jsou tranzitivní a ani nevím jak toho využít

Sherlock · 21. 11. 2015 22:20

↑ byk7:

Ano to vím :) Mě spíš zajímalo - jde to nějak vypozorovat z těch formálních definic? Nebo musím metodou pokus omyl hledat protipříklady?

byk7 · 21. 11. 2015 23:47

A co toto, z $(z_{1},b)\in R\wedge (b,z_{2})\in S\Rightarrow(z_1,z_2)\in S\circ R$ , takže protipříklad budu konstruovat tak, že $(z_1,z_2)\not\in S\circ R$ .

sugyman · 22. 11. 2015 00:51

Trénujeme na čtvrteční písemečku? :D Osobně hledám protipříklady tak, že si to kreslím

Sherlock

↑ sugyman:

tak nějak :/

no já si to kreslím, akorát v tomto to nějak nevidím

↑ byk7:
EDIT: tomu nějak nerozumím, $R\circ S=\{(b,c),(a,c)\}$ tranzitivní je, ne?

sugyman

Jo byk7 blbě radí. Já bych myšlenkově postupoval takhle. Tak aby nebyla $R \circ S$ tranzitivní, tak by musela obsahovat třeba $(1,2)$ a $(2,3)$ ale ne $(1,3)$ , tak nechť $(1,2),(2,3) \in R \circ S$ . Ted stačí doplnit $R$ a $S$ a budeme vynakládat veškeré úsilí, aby nám tam $(1,3)$ nevyskočilo.
Takže doplnme $(1,4) \in S$ , $(4,2)\in R$ - tím si zajístíme, že $(1,2) \in R \circ S$ . A taky $(2,5) \in S$ , $(5,3) \in R$ - tím máme $(2,3) \in R \circ S$ . Je možný, že v $S$ a $R$ budou i další prvky ale zkusme si troufnout tam dát zatím jen ty naše: $R=\{(4,2),(5,3)\}, S=\{(1,4),(2,5)\}$ , $R\circ S={(1,2),(2,3)}$ Vidíme, že $(1,3)$ není v $R \circ S$ a zkontrolujme že $R$ i $S$ jsou tranzitivní.... Hurá.

Je to takový zkoušení, ale aspon trochu systematický.