\(\displaystyle{ R_{|A\cap B}= R_{|A} \cap R_{|B}.}\)
Udowodniłem też inne fakty, np. dla dowolnych relacji \(\displaystyle{ R,S}\) w zbiorze \(\displaystyle{ X}\), dla dowolnego zbioru \(\displaystyle{ A\subset X,}\) mamy np.:
\(\displaystyle{ (R \setminus S)_{|A}=R_{|A} \setminus S_{|A},}\)
\(\displaystyle{ (R\oplus S)_{|A}=R_{|A}\oplus S_{|A}, }\) gdzie \(\displaystyle{ R\oplus S}\) oznacza różnicę symetryczną \(\displaystyle{ R}\) i \(\displaystyle{ S.}\)
Udowodniłem też, że dla dowolnej relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) relacja \(\displaystyle{ (R \setminus R^{-1}) \cup \left( R\cap I_X\right)}\) jest relacją antysymetryczną zawartą w \(\displaystyle{ R}\). Chciałem udowodnić, ze jest to największa taka relacja antysymetryczna zawarta w \(\displaystyle{ R}\), niestety przy próbie dowodu zdałem sobie sprawę, że coś źle sobie wyobrażam, przecież jeśli będziemy mieli ilustrację relacji w postaci graficznej ciągłej to wystarczy rozważyć górna część ( tzn. powyżej przekątnej) tej relacji jako jeszcze większą relację antysymetryczną zawarta w \(\displaystyle{ R}\). Niestety, chyba to nie takie proste. Natomiast kojarzę, że kiedyś udowodniłem, że dla dowolnej relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) można wyznaczyć największą jej część symetryczną, tzn. największą relację symetryczną zawartą w relacji \(\displaystyle{ R}\), co może jeszcze raz udowodnię. Przedstawię teraz dowody tych prostych faktów.
Przypomnę może najpierw, że dla dowolnych czterech zbiorów \(\displaystyle{ A,B,C,D}\) mamy: \(\displaystyle{ (A\times B) \cap (C\times D)=(A\cap C) \times (B\cap D)}\)- przekrój dwóch iloczynów kartezjańskich jest iloczynem kartezjańskim, i to postaci: przekrój pierwszych składowych iloczynu kartezjańskiego razy przekrój drugich składowych. To można dość prosto udowodnić.
Przypominam dla dowolnych trzech zbiorów \(\displaystyle{ A,B,C}\), mamy: \(\displaystyle{ A \cap (B \cap C)=(A \cap B ) \cap C}\), łączność przekroju.
Możemy zatem teraz udowodnić, że dla dowolnej relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), dla dowolnych zbiorów \(\displaystyle{ A,B\subset X}\), mamy:
\(\displaystyle{ R_{|A\cap B}=R_{|A}\cap R_{|B}.}\)
Dowód:
Niewątpliwie mamy:
\(\displaystyle{ R_{|A}\cap R_{|B}= R\cap (A\times A)\cap R\cap (B\times B)= R\cap R\cap (A\times A)\cap (B\times B)= R\cap (A\times A)\cap (B\times B)= R\cap [(A\cap B)\times (A\cap B)]=\\ = R_{|A\cap B}}\), gdzie przedostatnia równość wynika z przytoczonego faktu o przekroju dwóch iloczynów kartezjańskich. Dowód jest zakończony.
Zauważmy, że dla dowolnych relacji \(\displaystyle{ R,S}\) w zbiorze \(\displaystyle{ X}\), dla dowolnego zbioru \(\displaystyle{ A\subset X}\), mamy:
1)\(\displaystyle{ (R\cup S)_{|A}= R_{|A}\cup S_{|A}. }\)
2) \(\displaystyle{ (R\cap S)_{|A}= R_{|A}\cap S_{|A}.}\)
3) \(\displaystyle{ (R \setminus S)_{|A}=R_{|A} \setminus S_{|A}.}\)
4)\(\displaystyle{ (R\oplus S)_{|A}=R_{|A}\oplus S_{|A}.}\)
5)\(\displaystyle{ (R'=(X\times X) \setminus R )_{|A}= (A\times A) \setminus R_{|A}.}\)
Są to proste fakty. Dowód 1) jest oczywisty, Dowód 2) przedstawiam w ukrytej treści:
Ukryta treść:
Dowód 4) wynika stąd, że dla dowolnych trzech zbiorów \(\displaystyle{ X_1,X_2,X_3}\), mamy:\(\displaystyle{ \left( X_1\oplus X_2\right) \cap X_3 =(X_1\cap X_3)\oplus (X_2 \cap X_3)}\), a stąd łatwo wynika 4). Można też inaczej, skorzystać z wcześniejszych faktów i definicji różnicy symetrycznej:
\(\displaystyle{ (R\oplus S)_{|A}=((R \setminus S) \cup (S \setminus R))_{|A}=\left( R \setminus S\right)_{|A}\cup \left( S \setminus R\right)_{|A}=(R_{|A} \setminus S_{|A}) \cup (S_{|A} \setminus R_{|A})= (R_{|A})\oplus (S_{|A}).}\)
Dowód 5) łatwo wynika z własności 3) z różnicą.
Wykażemy teraz, że dla dowolnej relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), mamy\(\displaystyle{ S:=\left( R \setminus R ^{-1} \right) \cup \left( R\cap I_X\right)}\) jest relacją antysymetryczną zawartą w \(\displaystyle{ R}\) (niestety, nie jest na ogół największą taką relacją).
Aby wykazać, że \(\displaystyle{ S}\) jest antysymetryczna, to niech \(\displaystyle{ (x,y);(y,x)\in S.}\)
Jeśli \(\displaystyle{ (x,y)\in R\cap I_X}\), to \(\displaystyle{ (x,y)\in I_X}\), a stąd \(\displaystyle{ x=y}\), co należało pokazać.
Jeśli \(\displaystyle{ (y,x)\in R\cap I_X}\), to \(\displaystyle{ (y,x)\in I_X}\), skąd \(\displaystyle{ x=y.}\)
Pozostaje rozważyć przypadek gdy \(\displaystyle{ (x,y)\not\in R\cap I_X}\) i \(\displaystyle{ (y,x)\not\in R\cap I_X}\), czyli (gdyż obie pary należą do \(\displaystyle{ S}\)) , więc \(\displaystyle{ (x,y)\in R \setminus R^{-1}}\) i \(\displaystyle{ (y,x)\in R \setminus R^{-1}}\). Łatwo on prowadzi do sprzeczności, gdyż wtedy \(\displaystyle{ (x,y)\in R, (x,y)\not\in R^{-1},}\) podobnie druga własność daje \(\displaystyle{ (y,x)\in R}\), a więc z określenia relacji odwrotnej\(\displaystyle{ (x,y)\in R^{-1}}\)- sprzeczność. Wobec czego ten przypadek jest niemożliwy. Dowód antysymetrii jest zakończony, a więc \(\displaystyle{ S}\) jest antysymetryczna. Oczywiście \(\displaystyle{ S\subset R}\) jako suma dwóch podzbiorów \(\displaystyle{ R}\), jest podzbiorem relacji \(\displaystyle{ R.\square}\)
Natomiast dla relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), \(\displaystyle{ R^{-1}\cap R}\) jest największą relacją symetryczną zawartą w \(\displaystyle{ R}\).
Dowód:
Niewątpliwie \(\displaystyle{ R^{-1}\cap R\subset R}\). Aby wykazać, że \(\displaystyle{ R^{-1}\cap R}\) jest relacją symetryczną należy wykazać, że jest równa swojej relacji odwrotnej; wobec czego wyznaczmy \(\displaystyle{ (R^{-1}\cap R)^{-1}}\):
\(\displaystyle{ (R^{-1}\cap R)^{-1}=(R^{-1})^{-1}\cap R^{-1}=R\cap R^{-1}= R^{-1}\cap R}\), tak więc relacja \(\displaystyle{ R^{-1}\cap R}\) jest równa swojej relacji odwrotnej, jest więc relacją symetryczną.
Pozostaje wykazać, że jest to największa taka relacja. Niech \(\displaystyle{ S}\) będzie relacją w \(\displaystyle{ X}\), relacją symetryczną zawartą w \(\displaystyle{ R}\)- \(\displaystyle{ S\subset R}\). Pokażemy, że \(\displaystyle{ S\subset R^{-1}\cap R}\). Ponieważ \(\displaystyle{ S}\) jest symetryczna, to \(\displaystyle{ S=S^{-1}}\), jest równa swojej relacji odwrotnej, ponieważ \(\displaystyle{ S\subset R}\), to również \(\displaystyle{ S=S^{-1}\subset R^{-1}.}\) Mamy \(\displaystyle{ S\subset R^{-1}, S\subset R}\), więc również \(\displaystyle{ S}\) zawiera się w przekroju tych dwóch zbiorów: \(\displaystyle{ S\subset R^{-1}\cap R.}\) Tak więc \(\displaystyle{ R^{-1}\cap R}\) jest największą relacją symetryczną zawartą w relacji \(\displaystyle{ R. \square}\)
Na koniec dodam, ze jest taki bardzo ciekawy problem, że w relacji można zawrzeć maksymalny kwadrat kartezjański, polecam.