Zawężenia relacji

[Jakub Gurak]

Wprowadźmy notację, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R}\) relacją w zbiorze \(\displaystyle{ X}\), a \(\displaystyle{ A}\) podzbiorem zbioru \(\displaystyle{ X}\), to przez \(\displaystyle{ R_{|A}}\) będziemy oznaczać zawężenie relacji \(\displaystyle{ R}\) do zbioru \(\displaystyle{ A}\), tzn. \(\displaystyle{ R_{|A}:=R\cap (A\times A)}\). Wczoraj i dzisiaj udowodniłem, ż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}.}\)

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ść:    

\(\displaystyle{ (R\cap S)_{|A}= (R\cap S) \cap (A\times A)= R\cap S \cap (A\times A) \cap (A\times A)= \left[ R\cap (A\times A) \right] \cap [S\cap (A\times A)]=R_{|A}\cap S_{|A}.}\)

Dowód 3) wynika stąd, że dla dowolnych trzech zbiorów \(\displaystyle{ X_1,X_2,X_3}\), mamy \(\displaystyle{ (X_1 \setminus X_2)\cap X_3=\left( X_1\cap X_3\right) \setminus \left( X_2\cap X_3\right)}\), co jest prostym faktem, a stąd łatwo wynika własność 3.

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.

[Jakub Gurak]

Udowodniłem wczoraj sobie na dobranoc, że jeśli \(\displaystyle{ X,Y}\) są zbiorami, a funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest bijekcją, oraz zbiór \(\displaystyle{ A\subset X}\) jest podzbiorem dziedziny funkcji, to funkcja odwrotna do obcięcia funkcji \(\displaystyle{ f}\) do zbioru \(\displaystyle{ A}\) jest obcięciem funkcji odwrotnej do obrazu zbioru \(\displaystyle{ A}\). A dzień wcześniej na dobranoc udowodniłem, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ A\subset X}\)jego podzbiorem, to porządek odwrotny do porządku \(\displaystyle{ \le}\) obciętego do zbioru \(\displaystyle{ A}\) jest obcięciem porządku odwrotnego (na \(\displaystyle{ X}\)) do zbioru \(\displaystyle{ A}\). Przedstawię teraz dowody tych ciekawych faktów.

Niech \(\displaystyle{ X,Y}\) będą zbiorami, niech \(\displaystyle{ f:X \rightarrow Y}\) będzie bijekcją, niech zbiór \(\displaystyle{ A\subset X}\). Pokażemy, że \(\displaystyle{ f ^{-1} _{|\stackrel { \rightarrow }{f} (A)} =\left( f _{|A} \right) ^{-1}}\), czyli, że funkcja odwrotna do obcięcia funkcji \(\displaystyle{ f}\) do zbioru \(\displaystyle{ A}\) jest obcięciem funkcji odwrotnej do obrazu zbioru \(\displaystyle{ A}\).

Dowód:

Ponieważ funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest bijekcją, to również funkcja obcięta \(\displaystyle{ f_{|A}:A \rightarrow \stackrel { \rightarrow }{f}(A)}\) jest bijekcją, zatem relacja odwrotna \(\displaystyle{ \left( f _{|A} \right) ^{-1}}\) jest bijekcją (w szczególności jest funkcją) z \(\displaystyle{ \stackrel { \rightarrow }{f} (A )}\) w \(\displaystyle{ A}\). Natomiast (ponieważ \(\displaystyle{ f}\) jest bijekcją), to \(\displaystyle{ f:Y \rightarrow X }\) jest funkcją, i jej obcięcie do zbioru \(\displaystyle{ \stackrel { \rightarrow }{f} (A)}\) jest o wartościach w \(\displaystyle{ \stackrel { \rightarrow } {\left( g:=f^{-1}\right) }\left( \stackrel { \rightarrow }{f}(A)\right) = \stackrel { \rightarrow }{ f^{-1} }\left( \stackrel {\rightarrow} {f} (A)\right),}\) i ponieważ \(\displaystyle{ f}\) jest bijekcją, to ten zbiór jest równy zbiorowi \(\displaystyle{ A}\). Tak więc \(\displaystyle{ f^{-1} _{|\stackrel { \rightarrow }{f} (A)} : \stackrel{ \rightarrow }{f} (A) \rightarrow A}\), i również \(\displaystyle{ \left( f _{|A} \right) ^{-1}: \stackrel { \rightarrow } {f}\left( A\right) \rightarrow A}\). Pozostaje pokazać, że te funkcje w każdym punkcie dziedziny przyjmują te same wartości.

Niech \(\displaystyle{ y\in \stackrel { \rightarrow } {f} (A)}\). Oznaczmy \(\displaystyle{ f ^{-1} _{\stackrel { \rightarrow }{f} (A)} (y)=:x}\). Wtedy \(\displaystyle{ y\in \stackrel { \rightarrow } {f} (A), x\in A}\). Mamy, tym bardziej dla rozszerzenia tej funkcji: \(\displaystyle{ f ^{-1} (y)=x}\), zatem \(\displaystyle{ f(x)=y}\). Mamy \(\displaystyle{ x\in A, y\in\stackrel{\rightarrow }{f} (A) }\), zatem \(\displaystyle{ f _{|A}(x)=y}\), a zatem \(\displaystyle{ \left( f _{|A} \right) ^{-1} (y)=x = f ^{-1} _{\stackrel { \rightarrow }{f} (A)} (y). }\)

A zatem \(\displaystyle{ \left( f _{|A} \right) ^{-1} = f ^{-1} _{| \stackrel { \rightarrow }{f} (A)}. \square}\)


Wykażemy jeszcze, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, oraz \(\displaystyle{ A\subset X}\) jego podzbiorem, to jeśli rozważymy zbiór liniowo uporządkowany \(\displaystyle{ \left( A, \le _A\right) }\), a potem do niego porządek odwrotny, to będzie to identyczne z tym, gdy weźmiemy porządek odwrotny na całym \(\displaystyle{ X}\), a następnie obcięcie jego do zbioru \(\displaystyle{ A}\), tzn. \(\displaystyle{ \left( \le _{|A} ^{-1} \right) = \left( \le ^{-1} \right) _{|A} .}\)

Prosty dowód:

Zauważmy najpierw, że oba te porządki są określone na \(\displaystyle{ A}\) (gdyż porządek odwrotny do liniowego jest liniowy na tym samym zbiorze). I mamy, gdyż relacja odwrotna do przekroju dwóch relacji jest przekrojem relacji odwrotnych, więc:

\(\displaystyle{ \left( \le _{A} \right) ^{-1}= \left[ \le \cap \left( A \times A\right) \right] ^{-1}= \le ^{-1} \cap \left( A \times A\right) ^{-1} \stackrel { \left( B \times C\right) ^{-1} =C \times B } {=} \le ^{-1} \cap \left( A \times A\right) =\left( \le ^{-1} \right) _{|A} . \square}\)

[Jakub Gurak]

Udowodniłem przedwczoraj i dzień wcześniej, że jeśli mamy dwa zbiory, funkcję pomiędzy nimi, oraz podzbiór \(\displaystyle{ A}\) dziedziny funkcji (wtedy możemy rozważać obcięcie tej funkcji do zbioru \(\displaystyle{ A}\)), i jeśli mamy zbiór \(\displaystyle{ B\subset A}\), to obraz tego zbioru przez funkcję daną jest równy obrazowi tego zbioru przez funkcję, którą jest to obcięcie. Udowodniłem też, że przeciwobraz zbioru \(\displaystyle{ C\subset Y}\) przez funkcję obcięcia jest równy przeciwobrazowi tego zbioru przez funkcję daną przekrojonemu ze zbiorem \(\displaystyle{ A}\)- dziedziną funkcji obcięcia.
Przypominam, jak mamy dwie funkcję \(\displaystyle{ f_1:X_1 \rightarrow Y_1,}\) oraz \(\displaystyle{ f_2:X_2 \rightarrow Y_2,}\) i w przekroju dziedzin tych funkcji funkcję te się pokrywają, to suma tych dwóch funkcji jest funkcją ze sumy dziedzin tych funkcji w sumę przeciwdziedzin- jest to dość podstawowy fakt. I właśnie udowodniłem taki ciekawy fakt, że jeśli mamy zbiór \(\displaystyle{ A_1\subset X_1,}\) oraz zbiór \(\displaystyle{ A_2\subset X_2}\), to suma obrazu tego pierwszego zbioru przez pierwszą funkcję \(\displaystyle{ f_1, }\) i obrazu drugiego zbioru przez drugą funkcję \(\displaystyle{ f_2,}\) jest równa obrazowi sumy tych dwóch zbiorów przez funkcję, którą jest suma. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ X,Y}\) będą zbiorami, a \(\displaystyle{ f:X \rightarrow Y}\) niech będzie dowolną funkcją. Niech \(\displaystyle{ A\subset X}\). Będziemy rozważać obcięcie \(\displaystyle{ f _{|A}}\) funkcji \(\displaystyle{ f}\) do zbioru \(\displaystyle{ A}\). Wtedy \(\displaystyle{ f _{|A}:A \rightarrow Y}\). Rozważmy jeszcze zbiór \(\displaystyle{ B\subset A}\). Wykażemy, że obraz tego zbioru przez funkcję \(\displaystyle{ f}\) jest równy obrazowi tego zbioru przez funkcję obcięcia, czyli \(\displaystyle{ \stackrel { \rightarrow }{f} (B)= \stackrel { \rightarrow }{f _{|A} } (B).}\)

DOWÓD TEGO FAKTU:

Mamy \(\displaystyle{ B\subset X}\), a więc polecenie jest dobrze określone.

Niech \(\displaystyle{ y\in\stackrel { \rightarrow }{f} (B).}\) Wtedy \(\displaystyle{ y=f(x)}\), gdzie \(\displaystyle{ x\in B}\). Ponieważ \(\displaystyle{ B\subset A}\), więc \(\displaystyle{ x\in A}\). A zatem \(\displaystyle{ f _{|A}(x)= f(x)=y}\), czyli \(\displaystyle{ y=f _{|A} (x)}\), gdzie \(\displaystyle{ x\in B}\), a zatem \(\displaystyle{ y\in \stackrel { \rightarrow }{f _{|A} } (B)}\), co dowodzi inkluzji w prawo.

Niech teraz \(\displaystyle{ y\in \stackrel { \rightarrow }{f _{|A} } (B)}\). Wtedy \(\displaystyle{ y=f _{|A} (x)}\), gdzie \(\displaystyle{ x\in B}\). Wtedy również \(\displaystyle{ y=f(x)}\), gdzie \(\displaystyle{ x\in B}\), a zatem \(\displaystyle{ y\in \stackrel { \rightarrow }{f} (B)}\), co dowodzi inkluzji w drugą stronę, i \(\displaystyle{ \stackrel { \rightarrow }{f} (B)= \stackrel { \rightarrow }{f _{|A} } (B).\square}\)

Wynika stąd, że zbiór wartości funkcji obcięcia jest równy obrazowi zbioru \(\displaystyle{ A}\) przez daną funkcję \(\displaystyle{ f}\).


Wykażemy teraz, że jeśli (przy tych samych oznaczeniach) jeśli mamy zbiór \(\displaystyle{ C\subset Y}\), to: \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} _{|A} }(C)= \stackrel { \rightarrow }{f ^{-1} } (C) \cap A.}\)

Niech \(\displaystyle{ x\in\stackrel { \rightarrow }{f ^{-1} _{|A} } \left( C\right) .}\) Wtedy \(\displaystyle{ x\in A}\), i \(\displaystyle{ f _{|A}(x)\in C}\). Mamy \(\displaystyle{ f(x)=f _{|A}(x)\in C}\), a zatem \(\displaystyle{ x\in\stackrel { \rightarrow }{f ^{-1} } \left( C\right)}\), i \(\displaystyle{ x\in \stackrel { \rightarrow }{f ^{-1} } \left( C\right) \cap A.}\)

Jeśli \(\displaystyle{ x\in \stackrel { \rightarrow }{f ^{-1} } \left( C\right) \cap A.}\) Wtedy \(\displaystyle{ x\in A}\), i z drugiego warunku mamy: \(\displaystyle{ f(x)\in C.}\) Wtedy \(\displaystyle{ f _{|A}(x)=f(x)\in C}\), a zatem \(\displaystyle{ x\in \stackrel { \rightarrow }{f ^{-1} _{|A} } \left( C\right).}\)

A zatem \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} _{|A} } \left( C\right) = \stackrel { \rightarrow }{f ^{-1} } \left( C\right) \cap A.\square}\)


Rozważmy teraz cztery zbiory \(\displaystyle{ X_1, X_2, Y_1, Y_2,}\) oraz dwie funkcję \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\), i \(\displaystyle{ f_2:X_2 \rightarrow Y_2;}\) takie, że dla każdego \(\displaystyle{ x\in X_1 \cap X_2}\), mamy: \(\displaystyle{ f_1(x)=f_2(x)}\) (czyli dodajemy tu jeszcze tylko jeden warunek: w przekroju dziedzin tych funkcji funkcje te się pokrywają), wtedy suma \(\displaystyle{ f_1 \cup f_2}\) jest funkcją ze sumy dziedzin tych funkcji, czyli z \(\displaystyle{ X_1 \cup X_2,}\) w sumę przeciwdziedzin \(\displaystyle{ Y_1 \cup Y_2}\). Rozważmy dwa zbiory: \(\displaystyle{ A_1\subset X_1}\), oraz zbiór \(\displaystyle{ A_2\subset X_2}\). I rozważmy obrazy tych zbiorów przez odpowiednio pierwszą funkcję \(\displaystyle{ f_1}\) i odpowiednio przez drugą funkcję \(\displaystyle{ f_2}\). Wykażemy, że suma tych obrazów jest równa obrazowi sumy tych dwóch zbiorów przez funkcję, którą jest suma, czyli, że: \(\displaystyle{ \stackrel { \rightarrow } {f_1} \left( A_1\right) \cup \stackrel { \rightarrow } {f_2} \left( A_2\right)=\stackrel{ \rightarrow }{f_1 \cup f_2}\left( A_1 \cup A_2\right).}\)

DOWÓD TEGO CIEKAWEGO FAKTU::    

Ponieważ dla dowolnej funkcji między dwoma zbiorami, obraz sumy dwóch podzbiorów dziedziny funkcji jest równy sumie obrazów tych zbiorów, więc:\(\displaystyle{ }\)

\(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1 \cup A_2\right)= \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1\right) \cup \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_2\right).}\)

Wykażemy teraz, że: \(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1\right) =\stackrel{ \rightarrow }{ f_1 }\left( A_1\right).}\)

Mamy, (dla \(\displaystyle{ y\in Y_1 \cup Y_2}\)), mamy:

\(\displaystyle{ y\in \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1\right) \Leftrightarrow y= \left( f_1 \cup f_2\right) (x),\hbox{ dla pewnego } x\in A_1}\),

wtedy \(\displaystyle{ x\in X_1}\), a zatem \(\displaystyle{ f_1(x)= \left( f_1 \cup f_2\right) (x)}\) , a zatem to ostatnie przejście znaczy to samo, co:

\(\displaystyle{ \Leftrightarrow y=f_1(x), \hbox{ dla pewnego } x\in A_1}\),

a to znaczy to samo, co warunek :

\(\displaystyle{ y\in \stackrel{ \rightarrow }{f_1 }\left( A_1\right). }\)

A zatem : \(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1\right) =\stackrel{ \rightarrow }{f_1 }\left( A_1\right).}\)


Analogicznie udowadniamy, że: \(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_2\right) =\stackrel{ \rightarrow }{ f_2 }\left( A_2\right). }\)

Łącząc te dwa fakty, otrzymujemy:

\(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1 \cup A_2\right)= \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_1\right) \cup \stackrel{ \rightarrow }{\left( f_1 \cup f_2\right) }\left( A_2\right)= \stackrel{ \rightarrow }{ f_1 }\left( A_1\right) \cup \stackrel{ \rightarrow }{f_2 }\left( A_2\right) .\square}\)

Na koniec wykażemy jeszcze jeden prosty fakt.

Nim to zrobimy, przypomnijmy, że jeśli mamy dwie funkcję \(\displaystyle{ f_1:X_1 \rightarrow Y_1}\) oraz \(\displaystyle{ f_2:X_2 \rightarrow Y_2}\), i gdy w przekroju dziedzin tych funkcji funkcje te się pokrywają, to przekrój \(\displaystyle{ f_1 \cap f_2}\) jest funkcją z \(\displaystyle{ X_1 \cap X_2}\) w \(\displaystyle{ Y_1 \cap Y_2}\)- jest to dość elementarny fakt.

Rozważmy teraz zbiór \(\displaystyle{ A\subset X_1 \cap X_2}\). Wykażemy, że obraz tego zbioru przez funkcję, którą jest przekrój, jest równy obrazowi tego zbioru przez funkcję pierwszą i jest równy obrazowi tego zbioru przez funkcję drugą, tzn.: \(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cap f_2\right) }\left( A\right) =\stackrel{ \rightarrow }{ f_1 }\left( A\right) =\stackrel{ \rightarrow }{ f_2 }\left( A\right).}\)

DOWÓD TEGO FAKTU::    

Wykażemy, że \(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cap f_2\right) }\left( A\right) =\stackrel{ \rightarrow }{ f_1 }\left( A\right).}\)

Niech \(\displaystyle{ y\in Y_1}\). Wtedy:

\(\displaystyle{ y\in \stackrel{ \rightarrow }{\left( f_1 \cap f_2\right) }\left( A\right) \Leftrightarrow y=\left( f_1 \cap f_2\right) \left( x\right), \hbox{ dla pewnego } x\in A.}\)

Ponieważ \(\displaystyle{ f_1 \cap f_2 \subset f_1}\), więc funkcja \(\displaystyle{ f_1}\) rozszerza funkcję \(\displaystyle{ f_1 \cap f_2}\), więc \(\displaystyle{ \left( f_1 \cap f_2\right) (x)=f_1(x)}\), a zatem to ostanie przejście znaczy to samo co:

\(\displaystyle{ y=f_1(x),\hbox{ dla pewnego } x\in A}\),

a to znaczy to samo co warunek:

\(\displaystyle{ y\in \stackrel{ \rightarrow }{f_1 }\left( A\right)}\).

Wobec czego \(\displaystyle{ \stackrel{ \rightarrow }{\left( f_1 \cap f_2\right) }\left( A\right) =\stackrel{ \rightarrow }{f_1 }\left( A\right).}\)

Podobnie, bardzo łatwo możemy pokazać, że: \(\displaystyle{ \stackrel{ \rightarrow }{f_1 }\left( A\right) =\stackrel{ \rightarrow }{f_2 }\left( A\right)}\), gdyż w przekroju dziedzin tych funkcji \(\displaystyle{ f_1}\), \(\displaystyle{ f_2}\) funkcję te się pokrywają, więc łatwo to możemy udowodnić.

Wobec czego: \(\displaystyle{ \stackrel{ \rightarrow }{f_1 }\left( A\right) =\stackrel{ \rightarrow }{f_2 }\left( A\right)=\stackrel{ \rightarrow }{\left( f_1 \cap f_2\right) }\left( A\right) .\square}\)

[Jakub Gurak]

Wprowadźmy notację, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R}\) relacją w zbiorze \(\displaystyle{ X}\), a \(\displaystyle{ A}\) podzbiorem zbioru \(\displaystyle{ X}\), to przez \(\displaystyle{ R_{|A}}\) będziemy oznaczać zawężenie relacji \(\displaystyle{ R}\) do zbioru \(\displaystyle{ A}\), tzn. \(\displaystyle{ R_{|A}:=R\cap (A\times A)}\). ...udowodniłem, ż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}.}\)

Tutaj TU, rozważałem (dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)), rozważałem tzw. ograniczenie relacji w dziedzinie do zbioru \(\displaystyle{ A\subset X,}\) oznaczone jako \(\displaystyle{ \left( A|R\right)}\), a także rozważałem ograniczenie relacji \(\displaystyle{ R}\) w przeciwdziedzinie do zbioru \(\displaystyle{ B\subset Y}\), oznaczone jako \(\displaystyle{ \left( R|B\right), }\) i udowodniłem prawa:

1) \(\displaystyle{ \left( A|R\right) \cap \left( R|B\right) =R \cap \left( A \times B\right)}\),
2) \(\displaystyle{ \left( A \cap B\right)|R= \left( A|R\right) \cap \left( B|R\right), }\)

i udowodniłem podobne prawo dla zawężeń relacji w przeciwdziedzinie.

Możemy zatem w inny sposób (ale bardzo prosty) udowodnić zacytowany fakt, co wczoraj sobie na dobranoc udowodniłem. Przedstawię teraz ten prosty dowód.


Podajmy najpierw ogólny prosty lemat.

LEMAT:

Dla dowolnej relacji \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), dla zbioru \(\displaystyle{ C\subset X}\), mamy:

\(\displaystyle{ R _{|C}=\left( C|R\right) \cap \left( R|C\right).}\)

PROSTY DOWÓD TEGO FAKTU:

Mamy, na mocy własności 1), mamy:

\(\displaystyle{ \left( C|R\right) \cap \left( R|C\right) =R \cap \left( C \times C\right) =R _{|C}.\square}\)

Przejdźmy do dowodu naszego zacytowanego faktu:

DOWÓD TEGO FAKTU:

Mamy, na mocy lematu powyżej:

\(\displaystyle{ R _{|A \cap B}=\left( \left( A \cap B\right) |R\right) \cap \left( R|\left( A \cap B\right) \right)=, }\)

co jest równe, na mocy własności 2) i analogicznej własności dla zawężeń relacji w przeciwdziedzinie, to jest równe:

\(\displaystyle{ =\left[ \left( A|R\right) \cap \left( B|R\right) \right] \cap \left[ \left( R|A\right) \cap \left( R|B\right) \right]=\left[ \left( A|R\right) \cap \left( R|A\right) \right] \cap \left[ \left( B|R\right) \cap \left( R|B\right) \right] =\left( R _{|A} \right) \cap \left( R _{|B} \right).\square}\)

[Jakub Gurak]

Wczoraj na dobranoc, udowodniłem, że jeśli w zbiorze mamy relację antysymetryczną, oraz gdy mamy podzbiór całego danego zbioru, to zawężenie relacji antysymetrycznej do podzbioru jest relacją antysymetryczną w tym podzbiorze.
Udowodniłem również, że jeśli w zbiorze mamy relację symetryczną, to zawężenie tej relacji symetrycznej do podzbioru całego zbioru jest relacją symetryczną w tym podzbiorze. Przedstawię teraz dowody tych ciekawych faktów.

Przypomnijmy, mamy prawo:
Relacja \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) jest antysymetryczna, dokładnie wtedy, gdy: \(\displaystyle{ R \cap R ^{-1} \subset I_X}\).
Tzn. relacja jest antysymetryczna, gdy jej przekrój z relacją do niej odwrotną leży w przekątnej \(\displaystyle{ I_X}\), bo relacja jest antysymetryczna, gdy jej odbicie względem przekątnej jest puste- dokładniej: odbicie fragmentu relacji leżącej poza przekątną musi być puste, tzn. gdy odbijemy taką relacje względem przekątnej, to po drugiej stronie, w tym samym miejscu, nie będzie ani jednej pary tej relacji, skąd takie odbicie może pokrywać się z daną relacją tylko na przekątnej. Przejdźmy do naszego faktu:

Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R}\) niech będzie relacją antysymetryczną w nim. Niech \(\displaystyle{ A \subset X}\). Wykażemy, że zawężenie \(\displaystyle{ R _{|A}}\) jest relacją antysymetryczną w zbiorze \(\displaystyle{ A}\).

DOWÓD TEGO FAKTU:

Musimy wykazać, że:

\(\displaystyle{ \left( R _{|A} \right) \cap \left( R _{|A} \right) ^{-1} \subset I_A.}\)

Niewątpliwie, mamy:

\(\displaystyle{ \left( R _{|A} \right) \cap \left( R _{|A} \right) ^{-1}= R \cap \left( A \times A\right) \cap \left[ R \cap \left( A \times A\right) \right] ^{-1}= R \cap \left( A \times A\right) \cap R ^{-1} \cap \left( A \times A\right) ^{-1}=}\)

co, na mocy łączności i przemienności operacji przekroju dwóch zbiorów, jest równe:

\(\displaystyle{ = R \cap R ^{-1} \cap \left( A \times A\right) \cap \left( A \times A\right) ^{-1}\stackrel{\left( B \times C\right) ^{-1}= C \times B } {=} R \cap R ^{-1} \cap \left( A \times A\right) \cap \left( A \times A\right)= R \cap R ^{-1} \cap \left( A \times A\right) = }\)

i ponieważ relacja \(\displaystyle{ R}\) jest antysymetryczna, to \(\displaystyle{ R \cap R ^{-1} \subset I_X}\), więc ten zbiór jest podzbiorem zbioru:

\(\displaystyle{ \subset I_X \cap \left( A \times A\right) = I_A.}\)

A zatem relacja \(\displaystyle{ R _{|A}}\) jest antysymetryczna w zbiorze \(\displaystyle{ A.\square}\)

Przejdźmy do naszego drugiego faktu:
Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R}\) niech będzie relacją symetryczną w tym zbiorze, oraz niech \(\displaystyle{ A \subset X}\). Wykażemy, że zawężenie \(\displaystyle{ R _{|A}}\) jest relacją symetryczną w zbiorze \(\displaystyle{ A}\).

Nim to udowodnimy, przypomnijmy, że jeśli \(\displaystyle{ X}\) jest zbiorem, to każdy kwadrat postaci \(\displaystyle{ B \times B}\), gdzie \(\displaystyle{ B \subset X,}\) jest relacją symetryczną, gdyż: \(\displaystyle{ \left( B \times B\right) ^{-1} \stackrel{\left( C \times D\right) ^{-1}= D \times C }= B \times B.}\)
Możemy zatem łatwo udowodnić nasz fakt(zachowując wprowadzone oznaczenia):

DOWÓD TEGO FAKTU:

Zauważmy najpierw, że:

\(\displaystyle{ R _{|A}= R \cap \left( A \times A\right) \subset A \times A, }\)

a więc relacja \(\displaystyle{ R _{|A}}\) jest relacją w zbiorze \(\displaystyle{ A}\).

Ponieważ relacja \(\displaystyle{ R}\) jest symetryczna (z założenia), i kwadrat \(\displaystyle{ \left( A \times A\right)}\) jest, na mocy powyższego faktu, jest relacją symetryczną, więc zawężenie \(\displaystyle{ R _{|A}}\), jako przekrój dwóch relacji symetrycznych, jest relacją symetryczną.\(\displaystyle{ \square}\)

Można też udowodnić, że jeśli w zbiorze \(\displaystyle{ X}\) mamy relację przeciwzwrotną, to zawężenie relacji przeciwzwrotnej do podzbioru jest relacją przeciwzwrotną w tym podzbiorze, tzn.:

Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R}\) jest relacją przeciwzwrotną w zbiorze \(\displaystyle{ X}\), oraz \(\displaystyle{ A \subset X}\), to zawężenie \(\displaystyle{ R _{|A}}\) jest relacją przeciwzwrotną w zbiorze \(\displaystyle{ A.}\)

DOWÓD TEGO FAKTU:

Musimy wykazać, że relacja \(\displaystyle{ R _{|A}}\) jest rozłączna z przekątną \(\displaystyle{ I_A}\).
Wyznaczmy zatem przekrój: \(\displaystyle{ R _{|A} \cap I_A}\). Mamy:

\(\displaystyle{ \left( R _{|A} \right) \cap I _{A} = \left[ R \cap \left( A \times A\right)\right] \cap I_A = \left[ R \cap \left( A \times A\right)\right] \cap \left[ I_X \cap \left( A \times A\right)\right] = }\)

co, na mocy łączności i przemienności operacji przekroju dwóch zbiorów, jest równe:

\(\displaystyle{ =R \cap \left( A \times A\right) \cap \left( A \times A\right) \cap I_X= R \cap \left( A \times A\right) \cap I_X= \left( R \cap I_X\right) \cap \left( A \times A\right) ;}\)

( gdzie ostatnie przejście otrzymujemy na mocy łączności i przemienności operacji przekroju dwóch zbiorów).
Teraz, ponieważ relacja \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\) jest przeciwzwrotna, to jest rozłączna z przekątną \(\displaystyle{ I_X}\), a więc \(\displaystyle{ R \cap I_X= \left\{ \right\}}\) , a więc nasz zbiór jest równy:

\(\displaystyle{ = \left\{ \right\} \cap \left( A \times A\right)=\left\{ \right\},}\)

i relacja \(\displaystyle{ R _{|A}}\) jest relacją przeciwzwrotną w zbiorze \(\displaystyle{ A.\square}\)

Można też łatwo udowodnić, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R}\) jest relacją zwrotną w nim, oraz \(\displaystyle{ A \subset X}\), to zawężenie \(\displaystyle{ R _{|A}}\) jest relacją zwrotną w zbiorze \(\displaystyle{ A}\), czyli zawężenie relacji zwrotnej do podzbioru całego zbioru jest relacją zwrotną w tym podzbiorze- można to bardzo prosto udowodnić.