\(\displaystyle{ S\circ R=\left\{ \left( a,c\right) \in A \times C\Bigl| \ \ \bigvee\limits_{b \in B} \left( a,b\right) \in R \wedge \left( b,c\right) \in S \right\}. }\)
Przypomnijmy, mamy prawo relacji \(\displaystyle{ T \subset A \times B; R,S \subset B \times C,}\) wtedy mamy prawo:
\(\displaystyle{ \left( R \cap S\right) \circ T \subset \left( R\circ T\right) \cap \left( S\circ T\right), }\)
DOWÓD TEGO FAKTU::
Mamy też podobne prawo relacji (pomiędzy odpowiednimi zbiorami):
\(\displaystyle{ T\circ \left( R \cap S\right) \subset \left( T\circ R\right) \cap \left( T\circ S\right). }\)
Można się spodziwać, że przez indukcję można udowodnić odpowiednik tego (tego pierwszego) prawa dla \(\displaystyle{ {n+1} }\) relacji \(\displaystyle{ R _{1}, R _{2}, \ldots, R_n \subset B \times C }\) oraz \(\displaystyle{ T \subset A \times B,}\) wtedy:
\(\displaystyle{ \left( R _{1} \cap R _{2} \cap R _{3} \cap\ldots \cap R _{n}\right) \circ T \subset \left( R _{1}\circ T \right) \cap \left( R _{2}\circ T \right) \cap \ldots \cap \left( R _{n}\circ T \right). }\)
Okazuje się, że to prawo można uogólnić dla dowolnej niepustej rodziny relacji, tzn.:
Jeśli \(\displaystyle{ A,B,C}\) są zbiorami,
a \(\displaystyle{ \mathbb {B}}\) jest niepustą rodziną relacji ze zbioru \(\displaystyle{ B}\) do \(\displaystyle{ C,}\) a \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ A}\) do \(\displaystyle{ B}\), to mamy prawo:
\(\displaystyle{ \left( \bigcap \mathbb{B}\right) \circ R \subset \bigcap_{A \in \mathbb{B}}\left( A\circ R\right). }\)
DOWÓD TEGO FAKTU:
Zauważmy najpierw, że obydwie relacje- zaròwno zbiór po lewej stronie inkluzji, jak i zbiór po prawej stronie, są relacjami z \(\displaystyle{ A}\) do \(\displaystyle{ C}\), można się o tym łatwo przekonać.
Niech \(\displaystyle{ A \in \mathbb {B}.}\)
Wtedy, z własności przekroju:
\(\displaystyle{ \bigcap\mathbb {B} \subset A,}\) a zatem \(\displaystyle{ \left( \bigcap\mathbb {B}\right) \cap A= \bigcap \mathbb {B}. }\)
A zatem:
\(\displaystyle{ \left( \bigcap\mathbb{B}\right)\circ R= \left( \left( \bigcap\mathbb{B}\right) \cap A \right)\circ R \subset \left( \left( \bigcap\mathbb{B}\right)\circ R \right) \cap \left( A\circ R\right) \subset A \circ R,}\)
gdzie pierwsza inkluzja pochodzi z wcześniej podanego faktu dla dwóch relacji, a druga inkluzja to zwykła własność przekroju dwóch zbiorów.
Otrzymujemy zatem:
\(\displaystyle{ \left( \bigcap\mathbb{B}\right)\circ R \subset A\circ R, }\)
i to dla dowolnej relacji \(\displaystyle{ A \in \mathbb{B} \neq \left\{ \right\}, }\) więc również:
\(\displaystyle{ \left( \bigcap\mathbb {B}\right)\circ R \subset \bigcap_{A \in \mathbb {B}} \left( A\circ R\right).\square }\)
Przypomnijmy, dla relacji \(\displaystyle{ R,S \subset B \times C,}\) oraz dla relacji \(\displaystyle{ T \subset A \times B,}\) mamy prawo:
\(\displaystyle{ \left( R \cup S\right)\circ T= \left( R\circ T\right) \cup \left( S\circ T\right). }\)
Mamy też prawo relacji (pomiędzy odpowiednimi zbiorami ):
\(\displaystyle{ T\circ\left( R \cup S\right)= \left( T\circ R\right) \cup \left( T\circ S\right). }\)
Okazuje się, że te dwa prawa można uogólnić dla dowolnej rodziny relacji.
Tzn. jeśli \(\displaystyle{ A,B,C}\) są zbiorami, \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ A}\) do \(\displaystyle{ B,}\) a \(\displaystyle{ \mathbb {B}}\) jest rodziną relacji z \(\displaystyle{ B}\) do \(\displaystyle{ C,}\) to mamy prawo:
\(\displaystyle{ \left( \bigcup\mathbb {B}\right)\circ R= \bigcup_{A \in \mathbb {B}} \left( A\circ R\right). }\)
DOWÓD TEGO FAKTU:
Zauważmy najpierw, że zarówno zbiór po lewej stronie równości, jak i zbiór po prawej stronie są relacjami z \(\displaystyle{ A}\) do \(\displaystyle{ C}\), można się o tym łatwo przekonać.
Niech \(\displaystyle{ A \in \mathbb{B}.}\)
Wtedy \(\displaystyle{ A \subset \bigcup \mathbb{B}}\),
a zatem \(\displaystyle{ \bigcup \mathbb {B} \cup A= \bigcup\mathbb {B}.}\)
A zatem:
\(\displaystyle{ \bigcup\mathbb {B}\circ R=\left( \bigcup\mathbb {B} \cup A\right)\circ R= \left( \bigcup\mathbb {B}\circ R \right) \cup \left( A\circ R\right) \supset A\circ R; }\)
i taka inkluzja zachodzi dla dowolnej relacji \(\displaystyle{ A \in \mathbb {B}. }\)
Otrzymujemy zatem, że dla dowolnej relacji \(\displaystyle{ A \in \mathbb {B}}\):
\(\displaystyle{ A\circ R \subset \left( \bigcup\mathbb {B} \right)\circ R, }\)
więc również:
\(\displaystyle{ \bigcup_{A \in \mathbb {B} } \left( A\circ R\right) \subset \left( \bigcup \mathbb {B}\right)\circ R. }\)
Aby pokazać inkluzje w drugą stronę, to niech \(\displaystyle{ \left( a,c\right) \in \bigcup\mathbb {B}\circ R. }\)
Wtedy \(\displaystyle{ \left( a,b\right) \in R }\) i \(\displaystyle{ \left( b,c\right) \in \bigcup \mathbb {B}, }\) dla pewnego elementu \(\displaystyle{ b \in B.}\)
Skoro \(\displaystyle{ \left( b,c\right) \in \bigcup\mathbb {B}, }\) to \(\displaystyle{ \left(b ,c\right) \in A, }\) dla pewnej relacji \(\displaystyle{ A \in\mathbb {B}.}\)
Skoro \(\displaystyle{ \left( a,b\right) \in R; \left( b,c\right) \in A, }\) to \(\displaystyle{ \left( a,c\right) \in A\circ R, }\) i ponieważ \(\displaystyle{ A \in \mathbb{B},}\) więc tym bardziej \(\displaystyle{ \left( a,c\right) \in \bigcup_{A \in \mathbb{B} } \left( A\circ R\right).\square }\)
Podobnie, jeśli \(\displaystyle{ A,B,C}\) są zbiorami, a \(\displaystyle{ \mathbb {B}}\) jest rodzina relacji z \(\displaystyle{ A}\) do \(\displaystyle{ B,}\) a \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ B}\) do \(\displaystyle{ C}\), to mamy prawo:
\(\displaystyle{ R\circ \bigcup\mathbb {B}= \bigcup_{A \in \mathbb {B}} \left( R\circ A\right). }\)
W sposób analogiczny jak powyżej, analogicznie możemy to udowodnić.
Przypomnijmy, mamy prawo odwracania złożenia relacji pomiędzy odpowiednimi zbiorami :
\(\displaystyle{ \left( S\circ R\right) ^{-1}= R ^{-1}\circ S ^{-1}, }\)
- relacja odwrotna do złożenia dwóch relacji jest złożeniem relacji odwrotnych, ale wziętych w odwróconej kolejności.
Ponieważ złożenie relacji jest operacją łączną, co udowodniłem TUTAJ, to latwo można pokazać przez indukcje porządkową, prawo \(\displaystyle{ n}\) relacji pomiędzy odpowiednimi zbiorami:
\(\displaystyle{ \left( R _{1}\circ R _{2}\circ R _{3} \circ \ldots \circ R _{n}\right) ^{-1}= R ^{-1} _{n}\circ R _{n-1} ^{-1}\circ \ldots \circ R ^{-1} _{2} \circ R ^{-1} _{1}; }\)
tzn. relacja odwrotna do złożenia \(\displaystyle{ n}\) relacji jest złożeniem relacji odwrotnych, ale w odwrotnej kolejności.
Łatwo to można, przez indukcje porządkową, udowodnić (przyjmując, że dla dowolnej relacji \(\displaystyle{ R,}\) mamy: \(\displaystyle{ \circ \left( R\right) = R}\)- złożenie tylko jednej relacji, to jest to ta sama relacja, jest wygodnym przyjęcie takiej umowy, dla dowodu indukcyjnego ), i taki fakt można łatwo, przez indukcje porządkową, udowodnić.
Dodam tutaj jeszcze jeden dowodzik.
Wykażemy prawo mówiące, że dla dowolnej niepustej rodziny zbiorów \(\displaystyle{ \mathbb {B},}\) oraz dla dowolnego zbioru \(\displaystyle{ X,}\) mamy prawo:
\(\displaystyle{ \left( \bigcap\mathbb {B}\right) \times X= \bigcap _{A \in \mathbb {B}} \left( A \times X\right). }\)
Przypomnijmy, mamy podobne prawo dla sumy, dla dowolnej rodziny zbiorów \(\displaystyle{ \mathbb {A},}\) oraz dla dowolnego zbioru \(\displaystyle{ Y}\), mamy:
\(\displaystyle{ \left( \bigcup \mathbb{A}\right) \times Y= \bigcup_{A \in \mathbb{A} } \left( A \times Y\right); }\)
jest to dość podstawowy fakt.
Zauważmy też, że jeśli mamy prostokąt \(\displaystyle{ Y \times X,}\) oraz mamy zbiór \(\displaystyle{ A \subset Y,}\) to dla dopełnienia mamy równość:
\(\displaystyle{ \left( A \times X\right)'=\left( Y \times X\right) \setminus \left( A \times X\right) =A' \times X. }\)
Łatwo zatem możemy udowodnić nasz fakt
DOWÓD TEGO FAKTU:
Niech \(\displaystyle{ \mathbb {B} }\) będzie niepustą rodziną zbiorów, i niech \(\displaystyle{ X}\) będzie zbiorem.
Niech \(\displaystyle{ U=\left( \bigcup\mathbb {B} \right) \times X}\) będzie naszą przestrzenią, do której będziemy dopełniać iloczyny kartezjańskie.
Wtedy:
\(\displaystyle{ \left( \bigcap\mathbb {B} \right) \times X=\left( \left( \bigcap\mathbb {B} \times X\right) '\right)'=\left( \left( \bigcap\mathbb {B}\right)' \times X\right)'=\left( \left( \bigcup_{A \in \mathbb {B} } A'\right) \times X\right)'= \left( \bigcup_{A \in \mathbb {B} } \left( A' \times X\right) \right)'= \bigcap_{A \in \mathbb{B}} \left( A' \times X\right) '= \bigcap_{A \in \mathbb {B}} \left( \left( A'\right) ' \times X \right) = \\=\bigcap_{A \in \mathbb {B} } \left( A \times X\right).\square }\)
, gdzie w drugim przejściu skorzystaliśmy ze wspomnianego prawa o dopełnieniu iloczynu kartezjańskiego, następnie używamy prawa de Morgana odnośnie dopełnienia przekroju, następnie mnożymy kartezjańsko tą sumę przez ten sam zbiór \(\displaystyle{ X}\), potem znowu używamy prawa de Morgana odnośnie dopełnienia sumy, i potem znowu używamy tego prostego prawa odnośnie dopełnienia iloczynu kartezjańskiego, i na koniec redukujemy podwójne dopełnienie, co kończy dowód tego faktu. \(\displaystyle{ \square}\)
Na koniec podam dwa proste fakty:
Zauważmy, że jeśli \(\displaystyle{ X,Y }\) I \(\displaystyle{ Z}\) są zbiorami i \(\displaystyle{ Y}\) jest zbiorem niepustym, to:
\(\displaystyle{ \left( Y \times Z\right)\circ \left( X \times Y\right)= \left( X \times Z\right). }\)
PROSTY DOWÓD TEGO FAKTU::
jeśli \(\displaystyle{ A \times B=A \times C,}\) to \(\displaystyle{ B=C;}\)
możemy to łatwo udowodnić.
