Surjekcja, 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

Surjekcja, injekcja, złożenie funkcji

Post autor: smo »

Tutaj chciałbym przedstawić dowód twierdzenia:
"jeżeli \(\displaystyle{ g:X \rightarrow Z}\) jest surjekcją oraz \(\displaystyle{ h:Z \rightarrow Y}\) jest injekcją to złożenie \(\displaystyle{ h\circ g=f}\), gdzie \(\displaystyle{ f:X \rightarrow Y}\)."

Niech \(\displaystyle{ g:X \rightarrow Z}\) będzie surjekcją, a \(\displaystyle{ h:Z \rightarrow Y}\) injekcją. Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\). Wówczas skoro \(\displaystyle{ g}\) jest surjekcją to \(\displaystyle{ g\left( x_{1} \right), g\left( x_{2} \right) \in dom\left( h\right)}\). Ponieważ \(\displaystyle{ h}\) jest injekcją to jeżeli \(\displaystyle{ g\left( x_{1} \right) \neq g\left( x_{2} \right)}\) to \(\displaystyle{ h\left( g\left( x_{1} \right) \right) \neq h\left( g\left( x_{2} \right) \right)}\). A skoro \(\displaystyle{ h\left( g\left( x_{1} \right) \right) =\left( h\circ g\right)\left( x_{1} \right) }\) oraz \(\displaystyle{ h\left( g\left( x_{2} \right) \right) =\left( h\circ g\right)\left( x_{2} \right) }\) to \(\displaystyle{ \left( h\circ g\right)\left( x_{1} \right) \neq \left( h\circ g\right)\left( x_{2} \right)}\). Wówczas \(\displaystyle{ x_{1} \neq x_{2}}\), a zatem \(\displaystyle{ g}\) jest injekcją. Korzystając z odpowiedniego twierdzenia wnioskujemy, że \(\displaystyle{ h\circ g}\) jest także różnowartościowa. Wówczas możemy znaleźć dowolną funkcję \(\displaystyle{ f:X \rightarrow Y}\) taką, że \(\displaystyle{ f\left( x_{1} \right) =\left( h\circ g\right)\left( x_{1} \right) }\) oraz \(\displaystyle{ f\left( x_{2} \right) =\left( h\circ g\right)\left( x_{2} \right) }\) dla dowolnych \(\displaystyle{ x_{1}, x_{2} \in X}\). Zatem \(\displaystyle{ h\circ g=f}\).

Jeżeli \(\displaystyle{ g}\) nie byłaby surjekcją to \(\displaystyle{ g\left( x_{1} \right), g\left( x_{2} \right)}\) mogłyby nie należeć do \(\displaystyle{ dom\left( h\right) }\). Wówczas funkcja \(\displaystyle{ h\circ g}\) nie przyjmowałaby wartości dla \(\displaystyle{ x_{1}, x_{2} \in X}\) tak jak dowolna funkcja \(\displaystyle{ f:X \rightarrow Y}\) czyli \(\displaystyle{ h\circ g \neq f}\).
Gdyby \(\displaystyle{ h}\) nie była injekcją to dla \(\displaystyle{ g\left( x_{1} \right) \neq g\left( x_{2} \right) \in dom\left( h\right)}\) mielibyśmy \(\displaystyle{ h\left( g\left( x_{1} \right) \right) =h\left( g\left( x_{2} \right) \right) }\), a zatem \(\displaystyle{ \left( h\circ g\right)\left( x_{1} \right) =\left( h\circ g\right)\left( x_{2} \right) }\). Wówczas jeżeli \(\displaystyle{ f:X \rightarrow Y}\) byłaby injekcją to dla \(\displaystyle{ x_{1} \neq x_{2}}\) byłoby \(\displaystyle{ f\left( x_{1} \right) \neq f\left( x_{2} \right)}\) tak więc \(\displaystyle{ f\left( x_{1} \right) \neq f\left( x_{2} \right) \neq \left( h\circ g\right)\left( x_{1} \right) =\left( h\circ g\right)\left( x_{2} \right) }\) czyli w konsekwencji \(\displaystyle{ h\circ g \neq f}\).

DS
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: a4karo »

Jeżeli przyjąć `Z=Y` i `h=id` to w pierwszej części "pokazałeś", że każda surjekcja jest injekcją

W drugiej części nie ma takiej możliwości, żeby obrazy elementów z `X` nie należały do dziedziny `h`
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 6 cze 2021, o 13:30 Tutaj chciałbym przedstawić dowód twierdzenia:
"jeżeli \(\displaystyle{ g:X \rightarrow Z}\) jest surjekcją oraz \(\displaystyle{ h:Z \rightarrow Y}\) jest injekcją to złożenie \(\displaystyle{ h\circ g=f}\), gdzie \(\displaystyle{ f:X \rightarrow Y}\)."
Ale to nie jest żadne twierdzenie. Twierdzisz, że jeśli \(\displaystyle{ g:X \rightarrow Z}\) i \(\displaystyle{ h:Z \rightarrow Y}\), to \(\displaystyle{ h\circ g: X \rightarrow Y}\) ? Przecież to definicja złożenia funkcji. Chyba o czymś zapomniałeś.

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

Post autor: smo »

To raz jeszcze:
"Dowolną funkcję \(\displaystyle{ f:X \rightarrow Y}\) można przedstawić w postaci złożenia dwóch funkcji \(\displaystyle{ g:X \rightarrow Z}\) i \(\displaystyle{ h:Z \rightarrow Y}\)(gdzie \(\displaystyle{ Z}\) jest pewnym zbiorem) takich, że \(\displaystyle{ g}\) jest surjekcją, a \(\displaystyle{ h}\) injekcją."
Dowód:
niech \(\displaystyle{ g:X \rightarrow Z}\) będzie surjekcją, a \(\displaystyle{ h:Z \rightarrow Y}\) injekcją. Ustalmy dowolne \(\displaystyle{ x_{1}, x_{2} \in X}\). Ponieważ \(\displaystyle{ g}\) jest surjekcją to \(\displaystyle{ g\left( x_{1} \right) = z_{1}, g\left( x_{2} \right) = z_{2} }\) gdzie \(\displaystyle{ z_{1}, z_{2} \in Z}\) są dowolnymi elementami. Wówczas skoro \(\displaystyle{ h}\) jest injekcją to dla \(\displaystyle{ g\left( x_{1} \right) \neq g\left( x_{2} \right)}\) mamy \(\displaystyle{ h\left( g\left( x_{1} \right) \right) =\left( h\circ g\right)\left( x_{1} \right)=h\left( z_{1} \right) \neq h\left( g\left( x_{2} \right) \right)=\left( h\circ g\right)\left( x_{2} \right)=h\left( z_{2} \right) }\). Ponieważ \(\displaystyle{ h\left( g\left( x_{1} \right) \right), h\left( g\left( x_{2} \right) \right) \in Y}\) niech \(\displaystyle{ h\left( g\left( x_{1} \right) \right) =h\left( z_{1} \right)= y_{1} }\) oraz \(\displaystyle{ h\left( g\left( x_{2} \right) \right) =h\left( z_{2} \right)= y_{2} }\), gdzie \(\displaystyle{ y_{1}, y_{2} \in Y}\). Wówczas \(\displaystyle{ \left( h\circ g\right)\left( x_{1} \right) = y_{1} }\) oraz \(\displaystyle{ \left( h\circ g\right)\left( x_{2} \right) = y_{2} }\). Zatem \(\displaystyle{ y_{1} =f\left( x_{1} \right)=\left( h\circ g\right)\left( x_{1} \right) }\), \(\displaystyle{ y_{2} =f\left( x_{2} \right)=\left( h\circ g\right)\left( x_{2} \right) }\) czyli funkcja \(\displaystyle{ h\circ g:X \rightarrow Y}\) przyjmuje swoje wartości dla dowolnych \(\displaystyle{ x_{1}, x_{2} \in X=dom\left( f\right) }\). To oznacza, że \(\displaystyle{ h\circ g}\) jest dowolną funkcją \(\displaystyle{ f:X \rightarrow Y}\).

Gdyby funkcja \(\displaystyle{ g}\) nie była surjekcją to funkcja \(\displaystyle{ f}\) mogłaby przyjmować takie wartości funkcji \(\displaystyle{ h}\), które byłyby różne od wartości przyjmowanych przez daną funkcję \(\displaystyle{ h\circ g}\). Rzecz jasna istniałyby jednocześnie takie funkcje\(\displaystyle{ f}\), które przyjmowałyby wartości dla funkcji \(\displaystyle{ h\circ g}\)(wówczas \(\displaystyle{ h\circ g=f}\)) ale równość \(\displaystyle{ h\circ g=f}\) nie byłaby spełniona przez każdą funkcję \(\displaystyle{ f}\).
Gdyby funkcja \(\displaystyle{ h}\) nie była injekcją to dla \(\displaystyle{ g\left( x_{1} \right), g\left( x_{2} \right) \in dom\left( h\right)}\) takich, że \(\displaystyle{ g\left( x_{1} \right) \neq g\left( x_{2} \right) }\) mielibyśmy \(\displaystyle{ \left( h\circ g\right)\left( x_{1} \right) =\left( h\circ g\right)\left( x_{2} \right) }\). Wówczas gdyby funkcja \(\displaystyle{ f}\) była injekcją to dla \(\displaystyle{ x_{1} \neq x_{2}}\) mielibyśmy \(\displaystyle{ f\left( x_{1} \right) \neq f\left( x_{2} \right)}\). Zatem \(\displaystyle{ f\left( x_{1} \right) \neq f\left( x_{2} \right) \neq \left( h\circ g\right)\left( x_{1} \right)=\left( h\circ g\right)\left( x_{2} \right) }\).

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

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 8 cze 2021, o 19:39 To raz jeszcze:
"Dowolną funkcję \(\displaystyle{ f:X \rightarrow Y}\) można przedstawić w postaci złożenia dwóch funkcji \(\displaystyle{ g:X \rightarrow Z}\) i \(\displaystyle{ h:Z \rightarrow Y}\)(gdzie \(\displaystyle{ Z}\) jest pewnym zbiorem) takich, że \(\displaystyle{ g}\) jest surjekcją, a \(\displaystyle{ h}\) injekcją."
Dowód:
niech \(\displaystyle{ g:X \rightarrow Z}\) będzie surjekcją, a \(\displaystyle{ h:Z \rightarrow Y}\) injekcją.
Nie, zupełnie nie o to chodzi.

Ty masz pokazać, że dla dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\) istnieją funkcje \(\displaystyle{ g:X \rightarrow Z}\) i \(\displaystyle{ h:Z \rightarrow Y}\) takie, że \(\displaystyle{ g}\) jest surjekcją, \(\displaystyle{ h}\) injekcją i \(\displaystyle{ f=h\circ g.}\)

Masz zatem ustalić dowolną funkcję \(\displaystyle{ f}\) i dla tej funkcji wskazać konkretne funkcje \(\displaystyle{ g}\) i \(\displaystyle{ h}\), które mają podane własności.

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

Post autor: smo »

Dziękuję.

Dowód:
niech \(\displaystyle{ f:X \rightarrow Y}\) będzie dowolną funkcją oraz \(\displaystyle{ Z}\) pewnym zbiorem. Ustalmy dowolne \(\displaystyle{ z \in Z}\) oraz dowolne \(\displaystyle{ y \in Y}\). Rozważmy funkcję \(\displaystyle{ g:X \rightarrow Z}\) taką, że \(\displaystyle{ g\left( x\right) =z}\). Wówczas jeżeli dla dowolnego \(\displaystyle{ z \in Z}\) istnieje \(\displaystyle{ x \in X}\) takie, że \(\displaystyle{ z =g\left( x\right) }\) to funkcja \(\displaystyle{ g}\) jest surjekcją. Rozważmy funkcję \(\displaystyle{ h:Z \rightarrow Y}\). Ponieważ \(\displaystyle{ g}\) jest surjekcją zatem \(\displaystyle{ h\left( z\right) =h\left( g\left( x\right) \right) =y}\), a skoro jednocześnie \(\displaystyle{ z=g\left( x\right) }\) to wówczas funkcja \(\displaystyle{ h}\) jest injekcją. Mamy zatem \(\displaystyle{ h\left( z\right) =h\left( g\left( x\right) \right)=\left( h\circ g\right)\left( x\right)=y}\). Wówczas dla dowolnego \(\displaystyle{ y \in Y}\) istnieje \(\displaystyle{ x \in X}\) takie, że \(\displaystyle{ y=\left( h\circ g\right)\left( x\right) }\), a więc \(\displaystyle{ h\circ g=f:X \rightarrow Y}\).

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

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 9 cze 2021, o 22:31niech \(\displaystyle{ f:X \rightarrow Y}\) będzie dowolną funkcją oraz \(\displaystyle{ Z}\) pewnym zbiorem. Ustalmy dowolne \(\displaystyle{ z \in Z}\) oraz dowolne \(\displaystyle{ y \in Y}\). Rozważmy funkcję \(\displaystyle{ g:X \rightarrow Z}\) taką, że \(\displaystyle{ g\left( x\right) =z}\).
No ale to przecież nie ma sensu. Z wielu powodów. W ogóle nie zrozumiałeś, co należy zrobić.

Powtórzę: ustalasz tylko dowolną funkcję \(\displaystyle{ f:X \rightarrow Y}\). Cała resztę musisz konkretnie i jednoznacznie zdefiniować. Cała resztę, czyli zbiór \(\displaystyle{ Z}\) oraz funkcje \(\displaystyle{ g: X\to Z}\) i \(\displaystyle{ h: Z\to Y}\). Stwierdzenie "niech \(\displaystyle{ Z}\) będzie pewnym zbiorem" nie ma NIC wspólnego ze zdefiniowaniem tego zbioru. Podobnie jak stwierdzenie "Ustalmy dowolne \(\displaystyle{ z \in Z}\) oraz dowolne \(\displaystyle{ y \in Y}\). Rozważmy funkcję \(\displaystyle{ g:X \rightarrow Z}\) taką, że \(\displaystyle{ g\left( x\right) =z}\)" nie ma NIC wspólnego ze zdefiniowaniem funkcji \(\displaystyle{ g}\).

Dowód wygląda tak.

Ustalmy dowolną funkcję \(\displaystyle{ f:X \rightarrow Y}\). Niech \(\displaystyle{ Z=\text{rng}(f)}\) i niech funkcje \(\displaystyle{ g: X\to Z}\) i \(\displaystyle{ h: Z\to Y}\) będą zadane wzorami \(\displaystyle{ g(x)=f(x)}\) i \(\displaystyle{ h(x)=x}\). Wówczas funkcja \(\displaystyle{ g}\) jest surjekcją (bo \(\displaystyle{ \text{rng}(g)=\text{rng}(f)=Z}\)), a funkcja \(\displaystyle{ h}\) jest (oczywiście) injekcją i dla dowolnego \(\displaystyle{ x\in X}\) mamy \(\displaystyle{ h(g(x))=h(f(x))=f(x)}\), zatem \(\displaystyle{ h\circ g=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: Surjekcja, injekcja, złożenie funkcji

Post autor: smo »

Dziękuję. Teraz zaczynam widzieć o co chodziło.
Nie rozumiem jednak, że funkcję \(\displaystyle{ h:Z \rightarrow Y}\) można określić wzorem \(\displaystyle{ h\left( x\right) =x}\).

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

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 10 cze 2021, o 13:57 Nie rozumiem jednak, że funkcję \(\displaystyle{ h:Z \rightarrow Y}\) można określić wzorem \(\displaystyle{ h\left( x\right) =x}\).
Przecież \(\displaystyle{ Z=\text{rng}(f) \subseteq Y}\), więc spokojnie mogę to zrobić.

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

Post autor: smo »

To czy w takim razie nie powinno być \(\displaystyle{ h\left( f\left( x\right) \right) =y}\)? Bo skoro \(\displaystyle{ Z=rng\left( f\right) }\) to argumentami funkcji \(\displaystyle{ h:Z \rightarrow Y}\) są elementy \(\displaystyle{ f\left( x\right)}\). Po prostu nie rozumiem zapisu \(\displaystyle{ h\left( x\right) =x}\) bo wówczas oznaczałoby to, że \(\displaystyle{ h:X \rightarrow X}\).

DS
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: a4karo »

A jak byś zrozumiał zapis taki:
`f:X\to Y, f(p)=p`?
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: Surjekcja, injekcja, złożenie funkcji

Post autor: smo »

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

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 10 cze 2021, o 18:12 To czy w takim razie nie powinno być \(\displaystyle{ h\left( f\left( x\right) \right) =y}\)?
Nie.
smo pisze: 10 cze 2021, o 18:12Po prostu nie rozumiem zapisu \(\displaystyle{ h\left( x\right) =x}\) bo wówczas oznaczałoby to, że \(\displaystyle{ h:X \rightarrow X}\).
A skąd ten wniosek?

A czy rozumiesz, jaką funkcją jest \(\displaystyle{ f:\NN\to\RR, f(x)=x.}\)

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

Post autor: smo »

Rozumiem, że jest to funkcja odwzorowująca zbiór liczb naturalnych w zbiór liczb rzeczywistych ale nie znam takiego całościowego zapisu jaki Pan przedstawił(czyli z wyrażeniem \(\displaystyle{ f\left( x\right) =x}\)).

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

Re: Surjekcja, injekcja, złożenie funkcji

Post autor: Jan Kraszewski »

smo pisze: 10 cze 2021, o 20:44ale nie znam takiego całościowego zapisu jaki Pan przedstawił(czyli z wyrażeniem \(\displaystyle{ f\left( x\right) =x}\)).
Jakiego "całościowego zapisu"? Przecież to zwykły wzór funkcji. Określam dziedzinę, przeciwdziedzinę i wzór.

JK
ODPOWIEDZ