Na tym wykładzie zajmiemy się pewnymi szczególnymi relacjami, zwanymi funkcjami. Zdefiniujemy injekcje, surjekcje i bijekcje, zdefiniujemy funkcję odwrotną i wykażemy twierdzenie o istnieniu funkcji odwrotnej.
Niech \(X, Y\) będą zbiorami. Weźmy relację (czyli podzbiór \(X\times Y\)) tym razem oznaczoną przez \(f\).
Definicja 76. Relację \(f\subset X\times Y\) nazywamy funkcją wtedy i tylko wtedy gdy spełniony jest warunek
\[\forall _{x\in X} \, \exists !_{y\in Y} \ (x,y)\in f.\]
Równoważnie ten warunek możemy zapisać jako koniunkcję dwóch warunków:
1. \(\forall _{x\in X} \, \exists _{y\in Y} \ (x,y)\in f\)
2. \(\forall _{x\in X, y_1,y_2\in Y} \ ((x,y_1)\in f\wedge (x,y_2)\in f)\lra y_1=y_2.\)
Uwaga 77.
1. Dla funkcji (jak już zapewne wszyscy wiedzą) nie stosujemy zwyczajowo zapisu \((x,y)\in f\) ani \(xfy\) tylko piszemy \(f(x)=y\). Niemniej, na tym wykładzie będzie pojawiał się niekiedy zapis \((x,y)\in f\). Nie piszemy też \(f\subset X\times Y\) ale \(f: X\to Y\), ewentualnie \(X\stackrel {f}{\to }Y\).
2. Zbiór wszystkich funkcji \(f: X\to Y\) oznaczamy \(Y^X\), czyli \(Y^X=\{f:X\to Y\}\).
3. Zauważmy, że w powyższej definicji dziedziną relacji (funkcji) \(f\) jest cały zbiór \(X\). Często spotykamy się jednak z sytuacją, gdy dziedziną funkcji jest zbiór \(A\) istotnie zawarty w \(X\) (co zapisujemy \(A\subsetneq X\)). Przykładowo gdy mamy zadanie „wyznacz dziedzinę funkcji \(f : \mathbb {R}\to \mathbb {R}\), danej wzorem \(f(x)=\frac {\sqrt {x}}{x-3}\)”, formalnie powinniśmy najpierw tę dziedzinę wyznaczyć, bo \(f : \mathbb {R}\to \mathbb {R}\) zadane tym wzorem, nie jest funkcją w sensie Definicji 76. Dlatego albo wprowadzamy pojęcie funkcji częściowej, czyli prowadzącej z pewnego podzbioru \(X\), co zapisujemy tak: \(f: X\pto Y\), albo (częściej, zwłaszcza w analizie matematycznej) pomijamy ten problem, przyjmując, że zapis \(f: X\to Y\) oznacza również funkcję częściową.
4. O dwóch funkcjach \(f\subset X\times Y\) i \(g\subset X\times Y\) powiemy, że są równe, jeśli są równe jako relacje (czyli są takimi samymi podzbiorami \(X\times Y\)). W szczególności oznacza to, że dziedziny funkcji są takie same, ale też, że zbiór \(Y\) do którego funkcje prowadzą ma być ten sam. Na przykład, funkcja \(f(x)=x^2\) będzie inną funkcją jeśli rozważamy ją jako funkcję z \(X=\R \) do \(Y=\R \) a inną jeśli rozważamy ją jako funkcję z \(X=\R \) do \(Y=[0,+\infty )\).
Przypomnijmy, że przeciwdziedziną relacji (a zatem i funkcji \(f\)) jest zbiór \(\Dom _f^*=\{y\in Y :\exists _{x\in X} (x,y)\in f \}=\{y\in Y :\exists _{x\in X} y=f(x) \}\).
Przykład 78. Niech \(f\) będzie relacją w \(\mathbb {R}\times \mathbb {R}\). Łatwo sprawdzić, że:
1. Relacja zadana warunkiem \((x,y)\in f \iff y=x^2\) jest funkcją.
2. Relacja zadana warunkiem \((x,y)\in f \iff y^2=x\) nie jest funkcją.
3. Relacja zadana warunkiem \((x,y)\in f \iff x^2+y^2=1\) nie jest funkcją.
4. Relacja zadana warunkiem \((x,y)\in f \iff y=1\) jest funkcją.
5. Relacja zadana warunkiem \((x,y)\in f \iff x=1\) nie jest funkcją.
Rysunek 5.1 ilustruje te relacje.
Rysunek 5.1:
Przykład 79. Niech teraz \(X=\mathbb {N}\) a \(Y\) niech będzie dowolnym zbiorem. Funkcję \(f: \mathbb {N}\to Y\) nazywamy ciągiem o wartościach w \(Y\). Większości znane są już zapewne ciągi o wyrazach rzeczywistych, czyli funkcje \(f: \mathbb {N}\to \mathbb {R}\). Dla ciągów stosuje się specjalne oznaczenia, zapisując te funkcje małymi literami \(a,b,\dots \) i pisząc \(a_n\) zamiast \(a(n)\).
Funkcje możemy też zadać graficznie, tak jak na Rysunku 5.2. Strzałka od elementu zbioru \(X\) do elementu zbioru \(Y\) pokazuje, że te elementy są w relacji. Relacja na rysunku po lewej jest funkcją, a na rysunkach w środku i po prawej nie jest funkcją. Relacja na rysunku w środku nie spełnia warunku 1 z Definicji 76, jest natomiast funkcją częściową, relacja na rysunku po prawej nie spełnia warunku 2. tej definicji.
Rysunek 5.2:
Jeszcze jeden sposób definiowania funkcji (ogólniej, relacji) to tabelka relacji. Stosuje się go jeśli elementów zbiorów \(X\) i \(Y\) jest niezbyt dużo. Wówczas pionowo wypisujemy elementy zbioru \(X\), poziomo elementy zbioru \(Y\) a kropka w tabelce oznacza, że dane dwa elementy są w relacji.
Zobaczmy następujący przykład.
Przykład 80. Niech \(X=\{a,b,c\}, \ Y=\{1,2,3,4\} \).
| 1 | 2 | 3 | 4 | |
| \(a\) | \(\bullet \) | |||
| \(b\) | \(\bullet \) | |||
| \(c\) | \(\bullet \) | |||
Która z relacji z rysunku 5.2 jest zadana przez tę tabelkę?
W szczególnym przypadku, gdy mamy funkcję \(f:X\to Y\) i zbiór \(X\) jest iloczynem kartezjańskim \(s\) zbiorów \(X=X_1\times \dots \times X_s\), to piszemy
\[f: X_1\times \dots \times X_s\to Y\]
i \(f\) nazywamy funkcją \(s\) zmiennych.
Najczęściej zapisujemy \(f(x_1,\dots , x_s)\) zamiast (jak formalnie powinniśmy) \(f((x_1,\dots , x_s))\).
Przykład 81. Weźmy \(f:\mathbb {R}^2\to \mathbb {R}\). Przykładowa funkcja dwóch zmiennych
(o wartościach w \(Y=\mathbb {R}\)) to \(f(x_1,x_2)=x_1x_2\).
Inny, dość ważny przykład to projekcja: funkcję z \(\R ^n\) w \(\R \), która jest dana wzorem
\[f(x_1,x_2,\dots ,x_n)=x_i\]
nazywamy projekcją (rzutowaniem) na \(i\)-tą zmienną, \(i=1,\dots ,n\).
Weźmy teraz \(f:\mathbb {R}^2\to \mathbb {R}^3\). Przykładowa funkcja dwóch zmiennych o wartościach w \(Y=\mathbb {R}^3\) to \(f(x_1,x_2)=(x_1^2,x_1+x_2,\cos x_2 )\).
Zajmiemy się teraz złożeniem funkcji, zwanym inaczej superpozycją funkcji.
Definicja 82. Niech \(X,Y,Z,V\) będą zbiorami, i niech \(Y\subset V\). Niech dane będą dwie funkcje \(f: X\to Y\) i \(g: V\to Z\). Te dwie funkcje są relacjami, zatem złożenie funkcji \(f\) i \(g\) to złożenie relacji oznaczane przez \(g\circ f\). Przypomnijmy, że \(g\circ f \subset X\times Z,\) oraz \((x,z)\in g\circ f\iff \exists _{y\in Y}: (x,y)\in f\wedge (y,z)\in g \).
Pozostaje pytanie, czy złożenie funkcji jest także funkcją. Twierdzącą odpowiedź na to pytanie podaje poniższe stwierdzenie.
Stwierdzenie 83. Załóżmy, że mamy taką sytuację jak w Definicji 82. Wówczas złożenie funkcji \(f\) i \(g\), czyli \(g\circ f\) jest funkcją.
Dowód. Sprawdźmy pierwszy warunek Definicji 76. Pytamy, czy dla każdego \(x\in X\) istnieje \(z\in Z\), takie, że para \((x,z)\in
g\circ f\). Weźmy zatem dowolne \(x\in X\). Ponieważ \(f\) jest funkcją, istnieje \(y\in Y\) takie, że \((x,y)\in f\). Weźmy teraz to właśnie \(y\). Ponieważ \(g\) jest funkcją, istnieje \(z\in Z\) takie,
że \((y,z)\in g\). Skoro \((x,y)\in f\) i \((y,z)\in g\) to \((x,z)\in g\circ f\), a zatem pierwszy warunek jest spełniony.
Sprawdźmy drugi warunek Definicji 76. Niech \(z_1\) i \(z_2\) będą takie, że \((x,z_1)\in g\circ f\) i \((x,z_2)\in g\circ f\). Z definicji złożenia mamy
\[\exists _{y_1\in Y} : (x,y_1)\in f\wedge (y_1,z_1)\in g\]
oraz
\[\exists _{y_2\in Y} : (x,y_2)\in f\wedge (y_2,z_2)\in g.\]
Skoro \(f\) jest funkcją, i z powyższego \((x,y_1)\in f\) i \((x,y_2)\in f\), to \(y_1=y_2\). W takim razie mamy \((y_1,z_1)\in g\) i \((y_1,z_2)\in g\). Ponieważ \(g\) jest funkcją, dostajemy \(z_1=z_2\). Zatem drugi warunek definicji funkcji też jest spełniony. □
Skoro \(g\circ f\) jest funkcją, to możemy napisać, że \((g\circ f)(x)=z\iff \exists _{y\in Y}: f(x)=y \wedge g(y)=z\).
Zdefiniujemy teraz pewne szczególne rodzaje funkcji. Niech dane będą dwa zbiory \(X, Y\) i funkcja \(f: X\to Y\).
Definicja 84 (Injekcja). Funkcja \(f: X\to Y\) jest injekcją wtedy i tylko wtedy, gdy zachodzi następujący warunek:
\[\forall _{x_1,x_2\in X} : f(x_1)=f(x_2)\lra x_1=x_2.\]
Równoważnie (prawo kontrapozycji) możemy warunek sformułować jako:
\[\forall _{x_1,x_2\in X} : x_1\neq x_2\lra f(x_1)\neq f(x_2).\]
Injekcje znane są też pod nazwą funkcje różnowartościowe a surjekcje nazywa się czasami funkcjami na. Stosowana jest też pisownia iniekcja.
1. Weźmy \(f: \mathbb {N}\to \mathbb {N}\) daną wzorem \(f(n)=3n\). Łatwo sprawdzić, że ta funkcja jest injekcją (faktycznie, \(f(n_1)=f(n_2)\iff 3n_1=3n_2\lra n_1=n_2\)), natomiast nie jest surjekcją (bo, biorąc na przykład \(y=1\), widzimy, że nie istnieje \(n\in \N \), dla którego \(3n=1\)).
2. Niech funkcja \(f: \mathbb {Q}\to \mathbb {Q}\) będzie dana wzorem \(f(x)=x^3\). Funkcja ta jest injekcją, bo \(x_1^3=x_2^3\iff x_1^3-x_2^3=0\iff (x_1-x_2)(x_1^2+x_1x_2+x_2^3)=0\). Wyrażenie w drugim nawiasie
(niepełny kwadrat dwumianu) jest zerem tylko wtedy, gdy \(x_1=x_2=0\). Jeśli \(x_1\) lub \(x_2\) są różne od zera, to zerem musi być wyrażenie w pierwszym nawiasie, zatem \(x_1=x_2\).
Funkcja ta nie jest surjekcją, bo, przykładowo, dla \(y=2\) nie istnieje \(x\in \mathbb {Q}\), takie, że \(x^3=2\).
3. Niech \(f: \mathbb {Q}\to \mathbb {Q}\) będzie dana wzorem \(f(x)=x^2\). Funkcja ta nie jest ani injekcją, ani surjekcją. Sprawdzenie tego faktu zostawiamy jako proste ćwiczenie.
4. Niech \(f: \mathbb {R}\to \mathbb {R}\) będzie dana jako \(f(x)=x^3\). Funkcja ta jest zarówno injekcją jak i surjekcją. Sprawdzenie tego faktu zostawiamy jako proste ćwiczenie (dowód injektywności przebiega tak, jak w punkcie 2.)
Funkcja z punktu 4. Przykładu 86 jest bijekcją.
Uwaga 88. Chcąc zaznaczyć, że funkcja \(f\) między zbiorami \(X\) i \(Y\) jest bijekcją, będziemy używać oznaczenia \(X\bij Y\). Stosuje się też oznaczenia \(X \twoheadrightarrow \) dla surjekcji i \(X \hookrightarrow Y\) dla injekcji.
Przypomnijmy teraz, że relację odwrotną do relacji \(R\) oznaczamy \(R^{-1}\) i definiujemy poprzez warunek \((y,x)\in R^{-1} \iff (x,y)\in R\). W przypadku gdy \(f\) jest funkcją, relację odwrotną oznaczamy przez \(f^{-1}\).
Uwaga 89. Relacja odwrotna do funkcji nie musi być funkcją. Weźmy przykładowo \(f:\mathbb {R}\to \mathbb {R}\) daną jako \(f(x)=x^2\). Zatem \(f^{-1}=\{(y,x): (x,y)\in f \}=\{(x^2,x), x\in \mathbb {R} \}\), porównaj Przykład 61. Skoro tak, to w szczególności \((1,1)\in f^{-1}\) oraz \((1,-1)\in f^{-1}\), co oznacza, że \(f^{-1}\) nie jest funkcją.
Następujące twierdzenie odpowiada na pytanie kiedy relacja odwrotna do funkcji jest funkcją.
Dowód. (\(\lra \)). Zakładamy, że \(f^{-1}\) jest funkcją. Chcemy sprawdzić, czy \(f\) jest bijekcją.
1. Najpierw sprawdzamy, czy \(f\) jest injekcją. Dla dowodu nie wprost, przypuśćmy, że \(f\) nie jest injekcją. Wtedy istnieją \(x_1,x_2\in X\), \(x_1\neq x_2\), takie, że \((x_1,y)\in f\) i \((x_2,y)\in f\). Stąd, i z definicji \(f^{-1}\) mamy \((y,x_1)\in f\) i \((y, x_2)\in f\), czyli \(f^{-1}\) nie jest funkcją. Zatem \(f\) musi być injekcją.
2. Przypuśćmy teraz, że \(f\) nie jest surjekcją. Wówczas istnieje \(y\in Y\), taki, że dla każdego \(x\in X\) para \((x,y)\notin f\). To oznacza, że dla każdego \(x\in X\) para \((y,x)\notin f^{-1}\). To oznacza, że \(f^{-1}\) nie spełnia warunku 1. z definicji funkcji, czyli otrzymaliśmy sprzeczność.
(\(\Longleftarrow \)) Wykażemy, że jeśli \(f\) jest bijekcją, to \(f^{-1}\) jest funkcją.
1. Jeśli \(f\) jest surjekcją to dla każdego \(y\in Y\) istnieje \(x\in X\) takie, że \((x,y)\in f\). Stąd dla każdego \(y\in Y\) istnieje \(x\in X\) takie, że \((y,x)\in f^{-1}\), zatem \(f^{-1}\) spełnia warunek 1. Definicji 76.
2. Jeśli \(f\) jest injekcją to mamy następującą implikację \(((x_1,y)\in f\wedge (x_2,y)\in f)\lra x_1=x_2\) co jest równoważne implikacji \(((y,x_1)\in f^{-1}\wedge (y,x_2)\in f^{-1})\lra x_1=x_2\) a to oznacza, że \(f\) spełnia 2. z Definicji 76. □
Kolejne stwierdzenie mówi, że jeśli \(f\) jest bijekcją (wtedy \(f^{-1}\) jest funkcją), to funkcja \(f^{-1}\) jest też bijekcją.
Dowód.
1. Sprawdzamy, czy \(f^{-1}\) jest injekcją. Niech \((y_1,x)\in f\) i \((y_2,x)\in f^{-1}\). Wówczas \((x,y_1)\in f\) i \((x,y_2)\in f\). Skoro \(f\) jest funkcją, to musi być \(y_1=y_2\), zatem \(f^{-1}\) jest injekcją.
2. Sprawdzamy, czy funkcja \(f^{-1}\) jest surjekcją, to znaczy chcemy wiedzieć, czy dla dowolnego \(x\in X\) istnieje \(y\in Y\) takie, że \((y,x)\in f^{-1}\). Weźmy zatem dowolne \(x\in X\). Skoro \(f\) jest funkcją to istnieje \(y\in Y\) takie, że \((x,y)\in f\) (warunek 1. Definicji 76), skąd \((y,x)\in f^{-1}\). □
Niech teraz \(Z\) będzie zbiorem. Zdefiniujemy funkcję identycznościową na zbiorze \(Z\).
Definicja 92. Niech \(\textrm {Id}_Z: Z\to Z\) będzie funkcją taką, że \(\textrm {Id}_Z(z)=Z\) dla każdego \(z\in Z\). \(\textrm {Id}_Z\) nazywamy funkcją identycznościową (albo identycznością) na zbiorze \(Z\).
Zachodzi następujące stwierdzenie,
Stwierdzenie 93. Niech \(f:X\bij Y\) będzie bijekcją. Wówczas:
\[ f^{-1}\circ f=\textrm {Id}_X \text { oraz } f\circ f^{-1}=\textrm {Id}_Y.\]
Dowód.
1. Złożenie \(f^{-1}\circ f\) przeprowadza zbiór \(X\) w zbiór \(X\), zatem dla dowolnego \(x_1\in X\) istnieje \(x_2\in X\) spełniające \((f^{-1}\circ f)(x_1)=x_2\). Jeśli wykażemy teraz, że \(x_1=x_2\) to wykażemy \(f^{-1}\circ f=\textrm {Id}_X\). Z definicji złożenia, \((x_1,x_2)\in f^{-1}\circ f \iff \exists _{y\in Y} : (x_1,y)\in f \wedge (y,x_2)\in f^{-1}\). Skoro \((x_1,y)\in f\) to \((y,x_1)\in f^{-1}\), mamy zatem \((y,x_2)\in f^{-1}\) i \((y,x_1)\in f^{-1}\). Wiemy, ze Stwierdzenia 91, że \(f^{-1}\) jest bijekcją, zatem \(x_1=x_2\), czyli dla dowolnego \(x_1\in X\) zachodzi \((f^{-1}\circ f)(x_1)=x_1\).
2. Rozumowanie jest analogicznie jak to w punkcie 1. Złożenie \(f\circ f^{-1}\) przeprowadza zbiór \(Y\) w zbiór \(Y\), zatem dla dowolnego \(y_1\in Y\) mamy \((f\circ f^{-1})(y_1)=y_2\), dla pewnego \(y_2\in Y\). Jeśli wykażemy, że \(y_1=y_2\) to wykażemy \(f\circ f^{-1}=\textrm {Id}_Y\). Z definicji złożenia, \((y_1,y_2)\in f\circ f^{-1}\iff \exists _{x\in X}: (y_1,x)\in f^{-1}\wedge (x,y_2)\in f\iff (y_1,x)\in f^{-1}\wedge (y_2,x)\in f^{-1}\). Skoro \(f^{-1}\) jest funkcją (Twierdzenie 90) to \(y_1=y_2\). Zatem \((f\circ f^{-1})(y_1)=y_1\) dla dowolnego \(y_1\), czyli \(f\circ f^{-1}=\textrm {Id}_Y.\) □
Na zakończenie tego wykładu wypiszemy dwa ćwiczenia, które warto zrobić samodzielnie.
Ćwiczenie 94. Weźmy dwie funkcje \(f :X\to Y\) i \(g:Y\to Z\) oraz ich złożenie \(g\circ f:X\to Z\).
1. Wykazać, że jeśli \(f\) i \(g\) są surjekcjami to \(g\circ f\) też.
2. Wykazać, że jeśli \(f\) i \(g\) są injekcjami to \(g\circ f\) też.
3. Jeśli \(g\circ f\) jest injekcją i \(f\) jest injekcją to co można powiedzieć o injektywności \(g\)?
4. Jeśli \(f\) jest injekcją a \(g\) surjekcją (lub na odwrót) to co można powiedzieć o \(g\circ f\)?
Ćwiczenie 95. Weźmy dwie bijekcje \(f :X\to Y\) i \(g:Y\to Z\) oraz ich złożenie \(g\circ f:X\to Z\). Wiemy, że \(g\circ f\) też jest bijekcją. Wykazać, że zachodzi następujący wzór na odwrotność złożenia funkcji:
\[(g\circ f)^{-1}=f^{-1}\circ g^{-1}.\]