Domknięcia relacji- zadania

[Jakub Gurak]

Udało mi się odpowiedzieć na wszystkie pytania, które w czwartek sobie postawiłem w związku pewnym zagadnieniem. Odpowiedziałem też na jeszcze jedno pytanie, które zresztą było bardzo dobrą pomocą, aby w sposób natychmiastowy odpowiedzieć na dwa z tych pytań. Przedstawię tu rozwiązania tych wszystkich zagadnień.

Niech \(\displaystyle{ X}\) będzie zbiorem. A \(\displaystyle{ R}\) dowolną relacją w zbiorze \(\displaystyle{ X}\). Oznaczmy przez \(\displaystyle{ R ^{ \alpha }}\) zwrotne domknięcie relacji \(\displaystyle{ R}\), przez \(\displaystyle{ R ^{ \beta }}\) symetryczne domknięcie relacji \(\displaystyle{ R}\), przez \(\displaystyle{ R ^{\gamma}}\) przechodnie domknięcie relacji \(\displaystyle{ R}\).

Niech \(\displaystyle{ X}\) będzie zbiorem, odpowiemy na pytania, czy dla dowolnej relacji \(\displaystyle{ R}\) w tym zbiorze:

0. \(\displaystyle{ \left( R ^{ \alpha }\right) ^{ \beta }=\left( R ^{ \beta } \right) ^{ \alpha }? }\)

1. \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma} }\) jest relacją równoważności

2. \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \beta } \right) ^{ \alpha } }\) jest relacją równoważności

Czy zawsze \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma} =\left( \left( R ^{ \gamma } \right) ^{ \beta } \right) ^{ \alpha } }\)

3. \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \alpha } \right) ^{\gamma} }\) jest relacją równoważności ?

4. \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \alpha } \right) ^{ \beta } }\) jest relacją równoważności ?

Czy zawsze \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \alpha } \right) ^{\gamma} =\left( \left( R ^{ \gamma } \right) ^{ \alpha } \right) ^{ \beta } }\) ?

5. \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \gamma } \right) ^{ \alpha } }\) jest relacją równoważności ?

6. \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \gamma } \right) ^{ \beta } }\) jest relacją równoważności ?

Czy zawsze \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \gamma } \right) ^{ \alpha } =\left( \left( R ^{ \alpha } \right) ^{ \gamma } \right) ^{ \beta } }\) ?

Przypomnijmy najpierw, jak wyglądają konstrukcje tych domknięć relacji, co prawda z samej logiki wynika, że w danym zbiorze każda relacja ma dokładnie jedno przechodnie domknięcie, każda relacja ma dokładnie jedno symetryczne domknięcie i ma dokładnie jedno zwrotne domknięcie. Ale będziemy potrzebowali odnieść się do ich konstrukcji. Przypomnijmy zatem:

Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R}\) relacją w nim, wtedy:

1.Zwrotnym domknięciem relacji \(\displaystyle{ R}\) jest \(\displaystyle{ R \cup I _{X}}\) (\(\displaystyle{ I _X}\) oznacza identyczność na zbiorze \(\displaystyle{ X}\)). Łatwo to sprawdzić.

2. Symetrycznym domknięciem relacji \(\displaystyle{ R}\) jest \(\displaystyle{ R \cup R ^{-1}.}\)

Dowód:

Oczywiście a)\(\displaystyle{ R \subset R \cup R ^{-1} .}\)
b) \(\displaystyle{ \left( R \cup R ^{-1}\right) ^{-1} =R ^{-1} \cup \left( R ^{-1}\right) ^{-1}=R ^{-1} \cup R=R\cup R ^{-1}}\), a zatem \(\displaystyle{ R \cup R ^{-1}=\left( R \cup R ^{-1}\right) ^{-1} }\), więc relacja \(\displaystyle{ R \cup R ^{-1}}\) jest symetryczna.
c) Niech \(\displaystyle{ T \subset X \times X}\) będzie relacją symetryczną, taką, że \(\displaystyle{ T\supset R}\). Pokażemy, że \(\displaystyle{ T\supset R \cup R ^{-1}.}\) Ponieważ \(\displaystyle{ T}\) jest symetryczna, więc \(\displaystyle{ T\supset T^{-1}}\). Ponieważ \(\displaystyle{ T\supset R}\), więc również \(\displaystyle{ T^{-1}\supset R^{-1}}\), ponieważ \(\displaystyle{ T\supset T^{-1}\supset R^{-1},}\) więc \(\displaystyle{ T\supset R^{-1}}\), mamy też \(\displaystyle{ T\supset R}\), więc również \(\displaystyle{ R \cup R ^{-1}\subset T.}\)

A więc \(\displaystyle{ R \cup R ^{-1}}\) jest domknięciem symetrycznym relacji \(\displaystyle{ R}\) (domknięcie jest tylko jedno).

3. Przechodnie domknięcie nie jest już takie proste. Aby je wprowadzić oznaczmy dla \(\displaystyle{ n\in\NN _{+}}\), przez \(\displaystyle{ R ^{n}}\) oznaczmy \(\displaystyle{ n}\)-krotne złożenie relacji \(\displaystyle{ R}\) z sobą, tzn. \(\displaystyle{ R ^{1}=R, R ^{n+1}=R ^{n}\circ R}\). Rozważmy rodzinę relacji:

\(\displaystyle{ \mathcal{R}=\left\{ S \subset X \times X\Bigl| \ \ \bigvee\limits_{n\in\NN}\left( n \neq 0 \wedge R ^{n}=S \right) \right\}. }\)

Jest to rodzina wszystkich wielokrotnych skończonych złożeń relacji \(\displaystyle{ R}\) z sobą. Wtedy \(\displaystyle{ \bigcup\mathcal{R}= \bigcup_{n\in\NN _{+} } R ^{n} }\) jest przechodnim domknięciem relacji \(\displaystyle{ R}\). Jak ktoś bardzo chcę to napiszę dowód. Przechodzimy do rozwiązań.

Niech \(\displaystyle{ X}\) będzie zbiorem.

LEMAT 0:    

Dla dowolnej relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), mamy \(\displaystyle{ \left( R ^{ \alpha }\right) ^{ \beta } =\left( R ^{ \beta} \right) ^{ \alpha}. }\).

Dowód: Wiemy, że relacja odwrotna do sumy dwóch relacji jest sumą relacji odwrotnych, oraz łatwo się przekonać, że \(\displaystyle{ \left( I _{X} \right)^{-1}=I _{X} }\), w związku z czym:

\(\displaystyle{ \left( R ^{ \alpha }\right) ^{ \beta }=\left( R \cup I _{X} \right)^{\beta} = \left( R \cup I _{X} \right) \cup \left( R \cup I _{X} \right) ^{-1}= \left( R \cup I _{X} \right) \cup \left( R ^{-1} \cup I _{X} ^{-1} \right) = R \cup R ^{-1} \cup I _{X} \cup I _{X}=R \cup R ^{-1} \cup I_{X} .}\)

Tymczasem

\(\displaystyle{ \left( R ^{ \beta }\right) ^{ \alpha } =\left( R \cup R ^{-1}\right) ^{ \alpha } = R \cup R ^{-1} \cup I _{X} .}\) A więc \(\displaystyle{ \left( R ^{ \beta } \right) ^{ \alpha } = \left( R ^{ \alpha }\right) ^{ \beta }. \square }\)

Nim udowodnię następny lemat przypomnę bardzo prosty fakt, że jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ \mathbb{B}}\) dowolną rodziną relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to \(\displaystyle{ \left( \bigcup \mathbb{B}\right) ^{-1}= \bigcup_{R\in\mathbb{B}} R ^{-1}- }\) relacją odwrotną do sumy rodziny relacji \(\displaystyle{ \mathbb{B}}\) jest suma relacji odwrotnych. To można bardzo łatwo sprawdzić. Również jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R}\) relacją w nim, a \(\displaystyle{ R ^{n}}\) dla \(\displaystyle{ n\in\NN _{+}}\) oznacza, jak wyżej, \(\displaystyle{ n}\)-krotne złożenie relacji \(\displaystyle{ R}\) z sobą, to można łatwo pokazać indukcyjnie \(\displaystyle{ \left( R ^{n} \right) ^{-1}= \left( R^{-1} \right)^{n}}\) (korzystając z prawa relacji \(\displaystyle{ \left( R\circ S \right) ^{-1}=S ^{-1} \circ R ^{-1} }\) ) Przypomnijmy również, że relacja w danym zbiorze jest symetryczna, dokładnie wtedy, gdy jest równa swojej relacji odwrotnej. W związku z czym udowodnimy kolejny lemat:

LEMAT 1:    

Wykażemy, że przechodnie domknięcie relacji symetrycznej jest zawsze symetryczne. Niech \(\displaystyle{ R}\) będzie relacją symetryczną w zbiorze \(\displaystyle{ X}\). Wtedy \(\displaystyle{ R=R ^{-1}}\). Wtedy przechodnie domknięcie relacji \(\displaystyle{ R}\) jest równe \(\displaystyle{ \bigcup_{n \in \NN _{+} } R ^{n}}\), wtedy na mocy przytoczonej równości odnośnie relacji odwrotnej do sumy rodziny relacji, otrzymujemy

\(\displaystyle{ \left( \bigcup_{n \in \NN _{+} } R ^{n}\right)^{-1}= \bigcup_{n\in\NN _{+} }\left( R ^{n} \right) ^{-1}= \bigcup_{n\in\NN _{+}} \left( R^{-1} \right)^{n}=\bigcup_{n \in \NN _{+} } R ^{n}, }\) gdyż \(\displaystyle{ R}\) jest symetryczna, więc \(\displaystyle{ R ^{-1}=R}\). A więc \(\displaystyle{ \left( \bigcup_{n \in \NN _{+} } R ^{n}\right)^{-1}= =\bigcup_{n \in \NN _{+} } R ^{n}, }\) a więc \(\displaystyle{ \bigcup_{n \in \NN _{+} } R ^{n}}\) jest symetryczna. \(\displaystyle{ \square}\)

Kolejny lemat:

LEMAT 2:    

Zwrotne domkniecie relacji symetrycznej jest zawsze relacją symetryczną.

Dowód:

Niech \(\displaystyle{ R}\) będzie relacją symetryczną w zbiorze \(\displaystyle{ X}\). Wtedy \(\displaystyle{ R=R-1}\). Pokażemy, że \(\displaystyle{ \left( R \cup I_X\right) }\)jest relacją symetryczną. Niewątpliwie mamy:

\(\displaystyle{ \left( R \cup I_X\right) ^{-1}=R ^{-1} \cup \left( I_X\right) ^{-1}=R \cup I_X}\), więc \(\displaystyle{ R \cup I_X=\left( R \cup I_X\right) ^{-1}}\), a więc relacja \(\displaystyle{ R \cup I_X}\) jest symetryczna\(\displaystyle{ .\square}\)

Nim przejdziemy dalej przypomnijmy, że relacja \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) jest przechodnia, dokładnie wtedy, gdy \(\displaystyle{ R\circ R \subset R.}\) Odnotujmy jeszcze prawa dla relacji \(\displaystyle{ R,S,T}\) pomiędzy zbiorami

\(\displaystyle{ R\circ(S \cup T)=R\circ S \cup R\circ T.}\)
\(\displaystyle{ \left( R \cup S\right) \circ T=R\circ T \cup S\circ T.}\)
\(\displaystyle{ R\circ I_X=R=I_X\circ R}\) ( jeśli relacja działa z \(\displaystyle{ X}\) do \(\displaystyle{ X}\)).

Czas zatem na ostatni lemat:

LEMAT 3:    

Zwrotne domknięcie relacji przechodniej jest zawsze relacją przechodnią.

Dowód:

Niech \(\displaystyle{ R}\) będzie relacją przechodnią w zbiorze \(\displaystyle{ X}\). Wtedy \(\displaystyle{ R\circ R \subset R}\). Wykażemy, że jej zwrotne domknięcie, czyli \(\displaystyle{ R \cup I_X}\) jest relacją przechodnią. W tym celu wykażemy, że \(\displaystyle{ \left( R \cup I_X\right) \circ \left( R \cup I_X\right) \subset R \cup I_X.}\) Na mocy przechodniości \(\displaystyle{ R}\), na podstawie rozdzielności złożenia względem sumy dwóch relacji, otrzymujemy:

\(\displaystyle{ \left( R \cup I_X\right) \circ \left( R \cup I_X\right) =\left[ R\circ\left( R \cup I_X\right) \right] \cup \left[ I_X\circ\left( R \cup I_X\right)\right] =\left( R\circ R\right) \cup \left( R\circ I_X\right) \cup \left( I_X\circ R\right) \cup\left( I_X\circ I_X\right) =\left( R\circ R\right) \cup R \cup R \cup I_X .}\) ponieważ \(\displaystyle{ R}\) jest przechodnia, czyli \(\displaystyle{ R\circ R \subset R}\), więc to jest równe \(\displaystyle{ R \cup I_X}\), czyli \(\displaystyle{ \left( R \cup I_X\right) \circ \left( R \cup I_X\right) =R \cup I_X,}\) więc w szczególności \(\displaystyle{ \left( R \cup I_X\right) \circ \left( R \cup I_X\right) \subset R \cup I_X. \square }\)

Odpowiemy teraz na zadane przeze mnie pytania.

0. Tak, udowodniłem to w lemacie 0.

1. Niech \(\displaystyle{ R}\) będzie relacją w zbiorze \(\displaystyle{ X}\). Wtedy relacja \(\displaystyle{ R ^{\alpha}}\) jako zwrotne domknięcie jest zwrotna, równoważnie \(\displaystyle{ R ^{ \alpha } \supset I_X}\). Domknięcie relacji musi być nadzbiorem tej relacji, w związku z czym\(\displaystyle{ I_X \subset R ^{ \alpha } \subset\left( R ^{ \alpha } \right) ^{ \beta } \subset \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma}}\), a więc \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma}\supset I_X }\), a więc \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma}}\) jest relacją zwrotną. Oczywiście \(\displaystyle{ \left( R ^{ \alpha } \right) ^{ \beta }}\) jest symetryczna (jako symetryczne domknięcie). wtedy nasza relacja jako jej przechodnie domknięcie relacji symetrycznej jest symetryczna- na mocy lematu 1. Oczywiście jest przechodnia też, zatem jest relacją równoważności.

2. Kontrprzykład. Niech \(\displaystyle{ X=\left\{ 0,1.2\right\}}\). oraz niech \(\displaystyle{ R=\left\{ \left( 0,2\right);(1,2) \right\} }\). Relacja \(\displaystyle{ R}\) jest przechodnia oczywiście, zatem jej przechodnie domknięcie jest jej równe \(\displaystyle{ R^{\gamma}=R}\), jej symetryczne domknięcie to \(\displaystyle{ \left( R^{\gamma}\right) ^{ \beta }= \left\{ \left( 0,2\right);\left( 2,0\right);\left( 1,2\right);\left( 2,1\right) \right\}}\), i po zwrotnym domknięciu dostajemy \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \beta } \right) ^{ \alpha } =\left\{ \left( 0,2\right);\left( 2,0\right);\left( 1,2\right);\left( 2,1\right);\left( 0,0\right);\left( 1,1\right),\left( 2,2\right) \right\}}\), taka relacja nie jest przechodnia, gdyż pary \(\displaystyle{ (0,2);(2,1)}\) do niej należą, podczas gdy para \(\displaystyle{ (0,1)}\) do niej nie należy; wobec czego to nie jest relacja przechodnia, i nie jest relacją równoważności. Ponieważ relacja \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma}}\) jest zawsze relacją równoważności, więc wtedy \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma} \neq \left( \left( R ^{ \gamma } \right) ^{ \beta } \right) ^{ \alpha } }\)

Odpowiedzi na następne dwa pytania wynikają natychmiast z dwóch poprzednich wyników oraz z lematu 0. Odpowiedzmy najpierw na pytanie 4.

4. Zauważmy, że z lematu 0 wynika, że zawsze \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \beta } \right) ^{ \alpha }= \left( \left( R ^{ \gamma } \right) ^{ \alpha } \right) ^{ \beta }}\). Biorąc ten sam kontrprzykład co poprzednio otrzymamy, że relacja \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \alpha } \right) ^{ \beta }}\) jako ta sama relacja nie będzie relacją równoważności.

3. Tak, jest to relacja równoważności na podobnej zasadzie. Niech \(\displaystyle{ R}\) będzie relacją w zbiorze \(\displaystyle{ X}\). Z lematu \(\displaystyle{ 0}\) wynika, że \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \alpha } \right) ^{\gamma }= \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma}.}\) Ponieważ, w punkcie pierwszym pokazaliśmy, że relacja \(\displaystyle{ \left( \left( R ^{ \alpha } \right) ^{ \beta } \right) ^{\gamma}}\) jest zawsze relacją równoważności, więc to oznacza, że również \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \alpha } \right) ^{\gamma }}\) jest relacją równoważności.
Ponieważ \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \alpha } \right) ^{ \beta } }\), nie musi być relacją równoważności, więc wtedy \(\displaystyle{ \left( \left( R ^{ \gamma } \right) ^{ \alpha } \right) ^{ \beta } \neq \left( \left( R ^{ \beta } \right) ^{ \alpha } \right) ^{\gamma }.}\)

I najistotniejsze (tu wykorzystam te lematy).

5. Tak, wykaże to.

Niech \(\displaystyle{ R}\) będzie relacją w zbiorze \(\displaystyle{ X}\). Wtedy relacja \(\displaystyle{ R ^{\beta}}\) jest symetryczna; zatem jej przechodnie domknięcie na mocy lematu 1 jest również symetryczne. Ponieważ jest symetryczne, więc następnie jego zwrotne domknięcie jest, na mocy lematu 2, jest również relacją symetryczną. Oznacza to, że relacja \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \gamma } \right) ^{ \alpha }}\) jest relacją symetryczną. Oczywiście jest też zwrotna. Pozostaje uzasadnić przechodniość. Wiemy, że relacja \(\displaystyle{ \left( R ^{ \beta }\right) ^\gamma{} }\) jest przechodnia, więc jej zwrotne domknięcie jest relacją przechodnią na mocy lematu 3. Oznacza to, że nasza relacja jest przechodnia, i jest relacją równoważności.

6. Nie podamy kontrprzykład. Niech \(\displaystyle{ X=\left\{ 1,2,3\right\}, R=\left\{ \left( 1,1\right);\left( 2,2\right);\left( 3,3\right);\left( \left( 1,2\right);\left( 1,3\right) \right) \right\} .}\) Wtedy \(\displaystyle{ R}\) jest zwrotna, zatem \(\displaystyle{ R ^{ \alpha }=R}\), jest też przechodnia więc \(\displaystyle{ R ^{\gamma}=R=\left( R ^{ \alpha} \right) ^{\gamma} }\), i po symetrycznym domknięciu otrzymujemy relację \(\displaystyle{ \left\{ \left( 1,1\right);\left( 2,2\right);\left( 3,3\right);\left( 1,2\right);\left( 1,3\right) ;\left( \left( 2,1\right) \right),\left( 3,1\right) \right\} }\), wtedy pary \(\displaystyle{ (2,1);(1,3) }\) należą do tej relacji, lecz para \(\displaystyle{ (2,3)}\) do niej nie należy. A więc nasza relacja nie jest przechodnia, i nie jest relacją równoważności. Ponieważ relacja \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \gamma } \right) ^{ \alpha } }\) jest zawsze relacją równoważności, więc wtedy \(\displaystyle{ \left( \left( R ^{ \beta } \right) ^{ \gamma } \right) ^{ \alpha } \neq \left( \left( R ^{ \alpha } \right) ^{ \gamma } \right) ^{ \beta }.\square }\)