Zawężenia relacji

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1011
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Zawężenia relacji

Post autor: Jakub Gurak » 9 lut 2021, o 01:47

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ść:    
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. :lol: :lol:
Ostatnio zmieniony 9 lut 2021, o 01:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nie używaj Caps Locka.

Jakub Gurak
Użytkownik
Użytkownik
Posty: 1011
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Re: Zawężenia relacji

Post autor: Jakub Gurak » 4 cze 2021, o 01:32

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}\) :lol:

Jakub Gurak
Użytkownik
Użytkownik
Posty: 1011
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Re: Zawężenia relacji

Post autor: Jakub Gurak » 2 lut 2022, o 13:53

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

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::    
8-) :D

Jakub Gurak
Użytkownik
Użytkownik
Posty: 1011
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Re: Zawężenia relacji

Post autor: Jakub Gurak » 22 cze 2022, o 20:21

Jakub Gurak pisze:
9 lut 2021, o 01:47
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}\) :lol:

ODPOWIEDZ