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: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

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

Post autor: Jakub Gurak »

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:

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}\):
Obrazek wygasł
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: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

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

Post autor: Jakub Gurak »

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}\)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

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

Post autor: Jakub Gurak »

Przypomnijmy, jeśli \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są zbiorami, a \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to dla dwóch zbiorów \(\displaystyle{ A\subset X, B\subset Y}\) można rozważać ograniczenie tej relacji w dziedzinie do zbioru \(\displaystyle{ A}\), a w przeciwdziedzinie do zbioru \(\displaystyle{ B}\), oznaczane jako \(\displaystyle{ A|R|B}\), i zdefiniowane jako:

\(\displaystyle{ A|R|B=\left\{ \left( x,y\right)\in R: \ \ x\in A, y\in B \right\} }\).

Równoważnie- jest to przekrój tej relacji z pionowym pasem \(\displaystyle{ A \times Y}\) i z poziomym pasem \(\displaystyle{ X \times B}\).

Już w niedzielę tydzień temu udowodniłem takie bardzo przydatne prawo, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A\subset X, B\subset Y,}\) takie ograniczenie tej relacji w dziedzinie do zbioru \(\displaystyle{ A,}\) a w przeciwdziedzinie do zbioru \(\displaystyle{ B,}\) jest równe przekrojowi zawężenia tej relacji w dziedzinie do zbioru \(\displaystyle{ A}\) z zawężeniem tej relacji w przeciwdziedzinie do zbioru \(\displaystyle{ B}\). Wczoraj wykazałem też, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla trzech zbiorów \(\displaystyle{ B_1,B_2\subset Y}\) i \(\displaystyle{ A\subset X}\), mamy prawo:

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

jak i udowodniłem drugie prawo symetryczne do tego.

Udowodniłem też wczoraj również, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla trzech zbiorów \(\displaystyle{ A_1, A_2\subset X, B\subset Y}\) mamy prawo:

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

jaki i udowodniłem prawo symetryczne do tego.

Wczoraj wieczorem udowodniłem na koniec taki bardzo ciekawy fakt, że jeśli mamy relacje \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), oraz mamy cztery zbiory \(\displaystyle{ A,B\subset X, C,D \subset Y}\), to jeśli z tych czterech zbiorów utworzymy wszystkie możliwe zawężenia tej relacji w dziedzinie i przeciwdziedzinie, i weźmiemy przekrój tych czterech zbiorów (bo mamy \(\displaystyle{ 2 \cdot 2=4}\) możliwości ), to jest on równy zawężeniu tej relacji w dziedzinie do przekroju tych dwóch podzbiorów pierwszej osi a w przeciwdziedzinie do przekroju tych dwóch podzbiorów drugiej osi. Przedstawię teraz dowody tych bardzo ciekawych faktów.


Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), niech \(\displaystyle{ A\subset X, B\subset Y}\).

Wykażemy, że \(\displaystyle{ A|R|B = \left( A|R\right) \cap \left( R|B\right)}\),

czyli wykażemy, że przekrój zawężenia tej relacji w dziedzinie do zbioru \(\displaystyle{ A}\) z zawężeniem tej relacji w przeciwdziedzinie do zbioru \(\displaystyle{ B}\) jest równy zawężeniu tej relacji w dziedzinie do zbioru \(\displaystyle{ A}\) a w przeciwdziedzinie do zbioru \(\displaystyle{ B}\).
DOWÓD TEGO INTUICYJNIE OCZYWISTEGO FAKTU::    
Przejdźmy do kolejnego problemu:

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), niech \(\displaystyle{ A\subset X, B\subset Y}\). Wykażemy, że \(\displaystyle{ \left( A|R|B\right) ^{-1}= B| R ^{-1}|A.}\)

DOWÓD TEGO FAKTU:

Mamy, na mocy faktu udowodnionego przed chwilą :

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


Dalej, niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Rozważmy trzy zbiory \(\displaystyle{ B_1, B_2\subset Y}\) i \(\displaystyle{ A\subset X}\). Wykażemy prawo:

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

Oto ilustracja tego prawa:\(\displaystyle{ \\ }\)
Zawężenia relacji w dziedzinie i przeciwdziedzinie- suma .jpg
\(\displaystyle{ \\}\)
Przejdźmy do dowodu tego faktu:

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \left( A|R|B_1\right) \cup \left( A|R|B_2\right)= \left[ \left( A|R\right) \cap \left( R|B_1\right) \right] \cup \left[ \left( A|R\right) \cap \left( R|B_2\right) \right] = \left( A|R\right) \cap \left[ \left( R|B_1\right) \cup \left( \left( R|B_2\right) \right) \right] = \left( A|R\right) \cap \left[ R| \left( B_1 \cup B_2\right) \right]= A|R| \left( B_1 \cup B_2\right) ,}\)

gdzie przedostatnia równość wynika z prawa udowodnionego w poście powyżej, a pozostałe równości z pierwszego prawa udowodnionego w tym poście, co kończy dowód.\(\displaystyle{ \square}\)

Wykażemy teraz prawo symetryczne do tego, tzn.:

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y.}\) Rozważmy trzy zbiory \(\displaystyle{ A_1, A_2\subset X, B\subset Y.}\) Wykażemy prawo:

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

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \left( A_1 \cup A_2\right) |R|B = \left[ \left( \left( A_1 \cup A_2\right) |R|B \right) ^{-1} \right] ^{-1} = \left[ B|R ^{-1} | \left( A_1 \cup A_2\right) \right] ^{-1}= }\)

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

\(\displaystyle{ =\left[ \left( B|R ^{-1}|A_1 \right) \cup \left( B|R ^{-1}|A_2 \right) \right] ^{-1}= \left( B|R ^{-1}|A_1 \right) ^{-1} \cup \left( B|R ^{-1}|A_2 \right) ^{-1}= \left[ A_1| \left( R ^{-1} \right) ^{-1} |B\right] \cup \left[ A_2|\left( R ^{-1}\right) ^{-1}|B \right] = \left( A_1|R|B \right) \cup \left( A_2|R|B\right). \square}\)


Następny fakt:

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Rozważmy trzy zbiory \(\displaystyle{ A_1, A_2\subset X, B\subset Y.}\) Wykażemy prawo:

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

Oto ilustracja tego faktu:\(\displaystyle{ \\}\)
Zawężenia relacji w dziedzinie i przeciwdziedzinie- przekroje .jpg
\(\displaystyle{ \\}\)
DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \left( A_1|R|B\right) \cap \left( A_2|R|B\right) = \left[ \left( A_1|R\right) \cap \left( R|B\right) \right] \cap \left[ \left( A_2|R\right) \cap \left( R|B\right) \right]= }\)

co jest równe, na mocy przemiienności i łączności przekroju, to jest równe:

\(\displaystyle{ = \left[ \left( A_1|R\right) \cap \left( A_2|R\right) \right] \cap \left[ \left( R|B\right) \cap \left( R|B\right) \right]= \left[ \left( A_1|R\right) \cap \left( A_2|R\right) \right] \cap R|B = }\)

a to jest równe, na mocy jednego z praw udowodnionego w postach powyżej, to jest równe:

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

Wykażemy również prawo symetryczne do tego, tzn.:

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Rozważmy trzy zbiory:\(\displaystyle{ B_1,B_2\subset Y}\) i \(\displaystyle{ A\subset X}\). Wykażemy prawo:

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

DOWÓD TEGO FAKTU:

Mamy:

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

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

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


Pozostał nam do wykazania ostatni fakt.

Rozważmy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Rozważmy cztery zbiory \(\displaystyle{ A,B\subset X}\); \(\displaystyle{ C,D\subset Y.}\) Rozważmy wszystkie możliwe zawężenia tej relacji pomiędzy tymi czterema zbiorami- czyli z \(\displaystyle{ A}\) do \(\displaystyle{ C}\), z \(\displaystyle{ A}\) do \(\displaystyle{ D}\), z \(\displaystyle{ B}\) do \(\displaystyle{ C}\) i z \(\displaystyle{ B}\) do \(\displaystyle{ D}\). Rozważmy przekrój tych czterech zawężeń. Wykażemy, że ten przekrój jest równy zawęzeniu tej relacji w dziedzinie do przekroju tych dwóch podzbiorów pierwszej osi, a w przeciwdziedzinie do przekroju tych dwóch podzbiorów drugiej osi, tzn. wykażemy prawo:

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

Oto ilustracja tego ciekawego faktu: \(\displaystyle{ \\}\)
Zawężenia relacji w dziedzinie i przeciwdziedzinie- przekroje- cztery zbiory.jpg
\(\displaystyle{ \\}\)

DOWÓD TEGO BARDZO CIEKAWEGO FAKTU:

Mamy, na mocy ostatnich dwóch faktów udowodnionych przed chwilą:

\(\displaystyle{ \left( A \cap B\right)|R| \left( C \cap D\right) = \left[ A|R| \left( C \cap D\right) \right] \cap \left[ B|R| \left( C \cap D\right) \right] = \left[ \left( A|R|C\right) \cap \left( A|R|D\right) \right] \cap \left[ \left( B|R|C\right) \cap \left( B|R|D\right) \right] .\square}\) 8-) :lol:
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 1 paź 2022, o 19:26to dla dwóch zbiorów \(\displaystyle{ A\subset X, B\subset Y}\) można rozważać ograniczenie tej relacji w dziedzinie do zbioru \(\displaystyle{ A}\), a w przeciwdziedzinie do zbioru \(\displaystyle{ B}\), oznaczane jako \(\displaystyle{ A|R|B}\), i zdefiniowane jako:

\(\displaystyle{ A|R|B=\left\{ \left( x,y\right)\in R: \ \ x\in A, y\in B \right\} }\).

Równoważnie- jest to przekrój tej relacji z pionowym pasem \(\displaystyle{ A \times Y}\) i z poziomym pasem \(\displaystyle{ X \times B}\).
Wprowadzanie nowego oznaczenia tylko po to, by wprowadzić nowe oznaczenie jest bez sensu. Przecież \(\displaystyle{ A|R|B=R\cap(A\times B)}\), a wszystkie "bardzo ciekawe własności nowego zupełnie zbędnego oznaczenia" to proste i dobrze znane własności podstawowych działań mnogościowych.

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

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

Post autor: Jakub Gurak »

Jan Kraszewski pisze: 1 paź 2022, o 20:11 Wprowadzanie nowego oznaczenia tylko po to, by wprowadzić nowe oznaczenie jest bez sensu. Przecież \(\displaystyle{ A|R|B=R\cap(A\times B)}\),
To nie mój wymysł, w książce "Logike formalna" Borkowskiego wprowadzono takie oznaczenie- a ja lubię udowadniać wszelakie własności pojęć. Poza tym, z tym, że to jest bez sensu, to się nie zgodzę- jest to przekrój dwóch relacji (określonego rodzaju), i nadano temu przekrojowi nowe oznaczenie- ma to pewien sens, aby pod tym oznaczeniem rozumieć tego rodzaju przekroje mnogościowe. Bardziej raczej jest rzecz w tym, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A \subset X, B \subset Y}\) można zapytać czy zachodzą równości :

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

bo przecież zawężenie relacji w dziedzinie do zbioru \(\displaystyle{ A}\), to też jest relacja z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), więc można ją zawęzić w przeciwdziedzinie do zbioru \(\displaystyle{ B}\), otrzymując relacje z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), a relacja obustronnie zawężona \(\displaystyle{ A|R|B }\) to też jest relacja z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), więc można badać równość tych dwóch relacji; i podobnie w drugą stronę.

To oznaczenie, dla tego dwustronnego zawężenia, może wyglądać na trochę zbędne, względem tych dwóch zawężeń jednostronnych, ale o tym Pan nic nie mówił. Ja zauważyłem to dopiero wtedy, gdy pisałem tamten post- już po przeprowadzenie dowodów, które wtedy pisałem. Nie udowadniałem takich praw (jako to fakty proste i mniej ciekawe), aczkolwiek są to potrzebne fakty, aby nie było tutaj kolizji oznaczeń. A tego oznaczenia, to ja sam nie wprowadzałem- w książce "Logika formalna" Borkowskiego wprowadzili je ( i nie skupiali się na tym), ale ja trochę tak- gdyż lubię udowadniać wszelakie nowe (jak dla mnie) własności pojęć. 8-)


Wykazałem wczoraj, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A,B \subset Y}\), mamy prawo:

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

tzn. zawężenie relacji w przeciwdziedzinie do różnicy dwóch podzbiorów drugiej osi jest równe różnicy zawężeń.

Wykazałem też, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A,B \subset X}\), mamy prawo:

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

- zawężenie relacji w dziedzinie do różnicy symetrycznej dwóch podzbiorów pierwszej osi jest równe różnicy symetrycznej zawężeń.

I wykazałem również symetryczny do tego fakt z różnicą symetryczną dla zawężeń relacji w przeciwdziedzinie . Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y.}\) Rozważmy dwa zbiory \(\displaystyle{ A,B \subset Y}\). Wykażemy prawo:

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

OTO ILUSTRACJA TEGO CIEKAWEGO FAKTU:\(\displaystyle{ \\}\)
Róznica zawężeń reklacji w przeciwdziedzinie.jpg
\(\displaystyle{ \\}\)

Nim to udowodnimy, przypomnijmy:

Dla relacji z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A,B \subset X}\), mamy prawo:

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

który to fakt udowodniłem w jednym z postów powyżej.

Przejdźmy do dowodu naszego faktu. Oto:

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ R|\left( A \setminus B\right)= \left[ \left( R|\left( A \setminus B\right)\right) ^{-1} \right] ^{-1}= \left[ \left( A \setminus B\right) | R ^{-1} \right] ^{-1} =}\)

co jest równe, na mocy przytoczonego faktu, to jest równe:

\(\displaystyle{ \left[ \left( A| R ^{-1} \right) \setminus \left( B| R ^{-1} \right) \right] ^{-1}=}\)

i ponieważ relacja odwrotna do różnicy dwóch relacji jest równa różnicy relacji odwrotnych, więc to jest równe:

\(\displaystyle{ = \left( A| R ^{-1} \right) ^{-1} \setminus \left( B| R ^{-1} \right) ^{-1}= \left[ \left( R ^{-1} \right) ^{-1}|A \right] \setminus \left[ \left( R ^{-1} \right) ^{-1} |B \right] = \left( R|A\right) \setminus \left( R|B\right).\square}\)


Przejdźmy do następnego problemu:

Rozważmy relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Rozważmy dwa zbiory \(\displaystyle{ A,B \subset X}\). Wykażemy prawo:

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

czyli wykażemy, że zawężenie relacji w dziedzinie do różnicy symetrycznej dwóch podzbiorów pierwszej osi jest równe różnicy symetrycznej zawężeń.

OTO ILUSTRACJA TEGO FAKTU:
\(\displaystyle{ \\}\)
Różnica symetryczna zawężeń relacji w dzedzinie.jpg
\(\displaystyle{ \\}\)
I oto:

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \left( A\oplus B\right) |R= \left( A \cup B \setminus A \cap B\right) |R= \left[ \left( A \cup B\right)|R \right] \setminus \left[ \left( A \cap B\right)|R \right] = }\)

= co jest równe, na mocy praw podanych w postach powyżej, więc to jest równe:

\(\displaystyle{ \left[ \left( A|R\right) \cup \left( B|R\right) \right] \setminus \left[ \left( A|R\right) \cap \left( B|R\right) \right] \stackrel{ C\oplus D= \left( C \cup D\right) \setminus \left( C \cap D\right) } {=} \left( A|R\right) \oplus \left( B|R\right).\square}\)

I ostatni nasz problem:

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Rozważmy dwa zbiory \(\displaystyle{ A,B \subset Y}\). Wykażemy prawo relacji:

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

Nim to zrobimy, przypomnijmy, że jak mamy dwa zbiory, oraz dwie relacje między nimi, to relacja odwrotna do różnicy symetrycznej tych dwóch relacji jest równa różnicy symetrycznej relacji odwrotnych- jest to prosty fakt.

Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ R|\left( A\oplus B\right) = \left[ \left( R| \left( A\oplus B\right) \right) ^{-1} \right] ^{-1}= \left( \left( A\oplus B\right) | R ^{-1} \right) ^{-1}= }\)

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

\(\displaystyle{ =\left[ \left( A| R^{-1} \right) \oplus \left( B|R ^{-1} \right) \right] ^{-1}= }\)

i ponieważ relacja odwrotna do różnicy symetrycznej dwóch relacji jest różnicą symetryczną relacji odwrotnych, więc to jest równe:

\(\displaystyle{ \left( A|R ^{-1} \right) ^{-1} \oplus \left( B| R ^{-1} \right) ^{-1}= \left[ \left( R ^{-1} \right) ^{-1} |A \right] \oplus \left[ \left( R ^{-1} \right) ^{-1}|B \right] = \left( R|A\right) \oplus \left( R|B\right). \square}\) 8-)
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 22 lis 2022, o 23:38To nie mój wymysł, w książce "Logike formalna" Borkowskiego wprowadzono takie oznaczenie
To jeszcze nie powoduje, że to oznaczenie ma sens.
Jakub Gurak pisze: 22 lis 2022, o 23:38To oznaczenie, dla tego dwustronnego zawężenia, może wyglądać na trochę zbędne, względem tych dwóch zawężeń jednostronnych, ale o tym Pan nic nie mówił. Ja zauważyłem to dopiero wtedy, gdy pisałem tamten post- już po przeprowadzenie dowodów, które wtedy pisałem. Nie udowadniałem takich praw (jako to fakty proste i mniej ciekawe), aczkolwiek są to potrzebne fakty, aby nie było tutaj kolizji oznaczeń. A tego oznaczenia, to ja sam nie wprowadzałem- w książce "Logika formalna" Borkowskiego wprowadzili je ( i nie skupiali się na tym), ale ja trochę tak- gdyż lubię udowadniać wszelakie nowe (jak dla mnie) własności pojęć. 8-)
Wprowadzanie nowych oznaczeń tylko po to, żeby dobrze znane fakty zapisać jeszcze raz, używając tych nowych znaczków jest matematycznie bezcelowe, bo matematyka to byty, a nie oznaczenia.

Oczywiście każdy może lubić co chce i innym nic do tego, ale skoro decydujesz się upubliczniać swoje preferencje na forum (w formie tak naprawdę bardziej pasującej do bloga niż do forum), to w naturalny sposób poddajesz swoje upodobania ocenie. I jak po raz kolejny czytam o "bardzo ciekawych faktach", które są w rzeczywistości elementarnymi własnościami, to trochę zgrzytam zębami.

JK

PS
A jeśli chodzi o dowody z powyższego posta (pokazywanie własności obcięć w przeciwdziedzinie relacji bo wcześniejszym dowiedzeniu tych własności w dziedzinie), to do od swojego studenta oczekiwałbym, że całość załatwi jednym słowem: "Analogicznie".
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

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

Post autor: Jakub Gurak »

Ja mam ambicję użyć praw relacji odwrotnej.
A mogę zapytać dlaczego są to "elementarne fakty"??- na jakiej zasadzie by je Pan uzasadnił :?:
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 23 lis 2022, o 10:52Ja mam ambicję użyć praw relacji odwrotnej.

Kod: Zaznacz cały

www.youtube.com/watch?v=qgu52a5Utbw
Jak pisałem: co kto lubi. Co nie zmienia mojej uwagi z post scriptum poprzedniego posta.
Jakub Gurak pisze: 23 lis 2022, o 10:52A mogę zapytać dlaczego są to "elementarne fakty"??
A dlaczego wejście na Ślężę

Kod: Zaznacz cały

pl.wikipedia.org/wiki/%C5%9Al%C4%99%C5%BCa
nie jest wyczynem alpinistycznym? Oczywiście, gdy na Ślężę wejdzie przedszkolak, to jest to dla niego duży wyczyn, godny pochwały. Gdyby takie dowody przedstawiał uczeń szkoły średniej, byłoby to godne pochwały.
Jakub Gurak pisze: 23 lis 2022, o 10:52na jakiej zasadzie by je Pan uzasadnił :?:
Wszystkie dowody w tym wątku to bezpośrednie zastosowanie elementarnych praw rachunku zbiorów.

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

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

Post autor: Jakub Gurak »

Może Pan podać przykład :?:
Ja podejrzewam, że takie dowody ( pewnie robione wprost z definicji) będą pewnie prostsze od moich, ale chciałbym (przynajmniej jeden)) taki dowód zobaczyć, poproszę. :roll:
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 23 lis 2022, o 19:53 Może Pan podać przykład
Przykład czego?

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

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

Post autor: Jakub Gurak »

Przykład dowodu jednego z tych moich faktów.
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

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

Post autor: Jan Kraszewski »

Wszystkie te dowody są podobne do tego:
Jakub Gurak pisze: 20 cze 2022, o 20:48\(\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:

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}\)
w którym korzystasz z rozdzielności przekroju względem sumy i rozdzielności iloczynu kartezjańskiego względem sumy, czyli dwóch bardzo elementarnych własności.

Dodatkowo wszystkie dowody związane z przeciwdziedziną relacji są matematycznie identyczne jak dowody związane z dziedziną relacji, więc zasługują wyłącznie na najkrótszy możliwy dowód, czyli "Analogicznie".

JK
ODPOWIEDZ