Matematické Fórum

Blujacker · 25. 10. 2011 00:03

Zítra píšu písemku na relace a narazil jsem na jednu nejasnost.

Mám příklad: Mějme množinu $A=\{1,2,3,4\}$ a relaci $R \subseteq A\times A$ , $R=\{(1,1), (1,2), (2,3), (3,4), (4,3), 2,1)\}$ . Spočítejte všechny mocniny této relace nutné pro zisk jejího tranzitivního uzávěru

Já bych to řešil tak, že bych postupně doplnoval prvky do relace abych splnil pravidlo tranzitivity: $(a, b) \in R \wedge (b, c) \in R \implies (a, c) \in R$ , jenomže tady se to chce nějakým umocňováním relace a vůbec nevím, co si pod tím představit.

Děkuji za každou radu

Rumburak

↑ Blujacker:
Transitivita relace R se dá popsat podmínkou $R\circ R \subseteq R$ , kde $\circ$ je operace skládání relací. Proto ty "mocniny"
( $R\circ R$ můžeme zapsat jako $R^2$ ).

OiBobik · 25. 10. 2011 16:12

↑ Blujacker:

Umocňování relace je zhruba toto (definováno induktivně):

$R^1\overset{\text{def}}{=}& R \\ R^n\overset{\text{def}}{=}& \{(x,z)| \exists y \in A : ((x,y)\in R^{n-1}) \wedge ((y,z) \in R) \}$

Neboli: R^2 je množina všech možných "složení" dvou navazujících "šipek" relace (načrtni si to na konečné relaci a snad to bude jasné), R^3 je to stejné, akorát beru vždy prvně šipku z R^2 a k ní šipku z R atd. Nebo si lze libovolnou šipku z R^3 také představit jako tři po sobě navazující šipky (toto s šipkami těžce neformálně, jen tak pro představu).

Blujacker · 26. 10. 2011 13:14

Děkuji všem :-)

Matematické Fórum

#1 25. 10. 2011 00:03

Tranzitivní uzávěr

#2 25. 10. 2011 16:10 — Editoval Rumburak (25. 10. 2011 16:14)

Re: Tranzitivní uzávěr

#3 25. 10. 2011 16:12

Re: Tranzitivní uzávěr

#4 26. 10. 2011 13:14

Re: Tranzitivní uzávěr

Zápatí