Injekcja, złożenie funkcji

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
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: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 18 cze 2021, o 14:23 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ą.
Tak jak pisałem, nadal brakuje jednego przejścia:

"Niech \(\displaystyle{ \left( y_{1},x \right),\left( y_{2},x \right) \in f^{-1} \subseteq Y\times X}\). Wtedy \(\displaystyle{ \left( x, y_{1} \right),\left( x, y_{2} \right) \in f \subseteq Y\times X}\), a ponieważ \(\displaystyle{ f}\) jest funkcją, to \(\displaystyle{ y_{1} = y_{2} }\), czyli \(\displaystyle{ f^{-1}}\) jest injekcją."
smo pisze: 18 cze 2021, o 14:23 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\} }\).
Nieprawda.

Z definicji masz tylko \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y_1,y_2\right) \in Y\times Y:(\exists x \in X)(\left( y_1,x\right) \in f^{-1}\land \left( x,y_2\right) \in f )\right\}. }\)

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ę.

To raz jeszcze:
niech \(\displaystyle{ f: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}\). Wówczas \(\displaystyle{ \left( x,y _{1} \right),\left( x, y_{2} \right) \in f \subseteq X \times Y}\), a ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\) czyli \(\displaystyle{ f^{-1}}\) jest injekcją.
Niech \(\displaystyle{ \left( y_{1}, x_{2} \right) \in f^{-1},\left( x_{1}, y_{2} \right) \in f }\). Ponieważ \(\displaystyle{ dom\left( f\circ f^{-1} \right) =rng\left( f\right)=dom\left( f^{-1} \right) }\) to \(\displaystyle{ \left( y_{1}, y_{2} \right) \in f\circ f^{-1}}\). Wówczas \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y_{1}, y_{2} \right) \in Y\times Y:\ istnieją\ x_{1}, x_{2} \in X\ takie,\ że\ \left( y_{1}, x_{2} \right) \in f^{-1}\ oraz\ \left( x_{1}, y_{2} \right) \in f \right\} }\). Ponieważ \(\displaystyle{ f\circ f^{-1}}\) jest funkcją więc \(\displaystyle{ x_{1}, x_{2} \in dom\left( f\right) \subseteq X}\) oraz \(\displaystyle{ y_{1} =f\left( x_{2} \right), y_{2}=f\left( x_{1} \right) \in rng\left( f\right) \subseteq Y }\). Zatem \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y_{1}, y_{2} \right) \in Y\times Y:\ istnieją\ x_{1}, x_{2} \in dom\left( f\right)\ takie,\ że\ \left( y_{1}, x_{2} \right) \in f^{-1}\ oraz\ \left( x_{1}, y_{2} \right) \in f \right\} }\). Czyli \(\displaystyle{ f\circ f^{-1} =\left\{ \left( y_{1}, y_{2} \right) \in Y\times Y: y_{1} =f\left( x_{2} \right), y_{2} =f\left( x_{1} \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}\).
Skoro \(\displaystyle{ x_{1}, x_{2} \in dom\left( f\right)}\), oraz \(\displaystyle{ dom\left( f^{-1}\circ f \right) =dom\left( f\right)=rng\left( f^{-1} \right) }\) to \(\displaystyle{ \left( x_{1}, x_{2} \right) \in f^{-1}\circ f}\). Jednocześnie \(\displaystyle{ y_{1}, y_{2} \in rng\left( f\right)}\), a wówczas \(\displaystyle{ f^{-1}\circ f =\left\{ \left( x_{1}, x_{2} \right) \in X\times X: x_{1}, x_{2} \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: 34125
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: 20 cze 2021, o 16:44 niech \(\displaystyle{ f: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}\). Wówczas \(\displaystyle{ \left( x,y _{1} \right),\left( x, y_{2} \right) \in f \subseteq X \times Y}\), a ponieważ \(\displaystyle{ f}\) jest funkcją to \(\displaystyle{ y_{1} = y_{2} }\) czyli \(\displaystyle{ f^{-1}}\) jest injekcją.
OK.
smo pisze: 20 cze 2021, o 16:44 Niech \(\displaystyle{ \left( y_{1}, x_{2} \right) \in f^{-1},\left( x_{1}, y_{2} \right) \in f }\).
No nie. Co to ma oznaczać?

Chcesz pokazać, że \(\displaystyle{ f\circ f^{−1}=\text{id}_{rng(f)}}\), ustalasz więc dowolną parę \(\displaystyle{ (y_1,y_2)}\) i chcesz pokazać, że \(\displaystyle{ (y_1,y_2)\in f\circ f^{−1} \Leftrightarrow (y_1,y_2)\in\text{id}_{rng(f)}}\). Warto przypomnieć, że \(\displaystyle{ \text{id}_{rng(f)}=\{(y,y):y\in rng(f)\}}\).

Wynikanie \(\displaystyle{ \left( \Leftarrow \right) }\) jest proste. Skoro \(\displaystyle{ (y_1,y_2)\in\text{id}_{rng(f)}}\), to (z powyższej def. \(\displaystyle{ \text{id}_{rng(f)}}\)) wiemy \(\displaystyle{ y_1=y_2}\) oraz istnieje \(\displaystyle{ x\in X}\) takie, że \(\displaystyle{ y_1=y_2=f(x)}\). Ale to oznacza \(\displaystyle{ \red{\left( x,y_1\right)\in f} }\) i \(\displaystyle{ \left( x,y_2\right)\in f }\). Ale czerwone jest równoważne z \(\displaystyle{ \left( y_1,x\right)\in f^{-1} }\), a skoro wiemy, że istnieje \(\displaystyle{ x\in X}\) takie, że \(\displaystyle{ \left( y_1,x\right)\in f^{-1} }\) i \(\displaystyle{ \left( x,y_2\right)\in f }\), to z definicji złożenia relacji mamy \(\displaystyle{ (y_1,y_2)\in f\circ f^{−1}}\).

W drugą stronę, jeśli \(\displaystyle{ (y_1,y_2)\in f\circ f^{−1}}\), to z definicji złożenia relacji wiemy, że istnieje \(\displaystyle{ x\in X}\) takie, że \(\displaystyle{ \left( y_1,x\right)\in f^{-1} }\) i \(\displaystyle{ \left( x,y_2\right)\in f }\). Ale wtedy \(\displaystyle{ \left( x,y_1\right)\in f}\) i \(\displaystyle{ \left( x,y_2\right)\in f }\), a ponieważ \(\displaystyle{ f}\) jest funkcją, więc \(\displaystyle{ y_1=y_2=y}\). Dodatkowo skoro istnieje \(\displaystyle{ x\in X}\) takie, że \(\displaystyle{ \left( x,y\right)\in f }\), to \(\displaystyle{ y\in rng(f).}\) Ale wtedy \(\displaystyle{ (y_1,y_2)=(y,y)\in \text{id}_{rng(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ę. To teraz dowód równości: \(\displaystyle{ f^{-1}\circ f = id_{dom\left( f\right) } }\).
Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in id_{dom\left( f\right) }}\). Z def. \(\displaystyle{ id_{dom\left( f\right) } =\left\{ \left( x,x\right):x \in dom\left( f\right) \right\} }\). Zatem \(\displaystyle{ x_{1} = x_{2} }\). Z def. złożenia relacji wynika, że istnieje \(\displaystyle{ y \in Y}\) takie, że \(\displaystyle{ \left( x_{1},y \right) \in f,\left( y, x_{2} \right) \in f^{-1}}\). Ponieważ \(\displaystyle{ dom\left( f^{-1}\circ f \right) =dom\left( f\right)=rng\left( f^{-1} \right) }\) to z def. złożenia relacji \(\displaystyle{ \left( x_{1}, x_{2} \right) \in f^{-1}\circ f}\).

Jeżeli \(\displaystyle{ \left( x_{1}, x_{2} \right) \in f^{-1}\circ f}\) to z def. złożenia relacji wynika, że istnieje \(\displaystyle{ y \in Y}\) takie, że \(\displaystyle{ \left( x_{1},y \right) \in f}\) oraz \(\displaystyle{ \left( y, x_{2} \right) \in f^{-1}}\). Wówczas \(\displaystyle{ \left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f^{-1}\circ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\). Jednocześnie \(\displaystyle{ dom\left( f^{-1}\circ f \right) =dom\left( f\right)=rng\left( f^{-1} \right) }\) tak więc \(\displaystyle{ x_{1} = x_{2}=x \in dom\left( f\right) }\), a zatem \(\displaystyle{ \left( x_{1}, x_{2} \right)=\left( x,x\right) \in id_{dom\left( f\right) } }\).

DS
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: Injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 21 cze 2021, o 15:51 Dziękuję. To teraz dowód równości: \(\displaystyle{ f^{-1}\circ f = id_{dom\left( f\right) } }\).
Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in id_{dom\left( f\right) }}\).
Ustalmy dowolne \(\displaystyle{ \left( x_{1}, x_{2}\right) \in id_{dom\left( f\right) }}\).
smo pisze: 21 cze 2021, o 15:51Z def. \(\displaystyle{ id_{dom\left( f\right) } =\left\{ \left( x,x\right):x \in dom\left( f\right) \right\} }\). Zatem \(\displaystyle{ x_{1} = x_{2} }\). Z def. złożenia relacji wynika, że istnieje \(\displaystyle{ y \in Y}\) takie, że \(\displaystyle{ \left( x_{1},y \right) \in f,\left( y, x_{2} \right) \in f^{-1}}\).
Źle, przecież tu nie ma żadnego złożenia!

Ponieważ \(\displaystyle{ x_1\in dom(f)}\), więc istnieje \(\displaystyle{ y\in Y}\) takie, że \(\displaystyle{ (x_1,y)\in f}\), czyli także \(\displaystyle{ (x_2,y)\in f}\). Wtedy \(\displaystyle{ \left( y, x_{2} \right) \in f^{-1}}\) i z def. złożenia relacji mamy \(\displaystyle{ \left( x_1, x_{2} \right) \in f^{-1}\circ f}\), czego należało dowieść.
smo pisze: 21 cze 2021, o 15:51Jeżeli \(\displaystyle{ \left( x_{1}, x_{2} \right) \in f^{-1}\circ f}\) to z def. złożenia relacji wynika, że istnieje \(\displaystyle{ y \in Y}\) takie, że \(\displaystyle{ \left( x_{1},y \right) \in f}\) oraz \(\displaystyle{ \left( y, x_{2} \right) \in f^{-1}}\). Wówczas \(\displaystyle{ \left( x_{2},y \right) \in f}\). Ponieważ \(\displaystyle{ f^{-1}\circ f}\) jest injekcją to \(\displaystyle{ x_{1} = x_{2} }\).
Ponieważ \(\displaystyle{ f}\) jest injekcją, więc \(\displaystyle{ x_{1} = x_{2} }\).
smo pisze: 21 cze 2021, o 15:51Jednocześnie \(\displaystyle{ dom\left( f^{-1}\circ f \right) =dom\left( f\right)=rng\left( f^{-1} \right) }\) tak więc \(\displaystyle{ x_{1} = x_{2}=x \in dom\left( f\right) }\), a zatem \(\displaystyle{ \left( x_{1}, x_{2} \right)=\left( x,x\right) \in id_{dom\left( f\right) } }\).
Ponadto jeśli \(\displaystyle{ \left( x_{1},y \right) \in f}\), to \(\displaystyle{ x_{1}\in dom\left( f\right) }\), a zatem \(\displaystyle{ \left( x_{1}, x_{2} \right)=\left( x,x\right) \in id_{dom\left( f\right) } }\).

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ę.

DS
ODPOWIEDZ