Injekcja, złożenie funkcji

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Injekcja, złożenie funkcji

Post autor: smo »

Chciałbym przeprowadzić dowód następującego twierdzenia:
"Funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją wtedy i tylko wtedy, gdy dla dowolnego zbioru \(\displaystyle{ Z}\) oraz dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) zachodzi implikacja: \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\)."

Dowód implikacji "jeżeli funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją to dla dowolneo zbioru \(\displaystyle{ Z}\) oraz dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\)."
Niech \(\displaystyle{ f:X \rightarrow Y}\) będzie injekcją oraz \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) dowolnymi funkcjami. Weźmy \(\displaystyle{ \left( z_{1} ,y\right) \in f\circ g_{1}}\) oraz \(\displaystyle{ \left( z_{2}, y \right) \in f\circ g_{2}}\) gdzie \(\displaystyle{ z_{1}, z_{2} \in Z, y \in Y}\) są dowolnymi elementami. Ponieważ \(\displaystyle{ rng\left( g_{1} \right), rng\left( g_{2} \right) \subseteq X}\) to \(\displaystyle{ g_{1}\left( z_{1} \right), g_{2}\left( z_{2} \right) \in X =dom\left( f\right) }\). Niech \(\displaystyle{ g_{1}\left( z_{1} \right) = x_{1}, g_{2}\left( z_{2} \right)= x_{2} \in X }\). Wówczas \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( x_{1} \right), f\left( g_{2}\left( z_{2} \right) \right) =f\left( x_{2} \right) \in Y }\). Załóżmy, że \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{2} \right) \right) }\). Wówczas skoro \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ g_{1}\left( z_{1} \right) = g_{2 }\left( z_{2} \right) }\) czyli jeżeli \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) }\) to \(\displaystyle{ x_{1} = x_{2} }\) dla dowolnych \(\displaystyle{ g_{1}\left( z_{1} \right), g_{2}\left( z_{2} \right) \in X}\). Zatem \(\displaystyle{ z_{1} \in dom\left( f\circ g_{2} \right)}\) oraz \(\displaystyle{ z_{2} \in dom\left( f\circ g_{1} \right)}\), ponieważ jednocześnie \(\displaystyle{ z_{1} \in dom\left( f\circ g_{1} \right)}\) oraz \(\displaystyle{ z_{2} \in dom\left( f\circ g_{2} \right)}\) to \(\displaystyle{ z_{1}, z_{2} \in dom\left( f\circ g_{1} \right)}\), \(\displaystyle{ z_{1}, z_{2} \in dom\left( f\circ g_{2}\right)}\) dla dowolnych \(\displaystyle{ z_{1}, z_{2} \in Z}\). Tak więc \(\displaystyle{ dom\left( f\circ g_{1} \right) =dom\left( f\circ g_{2} \right) }\). Jednocześnie jeżeli \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{1} \right) \right) }\) oraz \(\displaystyle{ f\left( g_{2}\left( z_{2} \right) \right) =f\left( g_{1}\left( z_{2} \right) \right) }\) to wówczas z def. równości funkcji mamy, że \(\displaystyle{ f\circ g_{1} =f\circ g_{2} }\). Zatem skoro \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{1} \right) \right), f\left( g_{2}\left( z_{2} \right) \right)=f\left( g_{1}\left( z_{2} \right) \right) }\) oraz \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{2} \right) \right) }\) to \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{1} \right) \right)=f\left( g_{1}\left( z_{2} \right) \right) =f\left( g_{2}\left( z_{2} \right) \right) }\), a ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ g_{1}\left( z_{1} \right) = g_{2}\left( z_{1} \right)= g_{1}\left( z_{2} \right) = g_{2}\left( z_{2} \right) }\). Zatem \(\displaystyle{ z_{1} \in dom\left( g_{2} \right)}\) oraz \(\displaystyle{ z_{2} \in dom\left( g_{1} \right)}\) dla dowolnych \(\displaystyle{ z_{1}, z_{2} \in Z}\), a więc \(\displaystyle{ dom\left( g_{1} \right) =dom\left( g_{2} \right) }\). Jednocześnie skoro funkcja \(\displaystyle{ g_{1}}\) przyjmuje dla dowolnych argumentów \(\displaystyle{ z_{1}, z_{2} \in Z}\) te same wartości funkcji co funkcja \(\displaystyle{ g_{2}}\) dla tych samych \(\displaystyle{ z_{1}, z_{2} \in Z}\) to wówczas z def. wynika, że \(\displaystyle{ g_{1} = g_{2} }\).

Dowód implikacji: "jeżeli dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) oraz dowolnego zbioru \(\displaystyle{ Z}\) zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2}}\) to funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją."
Niech \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) oraz \(\displaystyle{ f:X \rightarrow Y}\) będą dowolnymi funkcjami. Skoro zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\) to wówczas \(\displaystyle{ g_{1} = g_{2} }\), a więc z def. \(\displaystyle{ dom\left( g_{1} \right) =dom\left( g_{2} \right) }\) oraz \(\displaystyle{ g_{1}\left( z\right) = g_{2}\left( z\right) }\) dla dowolnego \(\displaystyle{ z \in Z}\). Ponieważ \(\displaystyle{ rng\left( g_{1} \right) =rng\left( g_{2} \right) \subseteq X=dom\left( f\right) }\), zatem \(\displaystyle{ g_{1}\left( z\right), g_{2}\left( z\right) \in X}\). Jednocześnie \(\displaystyle{ f\circ g_{1} =f\circ g_{2} }\), a więc \(\displaystyle{ f\left( g_{1}\left( z\right) \right) =f\left( g_{2}\left( z\right) \right) \in Y }\) dla dowolnego \(\displaystyle{ z \in Z}\). Wówczas mamy, że \(\displaystyle{ f\left( g_{1}\left( z\right) \right) =f\left( g_{2}\left( z\right) \right) }\) oraz \(\displaystyle{ g_{1}\left( z\right) = g_{2}\left( z\right) }\) dla dowolnych \(\displaystyle{ g_{1}\left( z\right), g_{2}\left( z\right) \in X}\), a zatem \(\displaystyle{ f}\) jest injekcją.

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 28 maja 2021, o 20:52Dowód implikacji "jeżeli funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją to dla dowolneo zbioru \(\displaystyle{ Z}\) oraz dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\)."
Niech \(\displaystyle{ f:X \rightarrow Y}\) będzie injekcją oraz \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) dowolnymi funkcjami. Weźmy \(\displaystyle{ \left( z_{1} ,y\right) \in f\circ g_{1}}\) oraz \(\displaystyle{ \left( z_{2}, y \right) \in f\circ g_{2}}\) gdzie \(\displaystyle{ z_{1}, z_{2} \in Z, y \in Y}\) są dowolnymi elementami.
Tak nie można. Dlaczego równość \(\displaystyle{ f(g_1(z_1))=f(g_2(z_2))=y}\) (a dokładnie to oznacza "\(\displaystyle{ \left( z_{1} ,y\right) \in f\circ g_{1}}\) oraz \(\displaystyle{ \left( z_{2}, y \right) \in f\circ g_{2}}\)") miałaby być prawdziwa dla dowolnych \(\displaystyle{ z_{1}, z_{2} \in Z, y \in Y}\)?
smo pisze: 28 maja 2021, o 20:52Ponieważ \(\displaystyle{ rng\left( g_{1} \right), rng\left( g_{2} \right) \subseteq X}\) to \(\displaystyle{ g_{1}\left( z_{1} \right), g_{2}\left( z_{2} \right) \in X =dom\left( f\right) }\). Niech \(\displaystyle{ g_{1}\left( z_{1} \right) = x_{1}, g_{2}\left( z_{2} \right)= x_{2} \in X }\). Wówczas \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( x_{1} \right), f\left( g_{2}\left( z_{2} \right) \right) =f\left( x_{2} \right) \in Y }\). Załóżmy, że \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{2} \right) \right) }\). Wówczas skoro \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ g_{1}\left( z_{1} \right) = g_{2 }\left( z_{2} \right) }\) czyli jeżeli \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) }\) to \(\displaystyle{ x_{1} = x_{2} }\) dla dowolnych \(\displaystyle{ g_{1}\left( z_{1} \right), g_{2}\left( z_{2} \right) \in X}\). Zatem \(\displaystyle{ z_{1} \in dom\left( f\circ g_{2} \right)}\) oraz \(\displaystyle{ z_{2} \in dom\left( f\circ g_{1} \right)}\), ponieważ jednocześnie \(\displaystyle{ z_{1} \in dom\left( f\circ g_{1} \right)}\) oraz \(\displaystyle{ z_{2} \in dom\left( f\circ g_{2} \right)}\) to \(\displaystyle{ z_{1}, z_{2} \in dom\left( f\circ g_{1} \right)}\), \(\displaystyle{ z_{1}, z_{2} \in dom\left( f\circ g_{2}\right)}\) dla dowolnych \(\displaystyle{ z_{1}, z_{2} \in Z}\). Tak więc \(\displaystyle{ dom\left( f\circ g_{1} \right) =dom\left( f\circ g_{2} \right) }\). Jednocześnie jeżeli \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{1} \right) \right) }\) oraz \(\displaystyle{ f\left( g_{2}\left( z_{2} \right) \right) =f\left( g_{1}\left( z_{2} \right) \right) }\) to wówczas z def. równości funkcji mamy, że \(\displaystyle{ f\circ g_{1} =f\circ g_{2} }\). Zatem skoro \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{1} \right) \right), f\left( g_{2}\left( z_{2} \right) \right)=f\left( g_{1}\left( z_{2} \right) \right) }\) oraz \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{2} \right) \right) }\) to \(\displaystyle{ f\left( g_{1}\left( z_{1} \right) \right) =f\left( g_{2}\left( z_{1} \right) \right)=f\left( g_{1}\left( z_{2} \right) \right) =f\left( g_{2}\left( z_{2} \right) \right) }\), a ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ g_{1}\left( z_{1} \right) = g_{2}\left( z_{1} \right)= g_{1}\left( z_{2} \right) = g_{2}\left( z_{2} \right) }\). Zatem \(\displaystyle{ z_{1} \in dom\left( g_{2} \right)}\) oraz \(\displaystyle{ z_{2} \in dom\left( g_{1} \right)}\) dla dowolnych \(\displaystyle{ z_{1}, z_{2} \in Z}\), a więc \(\displaystyle{ dom\left( g_{1} \right) =dom\left( g_{2} \right) }\). Jednocześnie skoro funkcja \(\displaystyle{ g_{1}}\) przyjmuje dla dowolnych argumentów \(\displaystyle{ z_{1}, z_{2} \in Z}\) te same wartości funkcji co funkcja \(\displaystyle{ g_{2}}\) dla tych samych \(\displaystyle{ z_{1}, z_{2} \in Z}\) to wówczas z def. wynika, że \(\displaystyle{ g_{1} = g_{2} }\).
Ten dowód, jakkolwiek zawiera pewną poprawną obserwację, to:
- jest kompletnie nieczytelny
- używa mnóstwa niepotrzebnych znaczków
- zawiera mnóstwo oczywistych bądź niepotrzebnych spostrzeżeń
- jest źle sformułowany.

To jest bardzo proste rozumowanie:

Niech \(\displaystyle{ f:X \rightarrow Y}\) będzie injekcją. Ustalmy dowolne \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) takie, że \(\displaystyle{ f\circ g_1=f\circ g_2}\) oraz dowolne \(\displaystyle{ z\in Z}\). Wtedy \(\displaystyle{ f\circ g_1(z)=f\circ g_2(z)}\), czyli \(\displaystyle{ f(g_1(z))=f(g_2(z))}\). Ponieważ \(\displaystyle{ f}\) jest injekcją, więc \(\displaystyle{ g_1(z)=g_2(z)}\), co wobec dowolności wyboru \(\displaystyle{ z}\) oznacza, że \(\displaystyle{ g_1=g_2}\).
smo pisze: 28 maja 2021, o 20:52Dowód implikacji: "jeżeli dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) oraz dowolnego zbioru \(\displaystyle{ Z}\) zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2}}\) to funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją."
Niech \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) oraz \(\displaystyle{ f:X \rightarrow Y}\) będą dowolnymi funkcjami. Skoro zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\) to wówczas \(\displaystyle{ \red{g_{1} = g_{2}} }\)
:?: :?:
Niby dlaczego?

JK
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Dziękuję za wyjaśnienia.
Czy dowód implikacji: "jeżeli dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) oraz dla dowolnego zbioru \(\displaystyle{ Z}\) zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\) to funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją" może wyglądać następująco?
Dowód:
Niech \(\displaystyle{ f:X \rightarrow Y}\). Ustalmy dowolne funkcje \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) dla których zachodzi równość \(\displaystyle{ f\circ g_{1} =f\circ g_{2} }\) oraz dowolny element \(\displaystyle{ z \in Z}\). Wówczas \(\displaystyle{ f\left( g_{1}\left( z\right) \right) =f\left( g_{2}\left( z\right) \right) }\). Zatem jeżeli \(\displaystyle{ g_{1}\left( z\right) = g_{2}\left( z\right) }\) to \(\displaystyle{ g_{1} = g_{2} }\), ponieważ element \(\displaystyle{ z}\) został wybrany dowolnie. A wówczas skoro \(\displaystyle{ f\left( g_{1}\left( z\right) \right) =f\left( g_{2}\left( z\right) \right) }\) oraz \(\displaystyle{ g_{1}\left( z\right) = g_{2}\left( z\right) }\) to funkcja \(\displaystyle{ f}\) jest injekcją.

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 30 maja 2021, o 20:36 Czy dowód implikacji: "jeżeli dla dowolnych funkcji \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) oraz dla dowolnego zbioru \(\displaystyle{ Z}\) zachodzi implikacja \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\) to funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest injekcją" może wyglądać następująco?
Dowód:
Niech \(\displaystyle{ f:X \rightarrow Y}\). Ustalmy dowolne funkcje \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) dla których zachodzi równość \(\displaystyle{ f\circ g_{1} =f\circ g_{2} }\) oraz dowolny element \(\displaystyle{ z \in Z}\). Wówczas \(\displaystyle{ f\left( g_{1}\left( z\right) \right) =f\left( g_{2}\left( z\right) \right) }\). Zatem jeżeli \(\displaystyle{ g_{1}\left( z\right) = g_{2}\left( z\right) }\) to \(\displaystyle{ g_{1} = g_{2} }\), ponieważ element \(\displaystyle{ z}\) został wybrany dowolnie. A wówczas skoro \(\displaystyle{ f\left( g_{1}\left( z\right) \right) =f\left( g_{2}\left( z\right) \right) }\) oraz \(\displaystyle{ g_{1}\left( z\right) = g_{2}\left( z\right) }\) to funkcja \(\displaystyle{ f}\) jest injekcją.
Nie może, to "fałszywy" dowód. Ostatnie zdanie jest nieprawdziwe.

Masz złe podejście do założenia. Skorzystanie z założenia nie polega na "ustaleniu dowolnych funkcje \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\), dla których zachodzi równość \(\displaystyle{ f\circ g_{1} =f\circ g_{2} }\)", tylko na wybraniu konkretnych funkcji \(\displaystyle{ g_{1}, g_{2}}\), które będą Ci pasować do dowodu i do których zastosujesz założenie. Sam dowód zaczynasz też od złej strony - skoro chcesz pokazać, że funkcja \(\displaystyle{ f}\) jest injekcją, to trzeba zacząć od definicji injekcji. Ja bym zrobił go tak:

Po pierwsze, zauważam, że warunek \(\displaystyle{ f\circ g_{1} =f\circ g_{2} \Rightarrow g_{1} = g_{2} }\) jest równoważny warunkowi \(\displaystyle{ g_{1}\ne g_{2} \Rightarrow f\circ g_{1} \ne f\circ g_{2}}\) i w tej wersji będę z niego korzystał.
Po drugie:

Ustalmy dowolne \(\displaystyle{ x_1,x_2\in X}\) takie, że \(\displaystyle{ x_1\ne x_2}\). Niech \(\displaystyle{ g_{1}, g_{2}:Z \rightarrow X}\) będą funkcjami (stałymi) zadanymi warunkami \(\displaystyle{ g_1(z)=x_1,g_2(z)=x_2}\). Oczywiście \(\displaystyle{ g_1\ne g_2}\). Z założenia wiemy, że wówczas \(\displaystyle{ f\circ g_{1} \ne f\circ g_{2}}\), czyli istnieje \(\displaystyle{ z\in Z}\) takie, że \(\displaystyle{ f\circ g_{1}(z) \ne f\circ g_{2}(z)}\). Ale to znaczy, że \(\displaystyle{ f(x_1)=f(g_{1}(z)) \ne f(g_{2}(z))=f(x_2)}\), zatem funkcja \(\displaystyle{ f}\) jest injekcją.

JK
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Faktycznie samo rozumowanie jest bardzo proste w tych dowodach ale wpaść na odpowiednie sformułowania i kroki już nie jest dla mnie takie łatwe.
Dziękuję za wszystkie wyjaśnienia.

DS

Dodano po 1 dniu 18 godzinach 47 minutach 1 sekundzie:
Chciałbym jeszcze udowodnić następujące twierdzenie:
"Złożenie dwóch injekcji jest injekcją."
Dowód:
Niech \(\displaystyle{ f:X \rightarrow Y, g:Z \rightarrow W}\) będą injekcjami. Ustalmy dowolne elementy \(\displaystyle{ x_{1}, x_{2} \in X}\). Skoro \(\displaystyle{ f}\) jest injekcją to jeżeli \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) }\) to \(\displaystyle{ x_{1} = x_{2} }\). Jednocześnie z def. złożenia funkcji wynika, że istnieje \(\displaystyle{ y=f\left( x\right)=z \in Y\cap Z}\). Wówczas \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) \in Z }\). Ponieważ \(\displaystyle{ g}\) jest injekcją to \(\displaystyle{ g\left( f\left( x_{1} \right) \right) =g\left( f\left( x_{2} \right) \right)=g\left( z_{1} \right)=g\left( z_{2} \right) }\) oraz \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right)= z_{1}= z_{2} }\), gdzie \(\displaystyle{ z_{1}, z_{2} \in Z}\), a wówczas \(\displaystyle{ g\circ f}\) jest injekcją.

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 2 cze 2021, o 16:05Niech \(\displaystyle{ f:X \rightarrow Y, g:Z \rightarrow W}\) będą injekcjami. Ustalmy dowolne elementy \(\displaystyle{ x_{1}, x_{2} \in X}\). Skoro \(\displaystyle{ f}\) jest injekcją to jeżeli \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) }\) to \(\displaystyle{ x_{1} = x_{2} }\). Jednocześnie z def. złożenia funkcji wynika, że istnieje \(\displaystyle{ y=f\left( x\right)=z \in Y\cap Z}\). Wówczas \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) \in Z }\). Ponieważ \(\displaystyle{ g}\) jest injekcją to \(\displaystyle{ g\left( f\left( x_{1} \right) \right) =g\left( f\left( x_{2} \right) \right)=g\left( z_{1} \right)=g\left( z_{2} \right) }\) oraz \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right)= z_{1}= z_{2} }\), gdzie \(\displaystyle{ z_{1}, z_{2} \in Z}\), a wówczas \(\displaystyle{ g\circ f}\) jest injekcją.
Chęci dobre, ale jednak nie tak - sformułowanie rozumowania nie jest dobre.

Już na początku robisz błąd:

"Niech \(\displaystyle{ f:X \rightarrow Y, g:Z \rightarrow W}\) będą injekcjami."

bo takich funkcji w ogólności nie da się złożyć. Powinno być "Niech \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow Z}\)".

Dalej zaczynasz dobrze:

"Ustalmy dowolne elementy \(\displaystyle{ x_{1}, x_{2} \in X}\)"

ale potem nie jest już dobrze. Skoro chcesz pokazać, że \(\displaystyle{ g\circ f}\) jest injekcją, to powinieneś skorzystać z definicji injekcji i założyć, że dla tych ustalonych \(\displaystyle{ x_{1}, x_{2} \in X}\) zachodzi \(\displaystyle{ g\circ f (x_1)=g\circ f(x_2)}\) (lub \(\displaystyle{ x_1\ne x_2}\) - w zależności od tego, której wersji definicji chcesz użyć), a potem kolejno stosujesz założenia - skoro \(\displaystyle{ g(f (x_1))=g( f(x_2))}\), to z injektywności funkcji \(\displaystyle{ g}\) wynika, że \(\displaystyle{ f (x_1)= f(x_2)}\), a z tego - z injektywności funkcji \(\displaystyle{ f}\) - wynika, że \(\displaystyle{ x_1=x_2}\), co kończy dowód injektywności funkcji \(\displaystyle{ g\circ f}\).

JK
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Dziękuję.
Czyli dowód ma wyglądać w ten sposób?

Niech \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow Z}\) będą injekcjami(bo rozumiem, że trzeba założyć z góry, że te funkcje są różnowartościowe).
Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\). Załóżmy, że \(\displaystyle{ g\left( f\left( x_{1} \right) \right) =g\left( f\left( x_{2} \right) \right) }\). Wówczas \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) }\) co wynika z injektywności funkcji \(\displaystyle{ g}\), a ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\). Wówczas \(\displaystyle{ g\circ f}\) jest injekcją.

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 2 cze 2021, o 22:12 Niech \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow Z}\) będą injekcjami(bo rozumiem, że trzeba założyć z góry, że te funkcje są różnowartościowe).
A jak inaczej, skoro chcesz pokazać, że złożenie injekcji jest injekcją?
smo pisze: 2 cze 2021, o 22:12 Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\). Załóżmy, że \(\displaystyle{ g\left( f\left( x_{1} \right) \right) =g\left( f\left( x_{2} \right) \right) }\). Wówczas \(\displaystyle{ f\left( x_{1} \right) =f\left( x_{2} \right) }\) co wynika z injektywności funkcji \(\displaystyle{ g}\), a ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\). Wówczas \(\displaystyle{ g\circ f}\) jest injekcją.
Tak.

JK
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Dziękuję.
Teraz chciałbym udowodnić twierdzenie:
"jeżeli funkcja \(\displaystyle{ f \subseteq X\times Y}\) jest injekcją to relacja \(\displaystyle{ f^{-1} \subseteq Y\times X}\) jest także funkcją oraz injekcją, przy czym \(\displaystyle{ f\circ f^{-1} = id_{rng\left( f\right) } }\) oraz \(\displaystyle{ f^{-1}\circ f = id_{dom\left( f\right) } }\).
Dowód:
Niech \(\displaystyle{ f \subseteq X\times Y}\) będzie injekcją. Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\) oraz dowolne \(\displaystyle{ y \in Y}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to relacja \(\displaystyle{ f^{-1}}\) jest także funkcją. Wówczas jeżeli \(\displaystyle{ \left( y, x_{1} \right), \left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right), \left( x_{2},y \right) \in f}\) i z injektywności funkcji \(\displaystyle{ f}\) wynika, że \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest injekcją.
Z def. \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in Y\times Y: istnieje \ x \in X\ takie, że \ \left( y,x\right) \in f^{-1}\ oraz \ \left( x,y\right) \in f \right\} }\). Wówczas skoro istnieje \(\displaystyle{ x \in X}\) takie, że \(\displaystyle{ \left( x,y\right) \in f}\) to \(\displaystyle{ y=f\left( x\right) \in rng\left( f\right)=dom\left( f^{-1} \right) }\), a więc z def. \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in Y\times Y: \ y=f\left( x\right) \in rng\left( f\right) \right\}= id_{rng\left( f\right) } }\).
Z def. \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X: \ istnieje \ y \ \in Y \ takie, że \ \left( x,y\right) \in f \ oraz \ \left(y ,x\right) \in f^{-1} \right\} }\). Jednocześnie \(\displaystyle{ x \in X=dom\left( f\right) }\), a zatem z def. \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X: x \in dom\left( f\right) \right\}= id_{dom\left( f\right) } }\).

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 13 cze 2021, o 12:28Niech \(\displaystyle{ f \subseteq X\times Y}\) będzie injekcją. Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\) oraz dowolne \(\displaystyle{ y \in Y}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to relacja \(\displaystyle{ f^{-1}}\) jest także funkcją. Wówczas jeżeli \(\displaystyle{ \left( y, x_{1} \right), \left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right), \left( x_{2},y \right) \in f}\) i z injektywności funkcji \(\displaystyle{ f}\) wynika, że \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest injekcją.
No nie. Tu masz chaos. Deklarujesz, że pokażesz dwie rzeczy: że \(\displaystyle{ f^{-1}}\) jest funkcją i że jest to funkcja różnowartościowa. A w efekcie pierwszą z tych rzeczy stwierdzasz (bez uzasadnienia), a drugą próbujesz dowieść, ale robisz to niepoprawnie - to, co według Ciebie jest dowodem injektywności \(\displaystyle{ f^{-1}}\) jest tak naprawdę dowodem na to, że jest to funkcja.
smo pisze: 13 cze 2021, o 12:28 Z def. \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in Y\times Y: istnieje \ x \in X\ takie, że \ \left( y,x\right) \in f^{-1}\ oraz \ \left( x,y\right) \in f \right\} }\).
Nieprawda. A skoro zaczynasz od nieprawdy, to nie ma sensu czytać dalej...

JK
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Zgadza się.

Niech \(\displaystyle{ f \subseteq X\times Y}\) będzie injekcją. Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\) oraz dowolne \(\displaystyle{ y \in Y\ }\). Wówczas jeżeli \(\displaystyle{ \left( y, x_{1} \right),\left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right),\left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest funkcją. Ustalmy dowolne \(\displaystyle{ x \in X}\) oraz dowolne \(\displaystyle{ y_{1}, y_{2} \in Y}\). Jeżeli \(\displaystyle{ \left( x, y_{1} \right),\left( x, y_{2} \right) \in f}\) to \(\displaystyle{ \left( y_{1},x \right),\left( y_{2},x \right) \in f^{-1}}\). Ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\), a wówczas \(\displaystyle{ f^{-1}}\) jest injekcją.

Ustalmy dowolne \(\displaystyle{ y=f\left( x\right) \in rng\left( f\right) =dom\left( f^{-1} \right) }\). Wówczas z def. \(\displaystyle{ f\circ f^{-1} =\left\{ \left( f\left( x\right),f\left( x\right) \right) \in Y\times Y:\ istnieje\ takie\ x \in X,\ że\ \left( f\left( x\right),x \right) \in f^{-1}\ oraz\ \left( x,f\left( x\right) \right)\in f \right\} }\). Wówczas z def. dla \(\displaystyle{ rng\left( f\right) =dom\left( f^{-1} \right) \subseteq Y }\) mamy, że \(\displaystyle{ f\circ f^{-1} =\left\{ \left( f\left( x\right),f\left( x\right) \right) \in Y\times Y: f\left( x\right) \in rng\left( f\right) \right\}= id_{rng\left( f\right) } }\).

Ustalmy dowolne \(\displaystyle{ x \in X}\). Wówczas z def. \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X:\ istnieje\ takie\ y \in Y,\ że\ \left(x,y \right) \in f\ oraz\ \left( y,x\right) \in f^{-1} \right\} }\). Zatem dla \(\displaystyle{ dom\left( f\right) =rng\left( f^{-1} \right)=X}\) mamy \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X:x \in dom\left( f\right) \right\}= id_{dom\left( f\right) } }\).

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 13 cze 2021, o 19:27 Niech \(\displaystyle{ f \subseteq X\times Y}\) będzie injekcją. Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\) oraz dowolne \(\displaystyle{ y \in Y\ }\). Wówczas jeżeli \(\displaystyle{ \left( y, x_{1} \right),\left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right),\left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest funkcją.
OK.
smo pisze: 13 cze 2021, o 19:27Ustalmy dowolne \(\displaystyle{ x \in X}\) oraz dowolne \(\displaystyle{ y_{1}, y_{2} \in Y}\). Jeżeli \(\displaystyle{ \left( x, y_{1} \right),\left( x, y_{2} \right) \in f}\) to \(\displaystyle{ \left( y_{1},x \right),\left( y_{2},x \right) \in f^{-1}}\). Ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\), a wówczas \(\displaystyle{ f^{-1}}\) jest injekcją.
Wnioskowanie zapisane w nieodpowiedniej kolejności. Ustalasz dowolne \(\displaystyle{ x \in X}\) i \(\displaystyle{ y_{1}, y_{2} \in Y}\) takie, że \(\displaystyle{ \left( y_{1},x \right),\left( y_{2},x \right) \in f^{-1}}\). I dopiero teraz korzystasz z definicji relacji odwrotnej itd.
smo pisze: 13 cze 2021, o 19:27 Ustalmy dowolne \(\displaystyle{ y=f\left( x\right) \in rng\left( f\right) =dom\left( f^{-1} \right) }\).
Tak tego nie zapisujemy. Najpierw ustalasz \(\displaystyle{ y}\), a potem stwierdzasz istnienie \(\displaystyle{ x}\) takiego, że \(\displaystyle{ y=f(x)}\).
smo pisze: 13 cze 2021, o 19:27 Wówczas z def. \(\displaystyle{ f\circ f^{-1} =\left\{ \left( f\left( x\right),f\left( x\right) \right) \in Y\times Y:\ istnieje\ takie\ x \in X,\ że\ \left( f\left( x\right),x \right) \in f^{-1}\ oraz\ \left( x,f\left( x\right) \right)\in f \right\} }\).
A z jakiej definicji (i czego) korzystasz? Bo na pewno nie jest to definicja złożenia (ani funkcji, ani relacji).

JK

PS
Nawiasem mówiąc, w tym zadaniu korzystasz z innej definicji pojęcia funkcji niż w poprzednich swoich zadaniach. Jest to definicja równoważna, ale powinieneś być świadom tej różnicy.
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Nawiasem mówiąc, w tym zadaniu korzystasz z innej definicji pojęcia funkcji niż w poprzednich swoich zadaniach. Jest to definicja równoważna, ale powinieneś być świadom tej różnicy.
Rozumiem to tak, że jeżeli \(\displaystyle{ f}\) jest funkcją to zapis "\(\displaystyle{ f:X \rightarrow Y}\)" oznacza, że \(\displaystyle{ X=dom\left( f\right) }\) oraz \(\displaystyle{ rng\left( f\right) \subseteq Y}\). Zapis "\(\displaystyle{ f \subseteq X\times Y}\)" oznacza, że funkcja \(\displaystyle{ f}\) jest iloczynem kartezjańskim i jeżeli para uporządkowana \(\displaystyle{ \left( x,y\right) \in f}\) to jest to równoważne z tym, że \(\displaystyle{ y=f\left( x\right) }\). Z zapisu \(\displaystyle{ f \subseteq X\times Y}\) nie wynika, że \(\displaystyle{ dom\left( f\right) =X}\). Wówczas dziedzina funkcji \(\displaystyle{ f}\) jest podzbiorem zbioru \(\displaystyle{ X}\).
W związku z tym dowód powyższego twierdzenia sformułowałbym inaczej:
niech \(\displaystyle{ f \subseteq X\times Y}\) będzie injekcją. Jeżeli \(\displaystyle{ \left( y, x_{1} \right), \left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right), \left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest funkcją. Niech \(\displaystyle{ \left( y_{1},x \right), \left( y_{2},x \right) \in f^{-1}}\). Ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\), a wówczas \(\displaystyle{ f^{-1}}\) jest injekcją.

Z def. złożenia relacji mamy, że
\(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in Y\times Y: istnieje\ x \in dom\left( f\right)=rng\left( f^{-1} \right)\ takie, że\ \left( y,x\right) \in f^{-1}\ oraz\ \left( x,y\right) \in f\right\} }\). Wówczas \(\displaystyle{ y=f\left( x\right) }\), a więc \(\displaystyle{ f\circ f^{-1} =\left\{ \left( f\left( x\right),f\left( x\right) \right) \in Y\times Y: f\left( x\right) \in rng\left( f\right) =dom\left( f^{-1} \right), x \in dom\left( f\right) \right\}=\left\{ \left( y,y\right) \in Y\times Y: y=f\left( x\right) \in rng\left( f\right) \right\}= id_{rng\left( f\right) } }\) jest relacją identycznościową na zbiorze \(\displaystyle{ rng\left( f\right) \subseteq Y}\).
Z def. złożenia relacji wynika, że \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X:\ istnieje\ y \in dom\left( f^{-1} \right)=rng\left( f\right)\ takie, że\ \left( x,y\right) \in f\ oraz\ \left( y,x\right) \in f^{-1} \right\} }\).
Skoro \(\displaystyle{ y=f\left( x\right) }\) to \(\displaystyle{ \left(x,y \right) \in f}\), a więc \(\displaystyle{ \left( y,x\right) \in f^{-1}}\) czyli \(\displaystyle{ x= f^{-1}\left( y\right) }\). Wówczas \(\displaystyle{ f^{-1}\circ f =\left\{ \left( f^{-1}\left( y\right), f^{-1}\left( y\right) \right) \in X\times X: f^{-1}\left( y\right) =x \in dom\left( f\right)=rng\left( f^{-1} \right), y \in rng\left( f\right) \right\}=\left\{ \left( x,x\right) \in X\times X: x \in dom\left( f\right) \right\}= id_{dom\left( f\right) } }\) jest relacją identycznościową na zbiorze \(\displaystyle{ dom\left( f\right) \subseteq X}\).

DS
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 16 cze 2021, o 15:01Rozumiem to tak, że jeżeli \(\displaystyle{ f}\) jest funkcją to zapis "\(\displaystyle{ f:X \rightarrow Y}\)" oznacza, że \(\displaystyle{ X=dom\left( f\right) }\) oraz \(\displaystyle{ rng\left( f\right) \subseteq Y}\).
Tak.
smo pisze: 16 cze 2021, o 15:01Zapis "\(\displaystyle{ f \subseteq X\times Y}\)" oznacza, że funkcja \(\displaystyle{ f}\) jest iloczynem kartezjańskim
Funkcja nie jest iloczynem kartezjańskim, tylko podzbiorem iloczynu kartezjańskiego (czyli relacją) o własności jednoznaczności - nie ma w nim dwóch par o tym samym poprzedniku i różnych następnikach.
smo pisze: 16 cze 2021, o 15:01i jeżeli para uporządkowana \(\displaystyle{ \left( x,y\right) \in f}\) to jest to równoważne z tym, że \(\displaystyle{ y=f\left( x\right) }\).
Zapis \(\displaystyle{ y=f\left( x\right) }\) jest wygodniejszą formą zapisu tego, że \(\displaystyle{ \left( x,y\right) \in f }\).
smo pisze: 16 cze 2021, o 15:01Z zapisu \(\displaystyle{ f \subseteq X\times Y}\) nie wynika, że \(\displaystyle{ dom\left( f\right) =X}\). Wówczas dziedzina funkcji \(\displaystyle{ f}\) jest podzbiorem zbioru \(\displaystyle{ X}\).
W związku z tym dowód powyższego twierdzenia sformułowałbym inaczej:
niech \(\displaystyle{ f \subseteq X\times Y}\) będzie injekcją. Jeżeli \(\displaystyle{ \left( y, x_{1} \right), \left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right), \left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest funkcją. Niech \(\displaystyle{ \left( y_{1},x \right), \left( y_{2},x \right) \in f^{-1}}\). Ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\), a wówczas \(\displaystyle{ f^{-1}}\) jest injekcją.
OK, ale przed stwierdzeniem "Ponieważ \(\displaystyle{ f}\) jest funkcją to" skorzystałbym z definicji relacji odwrotnej, bo inaczej nie jest do końca jasne, do czego odnosi się to stwierdzenie.
smo pisze: 16 cze 2021, o 15:01Z def. złożenia relacji mamy, że
\(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in Y\times Y: istnieje\ x \in dom\left( f\right)=rng\left( f^{-1} \right)\ takie, że\ \left( y,x\right) \in f^{-1}\ oraz\ \left( x,y\right) \in f\right\} }\).
Nieprawda, to nie jest definicja złożenia relacji.
smo pisze: 16 cze 2021, o 15:01 Z def. złożenia relacji wynika, że \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X:\ istnieje\ y \in dom\left( f^{-1} \right)=rng\left( f\right)\ takie, że\ \left( x,y\right) \in f\ oraz\ \left( y,x\right) \in f^{-1} \right\} }\)
Nieprawda, to nie jest definicja złożenia relacji.

JK
smo
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 17 mar 2021, o 22:01
Płeć: Mężczyzna
wiek: 39
Podziękował: 4 razy

Re: Injekcja, złożenie funkcji

Post autor: smo »

Dziękuję za wszystkie wyjaśnienia.

Dowód:
niech \(\displaystyle{ f \subseteq X \times Y}\) będzie injekcją. Jeżeli \(\displaystyle{ \left( y, x_{1} \right),\left( y, x_{2} \right) \in f^{-1}}\) to \(\displaystyle{ \left( x_{1},y \right),\left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\), a zatem \(\displaystyle{ f^{-1}}\) jest funkcją. Niech \(\displaystyle{ \left( y_{1},x \right),\left( y_{2},x \right) \in f^{-1} \subseteq Y\times X}\). Ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\), a wówczas \(\displaystyle{ f^{-1}}\) jest injekcją.

Z def. złożenia relacji wynika, że \(\displaystyle{ f\circ f^{-1} \subseteq Y\times Y}\). Zatem \(\displaystyle{ f\circ f^{-1} \subseteq \left\{ \left( y,y\right) \in Y\times Y: y \in Y \right\}}\) oraz \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in Y\times Y:\ istnieje\ x \in X\ takie,\ że\ \left( y,x\right) \in f^{-1}\ oraz\ \left( x,y\right) \in f \right\} }\). Ponieważ jednak \(\displaystyle{ f\circ f^{-1}}\) jest jednocześnie funkcją to \(\displaystyle{ f\circ f^{-1} \subseteq \left[ dom\left( f^{-1} \right)\times rng\left( f\right) \right] \subseteq Y}\), a skoro \(\displaystyle{ dom\left( f^{-1} \right) =rng\left( f\right) }\) to możemy zapisać, że \(\displaystyle{ f\circ f^{-1} \subseteq \left[ rng\left( f\right)\times rng\left( f\right) \right]}\). Wówczas \(\displaystyle{ f\circ f^{-1} \subseteq \left\{ \left( y,y\right) \in \left[ rng\left( f\right)\times rng\left( f\right): y \in rng\left( f\right) \right] \right\}}\) oraz \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in \left[ rng\left( f\right)\times rng\left( f\right) \right]:\ istnieje\ x \in dom\left( f\right)=rng\left( f^{-1} \right)\ takie,\ że\ \left( y,x\right) \in f^{-1}\ oraz\ \left( x,y\right) \in f \right\} }\). Skoro \(\displaystyle{ \left( x,y\right) \in f}\) to \(\displaystyle{ y=f\left( x\right) }\). Zatem \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y,y\right) \in \left[ rng\left( f\right)\times rng\left( f\right) \right]: y=f\left( x\right) \in rng\left( f\right) \right\} }\). Jednocześnie z def. \(\displaystyle{ id_{rng\left( f\right) } =\left\{ \left( y,y\right) \in Y\times Y: y \in rng\left( f\right) \right\} }\), a ponieważ \(\displaystyle{ y \in rng\left( f\right) \subseteq Y}\) to \(\displaystyle{ \left( y,y\right) \in \left[ rng\left( f\right)\times rng\left( f\right) \right] \subseteq Y\times Y}\). Wówczas \(\displaystyle{ id_{rng\left( f\right) } =\left\{ \left( y,y\right) \in \left[ rng\left( f\right)\times rng\left( f\right) \right]: y \in rng\left( f\right) \right\}=f\circ f^{-1} }\).
Z def. złożenia relacji mamy, że \(\displaystyle{ f^{-1}\circ f \subseteq X\times X}\). Wówczas \(\displaystyle{ f^{-1}\circ f \subseteq \left\{ \left( x,x\right) \in X\times X: x \in X \right\}}\) oraz \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in X\times X:\ istnieje\ y \in Y\ takie,\ że\ \left( x,y\right) \in f\ oraz\ \left( y,x\right) \in f^{-1} \right\} }\). Ale \(\displaystyle{ f^{-1}\circ f}\) jest także funkcją, a więc \(\displaystyle{ f^{-1}\circ f \subseteq \left[ dom\left( f\right)\times rng\left( f^{-1} \right) \right] \subseteq X}\). Ponieważ \(\displaystyle{ dom\left( f\right) =rng\left( f^{-1} \right) }\) to \(\displaystyle{ f^{-1}\circ f \subseteq \left[ dom\left( f\right)\times dom\left( f\right) \right]}\). Wówczas \(\displaystyle{ f^{-1}\circ f \subseteq \left\{ \left( x,x\right) \in \left[ dom\left( f\right)\times dom\left( f\right) \right]: x \in dom\left( f\right) \right\}}\) oraz \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x,x\right) \in \left[ dom\left( f\right)\times dom\left( f\right) \right]:\ istnieje\ y \in rng\left( f\right)=dom\left( f^{-1} \right) \ takie,\ że\ \left( x,y\right) \in f\ oraz\ \left( y,x\right) \in f^{-1} \right\} }\). Skoro istnieje \(\displaystyle{ y \in dom\left( f^{-1} \right)}\) to \(\displaystyle{ f^{-1}\left( y\right) =x}\). Ponieważ jednocześnie \(\displaystyle{ y=f\left( x\right) }\) to \(\displaystyle{ f^{-1}\left( y\right) = f^{-1}\left( f\left( x\right) \right) =\left( f^{-1}\circ f \right)\left( x\right) }\). Zatem \(\displaystyle{ x=\left( f^{-1}\circ f \right)\left( x\right) }\). Wówczas \(\displaystyle{ f^{-1}\circ f =\left\{ \left( f^{-1}\left( y\right),\left( f^{-1}\circ f \right)\left( x\right) \right) \in \left[ dom\left( f\right)\times dom\left( f\right) \right] : f^{-1}\left( y\right) =\left( f^{-1}\circ f \right)\left( x\right) \in dom\left( f\right) \right\}=\left\{ \left( x,x\right) \in \left[ dom\left( f\right)\times dom\left( f\right) \right]:x \in dom\left( f\right) \right\}= id_{dom\left( f\right) } }\).
DS
ODPOWIEDZ