Zawężenia relacji w dziedzinie i w przeciwdziedzinie do podzbioru

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

Zawężenia relacji w dziedzinie i w przeciwdziedzinie do podzbioru

Post autor: Jakub Gurak » 20 cze 2022, o 20:48

Przypominam:

Jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ R}\) jest dowolną relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), i mamy zbiór \(\displaystyle{ A\subset X}\), to relacja \(\displaystyle{ A|R}\) określona w poniższy sposób:

\(\displaystyle{ (x,y)\in \left( A|R\right) \equiv x\in A \wedge \left( x,y\right) \in R}\),

zwana jest ograniczeniem relacji \(\displaystyle{ R}\) w dziedzinie do zbioru \(\displaystyle{ A.}\)

Równoważnie, możemy tą relację zdefiniować jako:

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

Jest to zbiór tych par z relacji \(\displaystyle{ R}\), których pierwsze współrzędne są elementami zbioru \(\displaystyle{ A}\), a bardziej wymownie jest to przekrój relacji \(\displaystyle{ R}\) z pionowym pasem \(\displaystyle{ A \times Y.}\)

Podobnie, jeśli mamy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), i gdy mamy zbiór \(\displaystyle{ B\subset Y}\), to relacja \(\displaystyle{ R|B}\), relacja złożona z tych par z relacji \(\displaystyle{ R}\), których drugie współrzędne należą do zbioru \(\displaystyle{ B}\), tzn. relacja dana jako:

\(\displaystyle{ \left( x,y\right) \in \left( R|B\right) \equiv \left( x,y\right)\in R \wedge y\in B}\),

zwana jest ograniczeniem relacji \(\displaystyle{ R}\) w przeciwdziedzinie do zbioru \(\displaystyle{ B}\).

Równoważnie możemy tą relację zdefiniować jako:

\(\displaystyle{ \left( R|B\right) = R \cap \left( X \times B\right)}\),

jest to przekrój tej danej relacji \(\displaystyle{ R}\) z poziomym pasem \(\displaystyle{ X \times B.}\)


Udowodniłem wczoraj, że jeśli mamy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), oraz gdy mamy dwa zbiory \(\displaystyle{ A\subset X}\), i gdy mamy zbiór \(\displaystyle{ B\subset Y}\), to przekrój ograniczenia relacji \(\displaystyle{ R}\) w dziedzinie do zbioru \(\displaystyle{ A}\) i ograniczenia tej relacji w przeciwdziedzinie do zbioru \(\displaystyle{ B}\) jest równy przekroju tej relacji z prostokątem \(\displaystyle{ A \times B.}\) Udowodniłem tez, że (dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)) jeśli mamy dwa zbiory \(\displaystyle{ A,B\subset X}\), to mamy prawo:

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

jak i udowodniłem podobne prawo dla zawężeń relacji \(\displaystyle{ R}\) w przeciwdziedzinie. Udowodniłem też, że jeśli mamy (dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)), gdy mamy dwa zbiory \(\displaystyle{ A_1, A_2\subset X}\), to mamy prawo:

\(\displaystyle{ \left( A_1 \cup A_2\right) |R= \left( A_1|R\right) \cup \left( A_2|R\right).}\)

Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), i niech \(\displaystyle{ A\subset X, B\subset Y}\). Wykażemy, że:

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

czyli, że przekrój zawężenia relacji \(\displaystyle{ R}\) w dziedzinie do zbioru \(\displaystyle{ A}\) i zawężenia tej relacji w przeciwdziedzinie do zbioru \(\displaystyle{ B}\) jest równy przekrojowi tej relacji z prostokątem \(\displaystyle{ A \times B}\).
DOŚĆ OCZYWISTY DOWÓD TEGO FAKTU::    
Rozważmy teraz relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), oraz dwa zbiory \(\displaystyle{ A,B\subset X}\). Wykażemy, że:

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

Nim udowodnimy ten bardzo ciekawy fakt, przypomnijmy, że jeśli mamy cztery zbiory \(\displaystyle{ X_1, X_2, Y_1, Y_2;}\) oraz dwa iloczyny kartezjańskie \(\displaystyle{ X_1 \times Y_1}\) i \(\displaystyle{ X_2 \times Y_2,}\) to przekrój tych 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- jest to dość elementarny fakt.

Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO CIEKAWEGO FAKTU:

Mamy:

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


Wykażemy podobny fakt dla ograniczeń relacji w przeciwdziedzinie, tzn. wykażemy, że (dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)), dla dwóch zbiorów \(\displaystyle{ B_1, B_2\subset Y}\), mamy:

\(\displaystyle{ R|\left( B_1 \cap B_2\right) = \left( R|B_1 \right) \cap \left( R|B_2\right) .}\)
PODOBNY DOWÓD, TYLKO OD DRUGIEJ STRONY::    
Wykażemy jeszcze, że (dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)) dla dwóch zbiorów \(\displaystyle{ A_1, A_2\subset X}\), mamy prawo:

\(\displaystyle{ \left( A_1 \cup A_2\right) |R= \left( A_1|R\right) \cup \left( A_2|R\right) .}\)

PROSTY DOWÓD TEGO FAKTU:\(\displaystyle{ }\)

Mamy:

\(\displaystyle{ \left( A_1|R\right) \cup \left( A_2|R\right)= \left[ R \cap \left( A_1 \times Y\right) \right] \cup \left[ R \cap \left( A_2 \times Y\right) \right] =R \cap \left[ \left( A_1 \times Y\right) \cup \left( A_2 \times Y\right) \right] =R \cap \left[ \left( A_1 \cup A_2\right) \times Y \right] = \left( A_1 \cup A_2\right) |R.\square}\)


Na koniec wykażemy, że (dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)), dla zbioru \(\displaystyle{ A\subset X}\), mamy prawo:

\(\displaystyle{ \left( A|R\right) ^{-1}= R ^{-1}|A.}\)

Oto ilustracja, dla relacji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\):

Kod: Zaznacz cały

naforum.zapodaj.net/98e3eb59f1c3.jpg.html
Odbijanie względem przekątnej nie jest moją mocną stroną, ale to zrobiłem:

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \left( A|R\right) ^{-1} =\left[ R \cap \left( A \times Y\right) \right] ^{-1}= R ^{-1} \cap \left( A \times Y\right) ^{-1}\stackrel {\left( B \times C\right) ^{-1} = C \times B }{=} R ^{-1} \cap \left( Y \times A\right) }\),

i ponieważ relacja \(\displaystyle{ R ^{-1}}\) jest relacją z \(\displaystyle{ Y}\) do \(\displaystyle{ X}\), więc to jest równe:

\(\displaystyle{ =R ^{-1}|A. \square}\)

8-) :lol:

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

Re: Zawężenia relacji w dziedzinie i w przeciwdziedzinie do podzbioru

Post autor: Jakub Gurak » 4 lip 2022, o 01:48

Udowodniłem wczoraj prawo dowolnej relacji \(\displaystyle{ R}\) ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\)- dla dwóch zbiorów \(\displaystyle{ B_1,B_2\subset Y}\) mamy prawo:

\(\displaystyle{ R|(B_1 \cup B_2)= \left( R|B_1\right) \cup \left( R|B_2\right) ,}\)

relacja zawężona w przeciwdziedzinie do sumy dwóch podzbiorów zbioru \(\displaystyle{ Y}\) jest równa sumie zaweżeń tej relacji do pierwszego i odpowiednio drugiego podzbioru.

Wykazałem też dziś, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A,B\subset X}\), ta relacja zawężona w dziedzinie do różnicy tych dwóch podzbiorów jest równa róznicy zawezeń, tzn. mamy prawo:

\(\displaystyle{ \left( A \setminus B\right) |R= \left( A|R\right) \setminus \left( B|R\right) }\)

Przedstawię teraz dowody tych ciekawych faktów.


Wykazemy najpierw, że dla relacji \(\displaystyle{ R}\) Z \(\displaystyle{ X }\) do \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ B\subset Y}\), mamy prawo:

\(\displaystyle{ \left( R|B\right) ^{-1}= \left( B|R ^{-1} \right) }\),

tzn. relacja odwrotna do zawężenia relacji \(\displaystyle{ R}\) w przeciwdziedzinie do zbioru \(\displaystyle{ B\subset Y}\) jest zawężeniem relacji odwrotnej w dziedzinie do tego zbioru \(\displaystyle{ B.}\)

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ B|R ^{-1}=\left( \left( B|R ^{-1} \right) ^{-1} \right) ^{-1 }=}\)

i na mocy odpowiedniego udowodnionego (pod koniec postu powyżej) prawa dla relacji odwrotnej do zawężenia relacji w dziedzinie, otrzymujemy, podstawiając za zbiór \(\displaystyle{ A}\) zbiór \(\displaystyle{ B}\), a za relację \(\displaystyle{ R}\) podstawiając relację \(\displaystyle{ R ^{-1}}\), otrzymujemy, że to jest równe:

\(\displaystyle{ =\left( \left( R ^{-1}\right) ^{-1} |B \right) ^{-1}= \left( R|B\right) ^{-1}. \square}\) :lol:


Wykazemy teraz, że mamy prawo relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), (dla dwóch zbiorów) \(\displaystyle{ B_1, B_2\subset Y,}\) mamy:

\(\displaystyle{ R|\left( B_1 \cup B_2\right) = \left( R|B_1\right) \cup \left( R|B_2\right) .}\)

Przypominam w poście powyżej udowodniliśmy prawo relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A_1, A_2 \subset X}\), may:

\(\displaystyle{ \left( A_1 \cup A_2\right) |R = \left( A_1|R\right) \cup \left( A_2|R\right).}\)

To prawo nam się przyda. Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ R|\left( B_1 \cup B_2\right) = \left( R|\left( B_1 \cup B_2\right) ^{-1} \right) ^{-1}=}\)

co jest równe, na mocy faktu udowodnionemu przed chwilą, to jest równe:

\(\displaystyle{ =\left( \left( B_1 \cup B_2\right)|R ^{-1} \right) ^{-1}=}\)

i na mocy przytoczonego parwo, to jest równe:

\(\displaystyle{ =\left[ \left( B_1|R ^{-1}\right) \cup \left( B_2|R ^{-1} \right) \right] ^{-1}=\left( B_1|R ^{-1} \right) ^{-1} \cup \left( B_2|R ^{-1} \right) ^{-1}= \left[ \left( R ^{-1} \right) ^{-1} |B_1 \right] \cup \left[ \left( R ^{-1} \right) ^{-1}| B_2 \right] = \left( R|B_1\right) \cup \left( R|B_2\right) .\square}\) 8-)


I wykazemy jeszcze drugi fakt, prawo relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A,B\subset X}\), wtedy mamy:

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

czyli zawężenie relacji w dziedzinie do różnicy dwóch podzbiorów tej dziedziny jest równe różnicy zawężeń.

Nim to udowodnimy, przypomnijmy prosty fakt, że dla dowolnych trzech zbiorów \(\displaystyle{ X_1, X_2, X_3}\), mamy:

\(\displaystyle{ X_1 \cap \left( X_2 \setminus X_3\right) = \left( X_1 \cap X_2\right) \setminus \left( X_1 \cap X_3\right)}\) ,

jest to prosty fakt. Przejdźmy do naszego dowodu:

DOWÓD TEGO CIEKAWEGO FAKTU:

Mamy:

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

ODPOWIEDZ