Wczoraj udowodniłem, że jeśli mamy (\(\displaystyle{ n+1}\)) zbiorów \(\displaystyle{ X_1,X_2,\ldots,X_n,X_{n+1}}\) gdzie \(\displaystyle{ n \ge 1}\) oraz \(\displaystyle{ n}\) dowolnych relacji \(\displaystyle{ R_1\subset X_1\times X_2, R_2\subset X_2\times X_3,\ldots, R_n\subset X_n\times X_{n+1}}\), to zachodzi prawo:
\(\displaystyle{ \left( R_1\circ R_2\circ\ldots \circ R_n\right) ^{-1}=R_n ^{-1}\circ R_{n-1}^{-1}\circ\ldots\circ R_2^{-1}\circ R_1^{-1} }\), relacją odwrotną do złożenia tych \(\displaystyle{ n}\) relacji jest złożenie relacji odwrotnych ( ale w odwrotnej kolejności). Tu przyjmujemy, że dla dowolnej relacji R, mamy :\(\displaystyle{ \circ(R)=R}\), że złożenie jednej tylko relacji to ta sama relacja- dla dowodu warto takie uogólnienie przyjąć. Dowód, wynika z prawa relacji \(\displaystyle{ \left( R\circ S\right) ^{-1}=S^{-1}\circ R^{-1}}\). Przedstawię teraz ten indukcyjny dowód:
Jeśli \(\displaystyle{ n=1}\), to \(\displaystyle{ \left[ \circ(R)\right] ^{-1}=R^{-1}=\circ\left( R^{-1}\right) }\), i własność zachodzi.
Jeśli \(\displaystyle{ n=2}\), to z prawa relacji \(\displaystyle{ \left( R_1\circ R_2 \right) ^{-1}= R_2 ^{-1}\circ R_{1} ^{-1}}\) i własność zachodzi.
Weźmy teraz liczbę naturalną \(\displaystyle{ n \ge 3}\), i przypuśćmy, że dla każdej liczby naturalnej \(\displaystyle{ 1\le m<n}\) twierdzenie zachodzi. Niech \(\displaystyle{ X_1,X_2,\ldots, X_n,X_{n+1}}\) będą zbiorami, a \(\displaystyle{ R_1\subset X_1\times X_2, R_2\subset X_2\times X_3,\ldots, R_n\subset X_n\times X_{n+1}}\) dowolnymi relacjami. Relacja \(\displaystyle{ R_1\circ R_2\circ \ldots\circ R_n}\) musi być pewnej postaci \(\displaystyle{ R\circ S}\), gdzie \(\displaystyle{ R=R_1\circ R_2\circ \ldots \circ R_k}\), gdzie \(\displaystyle{ 1 \le k<n}\),oraz \(\displaystyle{ S=R_{k+1}\circ R_{k+2}\circ \ldots\circ R_n}\). Z prawa relacji otrzymujemy \(\displaystyle{ \left( R_{1}\circ R_2\circ\ldots\circ R_n\right) ^{-1}=S^{-1}\circ R^{-1}}\). Zauważmy że relacja \(\displaystyle{ S}\) jest tutaj przedstawiona jako złożenie mniej niż \(\displaystyle{ n}\) relacji, podobnie \(\displaystyle{ R}\) jest tutaj złożeniem mniej niż \(\displaystyle{ n}\) relacji. Zatem na mocy założenia indukcyjnego otrzymujemy równość: \(\displaystyle{ S^{-1}=R_n ^{-1}\circ R_{n-1} ^{-1}\circ\ldots \circ R_{k+2}^{-1}\circ R_{k+1} ^{-1}.}\) Podobnie dla relacji \(\displaystyle{ R}\) otrzymujemy równość: \(\displaystyle{ R^{-1}=R_k^{-1}\circ R_{k-1}^{-1}\circ \ldots\circ R_2^{-1}\circ R_1^{-1}.}\) A zatem \(\displaystyle{ \left( R_1\circ R_2\circ \ldots \circ R_n\right) ^{-1}=S^{-1} \circ R^{-1}= R_n ^{-1}\circ R_{n-1}^{-1}\circ\ldots \circ R_2^{-1}\circ R_1^{-1}}\), co należało pokazać. Dowolność tych relacji kończy dowód kroku indukcyjnego. Na mocy zasady indukcji porządkowej (dla liczb naturalnych) twierdzenie jest udowodnione.\(\displaystyle{ \square}\)
Wykażemy jeszcze, że złożenie dwóch relacji zwrotnych jest relacją zwrotną. Przypomnijmy fakt, że relacja \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) jest zwrotna, dokładnie wtedy, gdy zawiera relację identyczności \(\displaystyle{ I_X}\). Możemy zatem łatwo wykazać, że złożenie dwóch relacji zwrotnych jest relacją zwrotną.
Dowód:
Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R,S}\) relacjami zwrotnymi w zbiorze \(\displaystyle{ X.}\)
Ponieważ \(\displaystyle{ R}\) jest zwrotna, to \(\displaystyle{ R\supset I_X}\), podobnie ze zwrotności \(\displaystyle{ S}\) otrzymujemy ze \(\displaystyle{ S\supset I_X.}\) A zatem, ze zgodności złożenia relacji z zawieraniem otrzymujemy: \(\displaystyle{ S\circ R\supset I_X\circ R\supset I_X\circ I_X=I_X}\), a zatem złożenie \(\displaystyle{ S\circ R}\) zawiera relację identyczności \(\displaystyle{ I_X}\) jest więc relacją zwrotną.\(\displaystyle{ \square}\)
Wykażemy jeszcze, bardzo prosto, że jeśli relacja \(\displaystyle{ R}\) jest symetryczna, to relacja \(\displaystyle{ R\circ R}\) jest relacją symetryczną, oraz, że jeśli relacja \(\displaystyle{ R}\) jest przechodnia, to \(\displaystyle{ R\circ R}\) jest relacją przechodnią.
DWA PROSTE DOWODZIKI:
Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R}\) relacją w zbiorze \(\displaystyle{ X}\).
Załóżmy, że \(\displaystyle{ R}\) jest relacją symetryczną. Pokażemy, że \(\displaystyle{ R\circ R}\) jest relacją symetryczną. Ponieważ relacja \(\displaystyle{ R}\) jest symetryczna, więc jest równa swojej relacji odwrotnej- \(\displaystyle{ R=R^{-1}}\). Wyznaczmy \(\displaystyle{ (R\circ R)^{-1}}\). Z prawa odwracania złożenia dwóch relacji otrzymujemy \(\displaystyle{ (R\circ R)^{-1}=R^{-1} \circ R^{-1}=R\circ R.}\) Otrzymujemy zatem, ze relacja \(\displaystyle{ R\circ R}\) jest równa swojej relacji odwrotnej, więc \(\displaystyle{ R\circ R}\) jest relacją symetryczną.\(\displaystyle{ \square}\)
2. Załóżmy, że relacja \(\displaystyle{ R}\) jest przechodnia. Zatem \(\displaystyle{ R\circ R\subset R}\). Aby wykazać, że relacja \(\displaystyle{ R\circ R}\) jest przechodnia, należy wykazać, że \(\displaystyle{ \left( R\circ R\right) \circ \left( R\circ R\right) \subset R\circ R}\). Ponieważ \(\displaystyle{ R\circ R\subset R}\), więc \(\displaystyle{ \left( R\circ R\right) \circ \left( R\circ R\right)\subset R\circ (R\circ R) \subset R\circ R}\), co należało otrzymać. Zatem \(\displaystyle{ R\circ R}\) jest relacją przechodnią.\(\displaystyle{ \square}\)
Możemy zatem wnioskować z tych rozważań, że jeśli \(\displaystyle{ R}\) jest relacją równoważności w \(\displaystyle{ X}\), to \(\displaystyle{ R\circ R}\) jest relacją równoważności w \(\displaystyle{ X}\).
ale w odwrotnej kolejności). Tu przyjmujemy, że dla dowolnej relacji R, mamy :