relacje binarne

[adner]

A jak rozpisać fakt, że \(\displaystyle{ \langle x;y \rangle \in (r \cap s)^{+}}\)? Brakuje mi tu jakiejś konkretnej definicji co to oznacza, w sensie że wiem co ten symbol "robi" ale jak to formalnie zapisać symbolami?

[adambak]

a.. w ten sposób.. ale zapis chyba nie jest dobry.. powinno być: \(\displaystyle{ \langle x;y \rangle \in \left( 1_{A} \cup \left( r\cap s\right) ^+\right)}\)

-- 6 lis 2011, o 22:23 --

o właśnie, tak samo jak adner mam problem jak to konkretniej rozpisać.. tej definicji którą mamy nie ma jak rozpisać żeby było widać, że to jest też po prawej stronie, chyba że o czymś nie wiem..

[adner]

No bo jak mam na przykład że \(\displaystyle{ x \in A-B}\) to wiem że to znaczy \(\displaystyle{ x \in A \wedge \neg x \in B}\), a tutaj?

[bemekw]

Przypomnę, że nasza definicja relacji domknięto przechodniej brzmi:

\(\displaystyle{ r^+ = \bigcap\{s \subseteq A \times S | s}\) jest przechodnia oraz \(\displaystyle{ r \subseteq s\}}\)

Jak więc widać definicja jest niezbyt korzystna do rozpisywania...

[adner]

Ja znam jeszcze jedną rzecz że, \(\displaystyle{ r^{*}=\bigcup r^{n}, n \in N}\), ale to też jest średnio pomocny fakt

[dmjeh]

to, ze \(\displaystyle{ <x,y> \in (r \cap s) ^{+}}\) mozna pociagnac dalej chyba tak, wiemy, ze to \(\displaystyle{ (r \cap s) ^{+}}\) zawiera \(\displaystyle{ (r \cap s)}\) i ewentualnie cos jeszcze ;p wiec mozna to znow rozpisac na dwa, gdy \(\displaystyle{ <x,y> \in (r \cap s)}\) i gdy nie nalezy. Jakbym cos zle kombinowal to prosze mnie poprawic mi tez sie przyda rada

[bemekw]

No dobra, rozpisuję powiedzme \(\displaystyle{ r^+}\) na \(\displaystyle{ (x,y) \in r \vee (x,y) \not\in r}\) Pierwszy przypadek łatwo dalej rozpisywać, jednak co zrobić, w tym drugim?

[Jan Kraszewski]

2) nie jest prawdziwe w ogólności. Dowód zawierania \(\displaystyle{ ( \subseteq)}\) robi się wprost z tego faktu:

\(\displaystyle{ r \subseteq s \Rightarrow r^* \subseteq s^*}\) - dowód wprost z def. przechodnio-zwartego domknięcia (najmniejsza relacja przechodnia i zwarta zawierająca daną relację).

Teraz dowód części 2):
\(\displaystyle{ ( \subseteq)}\) Ponieważ \(\displaystyle{ r\cap s \subseteq r}\) i \(\displaystyle{ r\cap s \subseteq s}\), więc \(\displaystyle{ (r\cap s)^* \subseteq r^*}\) i \(\displaystyle{ (r\cap s)^* \subseteq s^*}\), zatem \(\displaystyle{ (r\cap s)^* \subseteq r^*\cap s^*}\).

Zawierania przeciwnego nie ma, wystarczy wziąć relacje \(\displaystyle{ r=\{\langle 1,2\rangle, \langle 2,3\rangle, \langle 3,4\rangle\}}\) i \(\displaystyle{ s=\{\langle 1,2\rangle, \langle 1,3\rangle, \langle 1,4\rangle\}}\) na zbiorze \(\displaystyle{ \{1,2,3,4\}}\).

JK

[adambak]

1) \(\displaystyle{ (r^{*})^{-1}}\) = \(\displaystyle{ (r^{-1})^{*}}\)

tu na bank zawieranie.. ponadto pewnie skorzystać z tego, że przechodnio zwrotne domknięcie relacji \(\displaystyle{ r}\) zawiera tą relację + zwrotność + przechodniość, czyli jakoś pokazać to na elementach..

1) ale czy można jakoś w ten sposób, że bierzemy \(\displaystyle{ \langle x;y \rangle \in r}\), wtedy tymbardziej \(\displaystyle{ \langle x;y \rangle \in r^*}\), ale już \(\displaystyle{ \langle y;x \rangle \in \left( r^*\right) ^{-1}}\)
jak weźmiemy z drugiej strony (prawej) \(\displaystyle{ \langle x;y \rangle \in r}\) to wyjdzie na to samo bo w takim razie \(\displaystyle{ \langle y;x \rangle \in r^{-1}}\) i tymbardziej \(\displaystyle{ \langle y;x \rangle \in \left( r^{-1}\right)^*}\).. czyli tak jakby pokazaliśmy \(\displaystyle{ x \ r \ y \Rightarrow \left( x \ (r^{*})^{-1} \ y \Leftrightarrow x \ (r^{-1})^{*} \ y \right)}\)

2) dla zwrotności identycznie

3) dla przechodniości bierzemy \(\displaystyle{ \langle x;y \rangle, \langle y;z \rangle \in r}\) (no bo tylko tak bedzie ciekawie), wtedy \(\displaystyle{ \langle x;z \rangle \in r^*}\) i konsekwentnie \(\displaystyle{ \langle z;x \rangle \in \left( r^*\right)^{-1}}\)
z kolei z lewej strony: \(\displaystyle{ \langle x;y \rangle, \langle y;z \rangle \in r}\) co jest równoważne z tym, że \(\displaystyle{ \langle y;x \rangle, \langle z;y \rangle \in r^{-1}}\), z czego otrzymujemy \(\displaystyle{ \langle z;x \rangle \in \left( r^{-1}\right)^{*}}\)

czyli mamy te same pary jakby po obu stronach.. ale nie wiem czy ja potrzebnie się rozpisuję w ogóle, czy to nie jest wszystko.. hmm.. za słabe? np ta implikacja w 1).. czy to nam zapewnia, że WSZYSTKIE pary po lewej stronie są też po prawej i na odwrót?

[Jan Kraszewski]

Powiem uczciwie - nie chce mi się przegryzać przez wszystko, co napisałeś, ale na wyczucie to nie jest dobrze.

Jeżeli chcesz pokazać \(\displaystyle{ (r^*)^{-1}=\left( r^{-1}\right) ^*}\), to pokaż najpierw indukcyjnie, że dla każdego \(\displaystyle{ n\in\mathbb N}\) masz \(\displaystyle{ (r^n)^{-1}=\left( r^{-1}\right) ^n}\).

JK

[adambak]

a co oznacza zapis \(\displaystyle{ r^n}\), bo się z tym nie spotkałem? poza tym najpierw pokazać to znaczy że coś potem jeszcze trzeba będzie z tym robić?

[Jan Kraszewski]

\(\displaystyle{ r^n}\) to \(\displaystyle{ n}\)-krotne złożenie relacji \(\displaystyle{ r}\) ze sobą.

A potem korzystasz z tego:

Ja znam jeszcze jedną rzecz że, \(\displaystyle{ r^{+}=\bigcup r^{n}, n \in N}\), ale to też jest średnio pomocny fakt

JK

[adambak]

dla jedynki działa bo mamy po prostu \(\displaystyle{ r^{-1}=r^{-1}}\), załóżmy że dla \(\displaystyle{ n}\) działa.. cel: działa dla \(\displaystyle{ n+1}\), no to:

\(\displaystyle{ (r^{n+1})^{-1}=\left( r^{-1}\right) ^{n+1}}\)

\(\displaystyle{ (r^n \cdot r)^{-1}=\left( r^{-1}\right) ^{n}\cdot r^{-1}}\)

chociaż pewnie relacja odwrotna do złożenia to nie to samo co złożenie relacji odwrotnych.. a przynajmniej nic mi o tym nie wiadomo, ale może można złożyć obustronnie relacje z tą samą? czyli:

\(\displaystyle{ (r^{n})^{-1}=\left( r^{-1}\right) ^{n} \ \ \ | \cdot r^{-1}}\)

\(\displaystyle{ (r^{n})^{-1} \cdot r^{-1}=\left( r^{-1}\right) ^{n} \cdot r^{-1}}\)

\(\displaystyle{ (r^{n})^{-1} \cdot r^{-1}=\left( r^{-1}\right) ^{n+1}}\)

hmm.. nie wiem jakie stąd płyną wnioski..

[Jan Kraszewski]

1. Krok indukcyjny:

\(\displaystyle{ \langle x,y\rangle\in \left( r^{-1}\right) ^{n}\cdot r^{-1} \Leftrightarrow (\exists z)(\langle x,z\rangle\in \left( r^{-1}\right) ^{n}\land \langle z,y\rangle\in r^{-1}) \Leftrightarrow \\
\mbox{zał. ind.} \Leftrightarrow (\exists z)(\langle x,z\rangle\in \left( r^n\right) ^{-1}\land \langle z,y\rangle\in r^{-1}) \Leftrightarrow \\
\Leftrightarrow (\exists z)(\langle z,x\rangle\in r^n\land \langle y,z\rangle\in r) \Leftrightarrow \\
\Leftrightarrow (\exists z)(\langle y,z\rangle\in r\land\langle z,x\rangle\in r^n) \Leftrightarrow \\
\Leftrightarrow \langle y,x\rangle\in r\cdot r^n \Leftrightarrow \langle y,x\rangle\in r^{n+1} \Leftrightarrow \langle x,y\rangle\in \left( r^{n+1}\right) ^{-1}}\)

2. Zastosowanie

\(\displaystyle{ \left( r^{-1}\right)^+ =\bigcup_{n=1}^\infty \left( r^{-1}\right) ^{n}=\bigcup_{n=1}^\infty \left( r ^{n}\right)^{-1}=\\
=\mbox{ to trzeba udowodnić }= \left(\bigcup_{n=1}^\infty r ^{n}\right)^{-1}=\left( r^+\right)^{-1}}\)

Teraz wystarczy dodać przekątną i już (przekątna jest niewrażliwa na odwracanie relacji).

JK