Przeciwobraz zbioru przez relację

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

Przeciwobraz zbioru przez relację

Post autor: Jakub Gurak »

Pytanie czym jest, jak w temacie, przeciwobraz zbioru, ale przez dowolną relację. Dzisiaj na ekonomii matematycznej zaskoczyło mnie to pojęcie, pierwsze słyszę. Czyli:

Dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ B\subset Y}\), czym jest przeciwobraz \(\displaystyle{ R ^{-1} (B) }\):?: Czy to jest \(\displaystyle{ \left[ R \cap (X \times B)\right] _L}\), czyli rzut relacji \(\displaystyle{ R \cap (X\times B)}\) na oś \(\displaystyle{ x}\) :?: Dobrze myślę :?: To ciekawe.
Jan Kraszewski
Administrator
Administrator
Posty: 34555
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Przeciwobraz zbioru przez relację

Post autor: Jan Kraszewski »

Dobrze myślisz. Można to też zapisać podobnie jak dla funkcji:

\(\displaystyle{ R^{-1}[C]=\{x\in X:(\exists y\in C)\left\langle x,y\right\rangle\in R \}}\).

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

Re: Przeciwobraz zbioru przez relację

Post autor: Jakub Gurak »

Jakieś ogólne własności ma ten przeciwobraz?? Ja zauważam, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla \(\displaystyle{ B\subset Y}\): mamy \(\displaystyle{ R^{-1}(B)\subset R_L}\), monotoniczność przeciwobrazu zbiorów względem inkluzji, oraz jeśli \(\displaystyle{ B\supset R_P,}\) to \(\displaystyle{ R^{-1}(B)=R_L}\).
Dowód ostatniej własności:    
Podejrzewam, że taki przeciwobraz ma podobne własności jak przeciwobraz zbioru dla funkcji. Dobrze myślę :?: Jakie ma jeszcze własności ?
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1431
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 70 razy
Pomógł: 84 razy

Re: Przeciwobraz zbioru przez relację

Post autor: Jakub Gurak »

Jakub Gurak pisze: 25 lut 2021, o 22:28 Podejrzewam, że taki przeciwobraz ma podobne własności jak przeciwobraz zbioru dla funkcji. Dobrze myślę :?:
Otóż, nie do końca, dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla dwóch zbiorów \(\displaystyle{ A,B\subset Y}\), przeciwobraz przez tą relację przekroju tych dwóch zbiorów może być innym zbiorem niż przekrój przeciwobrazów; uzasadnili to w książce " LOGIKA FORMALNA" Ludwika Borkowskiego, jednakże podając kontrprzykład relacji na zbiorze ludzi. Ja podam, odpowieni do tego kontrprzykładu, podam bardziej matematyczny kontrprzykład:

KONTRPRZYKŁAD FORMALNY:

Niech \(\displaystyle{ X=\left[ 0,2\right] \subset \RR}\); niech \(\displaystyle{ Y=\left[ 0,3\right] \subset \RR}\). Niech \(\displaystyle{ R=\left[ 0,1\right] \times \left( \left[ 0,1\right] \cup \left[ 2,3\right] \right)}\) . Niech \(\displaystyle{ A=\left[ 0,1\right]}\) , \(\displaystyle{ B= \left[ 2,3\right]}\) . Wtedy :

\(\displaystyle{ A \cap B=\emptyset}\), a zatem \(\displaystyle{ R ^{-1}\left( A \cap B\right)= R ^{-1} \left( \emptyset\right) = \left[ R \cap \left( X \times \emptyset\right) \right] _L= \emptyset_L= \emptyset}\). Tymczasem:

\(\displaystyle{ R ^{-1}\left( A\right) = \left[ \left[ 0,1\right] \times \left( \left[ 0,1\right] \cup \left[ 2,3\right] \right) \cap \left[ 0,2\right] \times \left[ 0,1\right] \right] _L= \left( \left[ 0,1\right] \times \left[ 0,1\right] \right)_L= \left[ 0,1\right] .}\)

Podobnie \(\displaystyle{ R ^{-1}\left( B\right) = \left( \left[ 0,1\right] \times \left[ 2,3\right] \right) _L= \left[ 0,1\right] . }\)

A zatem: \(\displaystyle{ R ^{-1}(A) \cap R ^{-1}(B) = \left[ 0,1\right] \neq \emptyset = R ^{-1} \left( A \cap B\right) .\square}\) :D


Przypominam:

Jeśli \(\displaystyle{ R}\) jest relacją ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\), a \(\displaystyle{ x\in R_L}\), to zbiór:

\(\displaystyle{ \stackrel { \rightarrow }{R} (x):=\left\{ y\in Y: \ \left( x,y\right) \in R \right\} }\),

czyli zbiór tych elementów drugiej osi \(\displaystyle{ Y,}\) do których element \(\displaystyle{ x}\) pozostaje w relacji, nazywamy zbiorem następników elementu \(\displaystyle{ x}\) względem relacji \(\displaystyle{ R,}\) i oznaczamy jako \(\displaystyle{ \stackrel{ \rightarrow }{R} (x)}\). Jest to przekrój odcinka pionowego w punkcie \(\displaystyle{ x}\) przeciętego z relacją i rzut takiego przecięcia na oś \(\displaystyle{ Y.}\)

Analogicznie, dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla \(\displaystyle{ y\in R_P}\) zbiór:

\(\displaystyle{ \stackrel{ \leftarrow }{R} \left( y\right):= \left\{ x\in X: \ \left( x,y\right)\in R \right\} }\),

nazywamy zbiorem poprzedników elementu \(\displaystyle{ y}\) względem relacji \(\displaystyle{ R}\). Jest to odcinek poziomy w punkcie \(\displaystyle{ y}\) przecięty z relacją \(\displaystyle{ R}\) i rzut takiego przecięcia na oś \(\displaystyle{ X}\).

Udowodniłem, w piątkowe popołudnie, że jeśli mamy dowolną relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), oraz parę \(\displaystyle{ (a,b)\in R}\) tej relacji (wtedy możemy odzyskać obydwie współrzędne takiej pary), i wtedy przekrój zbioru następników elementu \(\displaystyle{ a}\) względem tej relacji (a właściwie odpowiadającemu mu podzbioru iloczynu kartezjńskiego \(\displaystyle{ X \times Y}\), którym jest odpowiadający mu odcinek pionowy w punkcie \(\displaystyle{ a}\)) oraz zbioru poprzedników elementu \(\displaystyle{ b}\) (a właściwie chodzi o odcienek poziomy, będący podzbiorem iloczynu kartezjańskiego \(\displaystyle{ X \times Y}\) , odcinek poziomy w punkcie \(\displaystyle{ b}\) ), wtedy przekrój takich zbiorów jest zbiorem jednopunktowym złożonym z pary \(\displaystyle{ \left( a,b\right)}\). Udowodniłem też, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla \(\displaystyle{ x\in R_L}\) , wtedy zbiór następników elementu \(\displaystyle{ x}\) względem tej relacji jest równy obrazowi zbioru jednopunktowego \(\displaystyle{ \left\{ x\right\}}\). Wykazałem też, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ B\subset Y,}\) wtedy przeciwobraz tego zbioru przez tą relację jest równy obrazowi tego zbioru, ale przez relację do niej odwrotną; i podobnie dla zbioru \(\displaystyle{ A\subset X}\), wtedy obraz tego zbioru przez relację daną jest równy przeciwobrazowi tego zbioru, ale przez relację do niej odwrotną. Wykazałem też w sobotę, że dla \(\displaystyle{ n=2,3,\ldots}\) i dla \(\displaystyle{ n}\) zbiorów \(\displaystyle{ X_1,X_2,\ldots, X_n,}\) jeśli mamy relację \(\displaystyle{ n}\) członową między tymi zbiorami, to ta relacja jest podzbiorem iloczynu kartezjańskiego wszystkich dziedzin tej relacji, tzn. iloczynu kartezjańskiego pierwszej dziedziny tej relacji, drugiej dziedziny tej relacji , ..., \(\displaystyle{ n}\)-tej dziedziny tej relacji. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ X,Y}\) będą zbiorami , a \(\displaystyle{ R}\) niech będzie dowolną relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Niech \(\displaystyle{ \left( a,b\right) \in R}\)( wtedy możemy odzyskać obydwie współrzędne takiej pary), wtedy \(\displaystyle{ a\in R_L}\) i \(\displaystyle{ b\in R_P}\), i wykażemy równość:

\(\displaystyle{ \left( \left\{ a\right\} \times \stackrel{ \rightarrow }{R} (a)\right)
\cap \left( \stackrel{ \leftarrow }{R} (b) \times \left\{ b\right\}\right) =\left\{ \left( a,b\right) \right\} .}\)


Nim udowodnimy ten bardzo ciekawy fakt, przypomnijmy, prosty fakt, że jeśli mamy cztery zbiory \(\displaystyle{ A,B,C,D}\), oraz dwa iloczyny kartezjańskie \(\displaystyle{ A \times B}\) i \(\displaystyle{ C \times D}\), to przekrój takich 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 prosty fakt.

Przejdźmy do dowodu naszego faktu:

Zbiór po lewej stronie równości jest równy( )na mocy powyzej przytoczonego faktu) :

\(\displaystyle{ =\left( \left\{ a\right\} \cap \stackrel{ \leftarrow }{R} (b)\right) \times \left( \stackrel{ \rightarrow }{R} (a) \cap\left\{ b\right\}\right) =}\)

i ponieważ \(\displaystyle{ (a,b)\in R}\) , to \(\displaystyle{ a \in \stackrel{ \leftarrow } {R} (b)}\), oraz \(\displaystyle{ b\in \stackrel{ \rightarrow }{R} (a)}\), bo \(\displaystyle{ \left( a,b\right) \in R}\). A zatem to jest równe:

\(\displaystyle{ =\left\{ a\right\} \times \left\{ b\right\} =\left\{ \left( a,b\right) \right\} .\square}\)


Przypomnijmy: dla relacji \(\displaystyle{ R}\) Z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ A\subset X,}\) obraz zbioru \(\displaystyle{ A,}\) oznaczany jako \(\displaystyle{ R(A),}\) jest dany jako:

\(\displaystyle{ R(A)= \left[ R \cap \left( A \times Y\right) \right]_P}\),

czyli, jest to przekrój pionowego pasa \(\displaystyle{ A \times Y}\) z naszą relacją, i rzut takiego przecięcia na óś \(\displaystyle{ Y. }\)

Wykażemy teraz, że dla relacji \(\displaystyle{ R }\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla \(\displaystyle{ x\in R_L}\), mamy równość:

\(\displaystyle{ \stackrel{ \rightarrow } {R} (x) =R\left( \left\{ x\right\} \right) ,}\)

czyli, zbiór nastepników elementu \(\displaystyle{ x,}\) względem tej relacji, jest równy obrazowi zbioru jednopunktowego \(\displaystyle{ \left\{ x\right\} .}\)
DOWÓD TEGO FAKTU::    
Również, dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla \(\displaystyle{ x\in R _L}\), wtedy: \(\displaystyle{ \stackrel { \rightarrow }{R} (x) = \stackrel { \leftarrow }{R ^{-1} } (x),}\)

czyli zbiór następników elementu \(\displaystyle{ x,}\) względem relacji danej, jest równy zbiorowi poprzedników tego elementu, ale względem relacji do niej odwrotnej.
DOWÓD TEGO FAKTU::    
Również, dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla \(\displaystyle{ x\in R_P}\), mamy:

\(\displaystyle{ \stackrel { \leftarrow }{R} (x) = \stackrel{ \rightarrow }{R ^{-1} } (x),}\)

czyli, zbiór poprzedników elementu \(\displaystyle{ x,}\) wzgledem relacji danej, jest równy zbiorowi jego następników, ale względem relacji do niej odwrotnej .

Dowód tego faktu łatwo wynika z faktu udowodnionego powyżej, oraz z prawa relacji (chyba mojego ulubionego ): \(\displaystyle{ \left( R ^{-1}\right) ^{-1}=R.}\)


Wykażemy teraz, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ B\subset Y}\), mamy:

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

( :!: proszę teraz, broń Boże nie podstawiać za to \(\displaystyle{ S}\), bo wyjdzie formalna oczywistość),

czyli przeciwobraz zbioru \(\displaystyle{ B,}\) przez relację daną, jest równy obrazowi tego zbioru, ale przez relację do niej odwrotną.

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ S(B)= \left[ S \cap \left( B \times X\right) \right] _P= \left[ R ^{-1} \cap \left( B \times X\right) \right]_P\stackrel{\left( X \times B\right) ^{-1} =B \times X }= \left[ R ^{-1} \cap \left( X \times B \right) ^{-1} \right] _P= \left[ R \cap \left( X \times B\right) \right] ^{-1}_P= \left[ R \cap \left( X \times B\right) \right] _L= R ^{-1} (B)= \\ =S(B),}\)

gdzie \(\displaystyle{ S= R ^{-1} . \square}\) :lol:


I podobnie, dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ A\subset X}\),mamy: \(\displaystyle{ R(A) =S ^{-1} (A)}\), gdzie \(\displaystyle{ S= R ^{-1},}\)

tzn. obraz zbioru \(\displaystyle{ A}\), przez relację daną, jest równy przeciwobrazowi tego zbioru, ale przez relację do niej odwrotną.

DOWÓD TEGO FAKTU:

Zbiór \(\displaystyle{ S ^{-1}(A)}\) jest równy, na mocy faktu udowodnionego przed chwilą, ten zbiór jest równy:

\(\displaystyle{ =T(A)}\), gdze \(\displaystyle{ T= S ^{-1},}\)

A wtedy:

\(\displaystyle{ T= S ^{-1}= \left( R ^{-1} \right) ^{-1}= R}\).

A zatem ten (poprzedni) zbiór jest równy:

\(\displaystyle{ =R(A)}\),

czyli \(\displaystyle{ S ^{-1} (A)= R(A) }\), gdzie \(\displaystyle{ S=R ^{-1} . \square}\)


Rozwazmy jeszcze, dla \(\displaystyle{ n=2,3,\ldots}\) oraz dla \(\displaystyle{ n}\) zbiorów \(\displaystyle{ X_1,X_2,\ldots, X_n,}\) rozważmy relację \(\displaystyle{ n}\)-członową \(\displaystyle{ R\subset X_1 \times X_2 \times \ldots \times X_n}\), który to iloczyn kartezjański będziemy dalej zapisywać jako (bo chodzi o zbiór \(\displaystyle{ n}\)-ek, a nie o wielokrotny binarny iloczyn kartezjański ), dalej będziemy go zapisywać jako: \(\displaystyle{ \prod_{j=1}^{n} X_j.}\)

Niech, dla dowolnego ustalonego \(\displaystyle{ i=1,2,\ldots, n}\), niech:

\(\displaystyle{ D_i=\left\{ x\in X_i: \ \bigvee \limits_ {\left( x_1, x_2, \ldots, x_n\right) } \left[ x=x_i \wedge \left( x_1, x_2,\ldots, x_n\right) \in R \right] \right\}}\) ,

jest to zbiór \(\displaystyle{ i}\)-ych współrzednych układów uporządkowanych tej relacji, będziemy ten zbiór nazywać \(\displaystyle{ i}\)-a dziedziną tej relacji.

Wykazemy, że:

\(\displaystyle{ R\subset \prod_{i=1}^{n} D_i}\),

czyli relacja \(\displaystyle{ R}\) jest podzbiorem iloczynu kartezjańskiego pierwszej dziedziny tej relacji , jej drugiej dziedziny,\(\displaystyle{ \ldots}\), jej \(\displaystyle{ n}\)-ej dziedziny.

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ \left( x_1,x_2,\ldots, x_n\right) \in R}\). Niech \(\displaystyle{ i=1,2,\ldots, n}\). Wtedy \(\displaystyle{ x:=x_i \in X_i, }\) i \(\displaystyle{ \left( x_1, x_2,\ldots, x_n\right) \in R}\), skąd, na podstawie definicji \(\displaystyle{ i}\)-ej dziedziny \(\displaystyle{ D_i}\) wnioskujemy, że \(\displaystyle{ x=x_i \in D_i}\), i otrzymujemy (z dowolności wyboru indeksu \(\displaystyle{ i}\) ) otrzymujemy, że dla każdego \(\displaystyle{ i=1,2,\ldots,n}\): \(\displaystyle{ x_i \in D_i}\), a zatem \(\displaystyle{ \left( x_1, x_2,\ldots, x_n\right) \in D_1 \times D_2 \times \ldots \times D_n= \prod_{i=1}^{n} D_i }\), i:

\(\displaystyle{ R\subset \prod_{i=1}^{n} D_i. \square}\) :lol:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1431
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 70 razy
Pomógł: 84 razy

Re: Przeciwobraz zbioru przez relację

Post autor: Jakub Gurak »

Przedwczoraj udowodniłem, że jeśli \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to dla rodziny podzbiorów drugiej osi, wtedy przeciwobraz sumy tej rodziny jest równy sumie przeciwobrazów tych zbiorów.
Wykazałem również, że dla relacji \(\displaystyle{ R}\) między dwoma zbiorami \(\displaystyle{ X}\) a \(\displaystyle{ Y}\), dla zbioru \(\displaystyle{ B \subset R_P,}\) wtedy przeciwobraz dopełnienia tego zbioru, do zbioru \(\displaystyle{ R_P}\), może być innym zbiorem niż dopełnienie przeciwobrazu, do zbioru \(\displaystyle{ R_L.}\) Przedstawię teraz dowody tych ciekawych faktów.


Przypomnijmy, dla dowolnej relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), dla rodziny podzbiorów zbioru \(\displaystyle{ X}\), wtedy obraz sumy tej rodziny zbiorów jest równy sumie obrazów zbiorów tej rodziny, ten ciekawy fakt udowodniłem ostatnio TUTAJ- i ten fakt przyda się nam.

Niech \(\displaystyle{ R}\) będzie relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y.}\)
Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną podzbiorów zbioru \(\displaystyle{ Y.}\)

Wykażemy równość:

\(\displaystyle{ R ^{-1} \left( \bigcup\mathbb{B}\right) = \bigcup_{ A \in \mathbb{B}} R ^{-1} \left( A\right), }\)

czyli wykażemy, że przeciwobraz sumy tej rodziny zbiorów jest równy sumie przeciwobrazów zbiorów tej rodziny.

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ R ^{-1} \left( \bigcup \mathbb{B}\right) = S\left( \bigcup \mathbb{B}\right)}\), dla \(\displaystyle{ S=R ^{-1}}\), czyli przeciwobraz sumy \(\displaystyle{ \bigcup\mathbb{B}}\), przez relację \(\displaystyle{ R}\), jest równy obrazowi tej sumy, ale przez relację odwrotną \(\displaystyle{ S= R ^{-1}. }\)

Ponieważ w podanym linku udowodniłem, że dla relacji między dwoma zbiorami obraz sumy rodziny zbiorów jest równy sumie obrazów, a relacja odwrotna to też jest relacja ze zbioru w zbiór, więc ten zbiór jest równy sumie obrazów zbiorów tej rodziny, czyli jest to równe: \(\displaystyle{ = \bigcup_{A \in \mathbb{B}} S\left( A\right).}\)

Zauważmy, że jeśli \(\displaystyle{ A \in \mathbb{B}}\), to \(\displaystyle{ S\left( A\right) = R ^{-1} \left( A\right)}\) , czyli przeciwobraz zbioru \(\displaystyle{ A}\) przez relację \(\displaystyle{ R}\) jest równy obrazowi tego zbioru, ale przez relację odwrotną \(\displaystyle{ S=R ^{-1}}\); i to dla dowolnego zbioru \(\displaystyle{ A \in \mathbb{B}}\); a zatem:

\(\displaystyle{ \left\{ S\left( A\right): \ A \in \mathbb{B} \right\} = \left\{ R ^{-1} \left( A\right): \ A \in \mathbb{B} \right\}.}\)

A zatem, ponieważ dla rodziny zbiorów istnieje tylko jedna jej suma, a zatem:

\(\displaystyle{ \bigcup \left\{ S\left( A\right): \ A \in \mathbb{B} \right\} = \bigcup \left\{ R ^{-1} \left( A\right) : \ A \in \mathbb{B}\right\} ,}\)

czyli:

\(\displaystyle{ R ^{-1} \left( \bigcup \mathbb{B}\right) = \bigcup_{ A \in \mathbb{B}} S\left( A\right) = \bigcup_{A \in \mathbb{B}} R ^{-1} \left( A\right).\square}\) 8-)

Oto ilustracja tego faktu: \(\displaystyle{ \\ }\)
przeciwobraz sumy zbiorów przez relację.jpg
\(\displaystyle{ \\}\)
Przejdźmy do drugiego z naszych faktów:

Wykażemy, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ X}\), dla zbioru \(\displaystyle{ B \subset R_P}\), wtedy przeciwobraz dopełnienia zbioru \(\displaystyle{ B}\), do zbioru \(\displaystyle{ R_P}\), może być różny od dopełnienia przeciwobrazu zbioru \(\displaystyle{ B}\), gdzie chodzi o dopełnienie przeciwobrazu do zbioru \(\displaystyle{ R_L.}\)

DOWÓD TEGO FAKTU:

Niech: \(\displaystyle{ X= \left[ 0,2\right] \subset \RR.}\)

Niech: \(\displaystyle{ R= \left( \left[ 0,1\right] \times \left[ 0,2\right] \right) \cup \left[ 1,2\right] \times \left[ 1,2\right] .}\)

Wtedy \(\displaystyle{ R\supset \left[ 0,1\right] \times \left[ 0,2\right]}\), a zatem \(\displaystyle{ R_P\supset \left( \left[ 0,1\right] \times \left[ 0,2\right] \right) _P= \left[ 0,2\right]}\), ale \(\displaystyle{ R_P \subset Y=X= \left[ 0,2\right]}\) , a zatem \(\displaystyle{ R_P= \left[ 0,2\right].}\)

Mamy \(\displaystyle{ R\supset \left[ 0,2\right] \times \left[ 1,2\right] }\), a zatem \(\displaystyle{ R_L\supset \left( \left[ 0,2\right] \times \left[ 1,2\right] \right) _L= \left[ 0,2\right] }\), i \(\displaystyle{ R_L= \left[ 0,2\right].}\)

Niech \(\displaystyle{ B= \left[ 0,1\right] \subset R_P= \left[ 0,2\right].}\)

Wtedy \(\displaystyle{ B' = R_P \setminus B = \left( 1,2\right]}\); a zatem z definicji relacji \(\displaystyle{ R}\):

\(\displaystyle{ R ^{-1} \left( B' \right) = R ^{-1} \left( \left( 1,2\right] \right)= \left[ 0,2\right]. }\)

Tymczasem:

\(\displaystyle{ \left( R ^{-1} \left( B\right) \right) '= R_L \setminus R ^{-1} \left( B\right) = \left[ 0,2\right] \setminus R ^{-1} \left( \left[ 0,1\right] \right) = \left[ 0,2\right] \setminus \left[ 0,1\right] = \left(1,2\right] \neq \left[ 0,2\right] = R ^{-1} \left( B'\right) . \square}\)

Oto ilustracja tego ciekawego faktu: \(\displaystyle{ \\}\)
Przeciwobraz dopełnienia zbioru przez relację jest różny od dopełninia przeciwobrazu.jpg
\(\displaystyle{ \\}\) Wynika stąd, że dla relacji \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ X}\), dla dwóch zbiorów \(\displaystyle{ A,B \subset R_P}\), wtedy przeciwobraz różnicy \(\displaystyle{ A \setminus B}\) może być różny od różnicy przeciwobrazów, tzn. może być:

\(\displaystyle{ R ^{-1} \left( A \setminus B\right) \neq R ^{-1} \left( A\right) \setminus R ^{-1} \left( B\right) .}\)

Wystarczy wziąć ten sam kontrprzykład co powyżej, oraz \(\displaystyle{ A=R_P}\) i \(\displaystyle{ B= \left[ 0,1\right]}\) ,

i łatwo to wynika z faktu, że przeciwobraz dopełnienia może być różny od dopełnienia przeciwobrazu (gdyż dopełnienie zbioru możemy zapisać za pomocą różnicy), łatwo możemy ten fakt udowodnić.
8-)

Dodano po 7 miesiącach 20 godzinach 42 minutach 38 sekundach:
Przedwczoraj łatwo udowodniłem sobie na dobranoc, że jeśli mamy relację \(\displaystyle{ R}\) miedzy dwoma zbiorami, oraz
mamy punkt na drugiej osi (a dokładniej to: mamy punkt z prawej dziedziny tej relacji), to zbiór poprzedników tego elementu względem tej relacji jest równy przeciwobrazowi przez tą relację zbioru jednopunktowego złożonego z tego elementu.


Tzn.:

Jeśli \(\displaystyle{ R}\) jest relacją ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\), oraz \(\displaystyle{ b \in R_P}\), to:

\(\displaystyle{ \stackrel{ \leftarrow }{R} \left( b\right)= R ^{-1} \left\{ b\right\}.}\)

Gdyż, ponieważ dla relacji między dwoma zbiorami, dla punktu na drugiej osi, wtedy zbiór poprzedników tego elementu jest równy zbiorowi jego następników, ale przez relację do niego odwrotną; i ponieważ dla relacji między dwoma zbiorami, dla elementu na pierwszej osi, zbiór jego następników przez tą relację jest równy obrazowi przez tą relację zbioru jednopunktowego złożonego z tego elementu (w powyższych postach można znaleźć dowód tego faktu, jak i można poczytać o tych zbiorach następników elementu, zbiorach poprzedników elementu, itd. ), więc:

\(\displaystyle{ \stackrel{ \leftarrow }{R} \left( b\right)= \stackrel{ \rightarrow }{S} \left( b\right)= }\);

gdzie \(\displaystyle{ S=R ^{-1}}\), a więc to jest równe, na mocy powyższego ostatnio podanego faktu, więc to jest równe:

\(\displaystyle{ =S\left( \left\{ b\right\} \right)= T ^{-1} \left\{ b\right\}=}\)

czyli to jest równe przeciwobrazowi tego zbioru jednopunktowego \(\displaystyle{ \left\{ b \right\}}\) przez relację odwrotną \(\displaystyle{ T=S ^{-1}}\);

ale wtedy:

\(\displaystyle{ T= S^{-1}= \left( R ^{-1} \right) ^{-1}=R}\),

a więc to jest równe przeciwobrazowi :

\(\displaystyle{ = R ^{-1} \left\{ b\right\}.\square }\)


Dodam jeszcze jeden prosty fakt:

Analogicznie do zadania z naiwnej teorii mnogości na ważniaku, gdzie jest \(\displaystyle{ n}\) punktów w przestrzeni trójwymiarowej, niech \(\displaystyle{ n=1,2,3,\ldots}\), i analogicznie, rozważmy \(\displaystyle{ n}\) punktów na płaszczyźnie; formalnie: niech \(\displaystyle{ R}\) będzie niepustą, skończoną relacją w zbiorze liczb rzeczywistych (wtedy relacja \(\displaystyle{ R}\) będzie zbiorem wszystkich takich punktów). Wtedy rzuty tej relacji na lewą i na prawą oś, tzn. zbiory \(\displaystyle{ R_L}\) i \(\displaystyle{ R_P}\) są zbiorami skończonymi. Wykażemy, że:

\(\displaystyle{ \left| R_L\right| \cdot \left| R_P\right| \ge \left| R\right|,}\)

przy czym równość mocy, zachodzi tylko wtedy, gdy \(\displaystyle{ R}\) jest zbiorem punktów na odcinku poziomym lub zbiorem punktów na odcinku pionowym.

DOWÓD TEGO FAKTU:

Ponieważ mamy prawo relacji:

\(\displaystyle{ R \subset R_L \times R_P,}\)

i ponieważ zbiory \(\displaystyle{ R_L}\) i \(\displaystyle{ R_P}\) są zbiorami skończonymi, więc:

\(\displaystyle{ \left| R\right| \le \left| R_L \times R_P\right|= \left| R_L\right| \cdot \left| R_P\right|.}\)

I jeśli relacja \(\displaystyle{ R}\) jest postaci \(\displaystyle{ R=R_L \times \left\{ b\right\}}\), to:

\(\displaystyle{ \left| R\right| =\left| R_L\right| = \left| R_L\right| \cdot \left| \left\{ b\right\} \right|= \left| R_L\right| \cdot \left| R_P\right|.}\)

Podobnie, jeśli relacja \(\displaystyle{ R}\) jest zbiorem punktów na odcinku pionowym, tzn. gdy jest postaci \(\displaystyle{ R=\left\{ a\right\} \cdot R_P}\), to w podobny sposób otrzymujemy równość mocy zbiorów.

A jeśli dla relacji \(\displaystyle{ R}\), zarówno rzut \(\displaystyle{ R_L}\) jak i rzut \(\displaystyle{ R_P}\) nie są zbiorami jednoelementowymi, ponieważ relacja \(\displaystyle{ R}\) z założenia jest niepusta, to ich rzuty również, a więc obydwa rzuty są co najmniej dwuelementowe.

Widać wtedy, że:

\(\displaystyle{ \left| R\right| \neq \left| R_L\right| \cdot \left| R_P\right|}\),

oto:

ILUSTRACJA TEGO FAKTU:\(\displaystyle{ \\}\)
n punktów na płaszczyźnię.jpg
\(\displaystyle{ \\}\)
a więc:

\(\displaystyle{ \left| R\right| <\left| R_L\right| \cdot \left| R_P\right|.\square }\)

Dodano po 3 godzinach 17 minutach 57 sekundach:
Wykażemy, że:

\(\displaystyle{ \left| R_L\right| \cdot \left| R_P\right| \ge \left| R\right|,}\)

przy czym równość mocy, zachodzi tylko wtedy, gdy \(\displaystyle{ R}\) jest zbiorem punktów na odcinku poziomym lub zbiorem punktów na odcinku pionowym.
Tu jest pomyłka:

Wystarczy, jako kontrprzykład, rozważyć wierzchołki kwadratu \(\displaystyle{ \left[ 0,1\right] \times \left[ 0,1\right]}\), tzn. rozważmy zbiór czteroelementowy: \(\displaystyle{ R:=\left\{ 0,1\right\} \times \left\{ 0,1\right\} \subset \RR ^{2} .}\)

Wtedy:

\(\displaystyle{ R_L= \left\{ 0,1\right\} =R_P,}\)

a zatem:

\(\displaystyle{ \left| R_L\right| \cdot \left| R_P\right|= 2 \cdot 2=4= \left| R\right|,}\)

i relacja \(\displaystyle{ R}\) nie leży na jednym odcinku poziomym, ani nie leży na jednym odcinku pionowym, niestety. :?

Odpuściłem sobie szczegółowe uzasadnienie tej tezy (ale myślałem, że będę w stanie się wybronić, i chyba zrobiłem przeskok myślowy, i zrobiłem błąd... przepraszam :roll: ); i tym samym powyższa ilustracja jest myląca- przepraszam. :oops:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1431
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 70 razy
Pomógł: 84 razy

Re: Przeciwobraz zbioru przez relację

Post autor: Jakub Gurak »

Przypomnijmy (Andrzej Grzegorczyk 'Zarys logiki matematycznej', str. 19):
Jeśli mamy podzbiór płaszczyzny \(\displaystyle{ A \subset \RR ^{2}}\), to każdemu punktowi \(\displaystyle{ P \in A}\) możemy przypisać jego rzut \(\displaystyle{ r\left( P\right)}\) na oś \(\displaystyle{ x,}\) i zbiór:
\(\displaystyle{ O\left( A\right):= \left\{ r\left( P\right)\Bigl| \ P \in A \right\};}\)
nazywamy rzutem prostopadłym zbioru \(\displaystyle{ A}\) na oś poziomą.
Można łatwo to pojęcie uogólnić na dowolny iloczyn kartezjański \(\displaystyle{ X \times Y}\):
Jeśli mamy zbiór \(\displaystyle{ A \subset X \times Y}\), to każdemu punktowi \(\displaystyle{ \left( x,y\right) \in A}\) przypisujemy jego pierwszą współrzędną, tzn. definiujemy funkcję \(\displaystyle{ r}\) jako: \(\displaystyle{ r\left( \left( x,y\right) \right)=x}\), a następnie definiujemy zbiór:
\(\displaystyle{ O\left( A\right):= \left\{ r\left( P\right)\Bigl| \ P \in A \right\};}\)
nazwiemy go również rzutem prostopadłym relacji \(\displaystyle{ A}\) na oś poziomą.
W ostatnią środę wykazałem, że jeśli \(\displaystyle{ R}\) jest relacją ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\), oraz jeśli mamy zbiór \(\displaystyle{ B \subset Y}\), taki, że \(\displaystyle{ B\supset R _{P}}\), tzn. mamy zbiór zawierający prawą dziedzinę relacji \(\displaystyle{ R}\), to przeciwobraz zbioru \(\displaystyle{ B}\) przez relację \(\displaystyle{ R}\) jest równy rzucie prostopadłym relacji \(\displaystyle{ R}\) na oś poziomą.
Wprowadziłem tutaj też analogiczne pojęcie rzutu prostopadłego relacji \(\displaystyle{ R \subset X \times Y}\) na oś pionową, i udowodniłem, że jeśli mamy zbiór \(\displaystyle{ A \subset X,}\) taki, że \(\displaystyle{ A\supset R _{L},}\) tzn. mamy zbiór zawierający lewą dziedzinę relacji \(\displaystyle{ R,}\) to ten rzut prostopadły relacji \(\displaystyle{ R}\) jest równy obrazowi zbioru \(\displaystyle{ A}\) przez tą relację. Udowodniłem też, że rzut prostopadły relacji \(\displaystyle{ R \subset X \times Y}\) na oś pionową jest równy rzucie prostopadłym relacji \(\displaystyle{ R ^{-1}}\) na oś poziomą, ale chodzi tu o rzut relacji odwrotnej \(\displaystyle{ R ^{-1}}\) ; i na odwrót. Przedstawię teraz dowody tych ciekawych faktów.

Niech \(\displaystyle{ R}\) będzie relacją ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\); i niech \(\displaystyle{ B \subset Y}\) będzie dowolnym zbiorem takim, że \(\displaystyle{ B\supset R_P}\). Wykażemy, że: \(\displaystyle{ R ^{-1} \left( B\right)= O\left( R\right)}\); tzn. wykażemy, że przeciwobraz zbioru \(\displaystyle{ B}\) przez relację \(\displaystyle{ R}\) jest równy rzucie prostopadłym tej relacji na oś poziomą.
DOWÓD TEGO FAKTU::    
Wprowadzimy teraz pojęcie rzutu prostopadłego relacji \(\displaystyle{ R \subset X \times Y}\) na oś pionową, tzn.:
Jeśli \(\displaystyle{ R}\) jest relacją ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\), to:
Wpierw parzę \(\displaystyle{ \left( x,y\right) \in R}\) przypiszmy jej drugą współrzędną, tzn. rozważmy funkcję \(\displaystyle{ s}\), daną jako: \(\displaystyle{ s\left( \left( x,y\right) \right)=y}\), i następnie zbiór:
\(\displaystyle{ S\left( R\right):= \left\{ s\left( P\right)\Bigl| \ \ P \in R \right\};}\)
nazwiemy rzutem prostopadłym relacji \(\displaystyle{ R}\) na oś pionową.

Niech \(\displaystyle{ R}\) będzie relacją ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\), i niech zbiór \(\displaystyle{ A \subset X}\) będzie dowolnym podzbiorem \(\displaystyle{ X}\) takim, że \(\displaystyle{ A\supset R _{L}.}\) Wykażemy, że:
\(\displaystyle{ R\left( A\right) = S\left( R\right);}\)
tzn. wykażemy, że obraz zbioru \(\displaystyle{ A}\) przez relację \(\displaystyle{ R}\) jest równy temu rzutowi prostopadłemu relacji \(\displaystyle{ R}\).
Podajmy najpierw pewne dwa Lematy:
Lemat 1:Jeśli \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to:
\(\displaystyle{ S\left( R\right) = O\left( R ^{-1} \right);}\)
tzn. rzut prostopadły relacji \(\displaystyle{ R}\) na oś pionową jest równy rzucie relacji odwrotnej \(\displaystyle{ R ^{-1}}\) na oś poziomą.
DOWÓD TEGO FAKTU::    
Podajmy teraz nasz drugi Lemat:
Lemat 2:
Jeśli \(\displaystyle{ R}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to:
\(\displaystyle{ O\left( R\right) =S\left( R ^{-1} \right);}\)
tzn. rzut prostopadły relacji \(\displaystyle{ R}\) na oś poziomą jest równy rzucie prostopadłym relacji \(\displaystyle{ R ^{-1}}\) na oś pionową. Oto:
PROSTY DOWÓD TEGO FAKTU:
Na mocy powyższego Lematu otrzymujemy (relacja odwrotna to też jest relacja między dwoma zbiorami, u nas mianowicie jest to relacja między zbiorem \(\displaystyle{ Y}\) a \(\displaystyle{ X}\)), więc otrzymujemy:
\(\displaystyle{ S\left( R ^{-1} \right)= O\left( \left( R ^{-1}\right) ^{-1} \right) = O\left( R\right).\square}\) :P
Przejdźmy do dowodu naszego faktu:
DOWÓD TEGO FAKTU(zachowując wprowadzone oznaczenia):
Relacja \(\displaystyle{ R ^{-1}}\) jest relacją z \(\displaystyle{ Y}\) do \(\displaystyle{ X}\), i ponieważ \(\displaystyle{ \left( R^{-1} \right) _{P}= R _{L}}\), to \(\displaystyle{ A\supset \left( R ^{-1} \right) _{P}.}\)
A zatem, na mocy naszego pierwszego udowodnionego w tym poście faktu, otrzymujemy:
\(\displaystyle{ T ^{-1} \left( A\right)= O\left( T\right)}\), gdzie \(\displaystyle{ T=R ^{-1};}\)
tzn. przeciwobraz zbioru \(\displaystyle{ A}\) przez relację \(\displaystyle{ T=R ^{-1}}\) jest równy rzucie prostopadłym tej relacji na oś poziomą.
Wtedy \(\displaystyle{ R\left( A\right)= T ^{-1} \left( A\right)}\), gdzie \(\displaystyle{ T=R ^{-1}.}\) Wtedy:
\(\displaystyle{ R\left( A\right) = T ^{-1}\left( A\right) = O\left( T\right)= S\left( T ^{-1} \right)=}\)
i ponieważ \(\displaystyle{ T= R ^{-1}}\), więc \(\displaystyle{ T ^{-1}= \left( R ^{-1} \right) ^{-1}= R}\),
a więc to jest równe \(\displaystyle{ =S\left( R\right).\square}\) 8-)
O jej- teraz zauważyłem, że te rzuty prostopadłe relacji \(\displaystyle{ R \subset X \times Y}\) to są to odpowiednio: lewa i prawa dziedzina relacji \(\displaystyle{ R}\), nie pomyślałem tutaj o tym, i tylko fakt z obrazem może być tutaj dla mnie nowym...

Dodam tutaj jeszcze takie ciekawe spostrzeżenie, że robiąc dowód w liczbach naturalnych dodatnich, i nie sprawdzając początkowego założenia o istnieniu liczby o danej własności, można wtedy dojść do wniosku, że \(\displaystyle{ 1}\) jest największą dodatnią liczbą naturalną.
CHYBIONY DOWÓD TEGO FAKTU:
Oznaczmy największą dodatnią liczbą naturalną przez \(\displaystyle{ x}\). Wtedy \(\displaystyle{ x \ge 1}\).
Jeśli \(\displaystyle{ x>1}\), to \(\displaystyle{ x ^{2}= x \cdot x>1 \cdot x=x}\), a ponieważ \(\displaystyle{ x ^{2}=x \cdot x}\), jako iloczyn dwóch liczb naturalnych, jest liczbą naturalna (i to dodatnią), to liczba \(\displaystyle{ x}\) nie może być największą dodatnią liczbą naturalną, więc otrzymujemy tutaj sprzeczność.
Zatem \(\displaystyle{ x\not>1}\), a zatem \(\displaystyle{ x}\) musi być równe \(\displaystyle{ 1.\square}\)
Błąd w tym dowodzie jest łatwy do wskazania- nie ma największej dodatniej liczby naturalnej, bo do każdej można dodać \(\displaystyle{ 1,}\) i otrzymać jeszcze większą...
Jan Kraszewski
Administrator
Administrator
Posty: 34555
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Przeciwobraz zbioru przez relację

Post autor: Jan Kraszewski »

Jaki jest cel powyższego posta? Pochwalenie się, że poznałeś definicję rzutu?

JK
ODPOWIEDZ