Relacje równoważności, funkcje

Kolejnym ważnym rodzajem relacji są tak zwane relacje równoważności. Związana z nimi zasada abstrakcji jest ważną metodą tworzenia nowych pojęć w matematyce. Najpierw wprowadzimy pojęcie partycji (podziału) zbioru $X$.

Partycją (podziałem) zbioru $X$ nazywamy każdą rodzinę niepustych, parami rozłącznych podzbiorów zbioru $X$, pokrywających w sumie cały zbiór $X$^9.1. Innymi słowy, zbiór ${\cal A}\subseteq {\cal P}(X)$ nazywamy partycją zbioru $X$, gdy:
(a) każdy zbiór $U\in{\cal A}$ jest niepusty, tzn. $(\forall U\in{\cal A})U\neq\emptyset$,
(b) różne zbiory $U,V\in{\cal A}$ są rozłączne, tzn. $(\forall U,V\in{\cal A})(U\neq V\Rightarrow U\cap V=\emptyset)$ oraz
(c) każdy element $x\in X$ należy do jakiegoś $U\in{\cal A}$, tzn.
$(\forall x\in X)(\exists U\in{\cal A})x\in U$.

Z każdą partycją ${\cal A}$ zbioru $X$ wiążemy pewną relację $R_{{\cal A}}$ na zbiorze $X$ określoną następująco:

$$xR_{{\cal A}}y\iff x\mbox{ i }y\mbox{ należą do tego samego zbioru partycji }{\cal A}.$$

Zwróćmy uwagę, że relacja $R_{{\cal A}}$ jest zwrotna, symetryczna i przechodnia.

Przykład 0. Niech $X=\{\mbox{Ala, Ewa, Kasia, Ula, Jaś, Piotr}\}$. Podział zbioru $X$ na zbiory $\{\mbox{Ala, Ewa}\},\{\mbox{Jaś, Kasia,Ula}\}$ i $\{\mbox{Piotr}\}$ to przykład partycji ${\cal A}=\{\{\mbox{Ala, Ewa}\},\{\mbox{Jaś, Kasia,Ula}\},\{\mbox{Piotr}\}\}$. Partycja ta ma trzy elementy. W szczególności, $\{\mbox{Ala, Ewa}\}\in{\cal A}$ oraz $\{\mbox{Piotr}\}\in{\cal A}$, jednak $\mbox{Piotr}\not\in{\cal A}$. W tym przykładzie możemy łatwo wypisać wszystkie elementy relacji $R_{{\cal A}}$:

$$R_{{\cal A}}=\{\langle \mbox{Ala,Ala}\rangle,\langle\mbox{Ala... ...le\mbox{Ewa, Ala}\rangle,\langle\mbox{Ewa,Ewa}\rangle,\dots\}.$$

Jako ćwiczenie pozostawiamy czytelnikowi sprawdzenie, ile jest różnych partycji zbioru $X$ w tym przykładzie. Szczególną partycją jest partycja zbioru $X$ składająca się z jednego zbioru, mianowicie samego zbioru $X$.

Przykład 1. Niech $X=\mathbb{R}^2$. Dla $a\in\mathbb{R}$ niech $X_a=\{\langle a,y\rangle\in\mathbb{R}^2:y\in\mathbb{R}\}$. Zatem ${\cal A}=\{X_a:a\in\mathbb{R}\}$ jest partycją płaszczyzny $\mathbb{R}^2$ na proste równoległe do osi $OY$. Relacja $R_{{\cal A}}$ na zbiorze $X=\mathbb{R}^2$ odpowiadająca tej partycji ma tu proste określenie: dla $\langle x,y\rangle,\langle u,v\rangle\in\mathbb{R}^2$ mamy

$$\langle x,y\rangle R_{{\cal A}}\langle u,v\rangle\iff x=u.$$

Przykład 2. Załóżmy, że $X$ oznacza zbiór ludzi. Możemy próbować klasyfikować ludzi według pewnej cechy, na przykład według wzrostu wyrażonego w centymetrach (w zaokrągleniu do najbliższej liczby calkowitej). Dla $n\in\mathbb{N}$ niech

$$X_n=\{u\in X:u\mbox{ ma wzrost }n\mbox{ cm }\}.$$

Wówczas ${\cal A}=\{X_n:n\in\mathbb{N}$ i $X_n\neq\emptyset\}$ jest partycją zbioru ludzi składającą się ze zbiorów ludzi tego samego wzrostu. Relację $R_{{\cal A}}$ na zbiorze $X$ możemy tu określić następująco:

$$xR_{{\cal A}}y\Leftrightarrow x\mbox{ i }y\mbox{ są tego samego wzrostu}.$$

Relacja ta, jak łatwo sprawdzić, jest zwrotna, symetryczna i przechodnia.

Z drugiej strony zbiór $X$ rozpada się tu na rozłączne podzbiory złożone z ludzi tego samego wzrostu: elementy partycji ${\cal A}$. W każdym z takich podzbiorów każde dwie osoby są względem siebie w relacji $R_{{\cal A}}$, osoby z różnych grup nie są względem siebie w relacji.

Okazuje się, że ta własność relacji $R_A$ jest wspólna dla wszystkich relacji, które są zwrotne, symetryczne i przechodnie. Wracając do naszego przykładu, osoby w tej samej grupie z punktu widzenia rozważanej cechy (wzrost) są od siebie nieodróżnialne, inaczej mówiąc: równoważne. To uzasadnia poniższą definicję.

Definicja 9..1   Relacja $R$ na zbiorze $X$ nazywa się relacją równoważności, gdy jest zwrotna, symetryczna i przechodnia.

Widzimy więc, że każda z relacji $R_{{\cal A}}$ wyznaczonych przez partycje zbioru $X$ jest relacją równoważności. Podamy teraz kilka dalszych przykładów relacji równoważności.

Przykład 3. Relacja równości $=$ na zbiorze $X$.

Przykład 4. Relacja równoległości $l_1\parallel l_2$ na zbiorze prostych na płaszczyźnie.

Przykład 5. Relacja $n\sim m\Leftrightarrow 3\mid(n-m)$ na zbiorze liczb całkowitych.

Przykład 6. Relacja `` $xRy\Leftrightarrow x$ i $y$ mają tych samych rodziców'' na zbiorze ludzi.

Przykład 7. Niech $v\in{\mathbb{R}}^2,v\neq 0$. Relacja $\sim$ na ${\bf R}^2$ określona przez

$$x\sim y\Leftrightarrow(\exists r\in{\mathbb{R}})(x-y=rv).$$

Zwróćmy uwagę, że gdy $v$ jest wektorem jednotkowym na osi $OY$, relacja $\sim$ pokrywa się z relacją $R_{{\cal A}}$ z przykładu 1.

Relacje równoważności często oznaczamy symbolami podobnymi do $=$, takimi jak na przykład $\equiv,\sim,\approx$. Załóżmy teraz, że $\sim$ jest relacją równoważności na zbiorze $X$. Elementy $a,b\in X$ takie, że $a\sim b$ nazywamy równoważnymi (w sensie relacji $\sim$). Na mocy symetryczności znaczy to również, że $b\sim a$. Dla dowolnego $a\in X$ definiujemy zbiór

$$[a]_{\sim}=\{b\in X:a\sim b\},$$

innymi słowy, $[a]_{\sim}$ to zbiór wszystkich elementów zbioru $X$ równoważnych $a$ (w szczególności $a\in [a]_{\sim}$). Zbiór ten nazywamy klasą abstrakcji (lub klasą równoważności) elementu $a$ (względem relacji $\sim$). Zbiory $[a]_{\sim}$ dla $a\in X$ nazywamy klasami abstrakcji (lub równoważności) relacji $\sim$.

Klasy abstrakcji relacji $R_{{\cal A}}$ na zbiorze $X$ to po prostu zbiory-elementy partycji ${\cal A}$. Okazuje się, że klasy abstrakcji dowolnej relacji równoważności tworzą partycję.

Uwaga 9..2   Załóżmy, że $\sim$ jest relacją równoważności na zbiorze $X$. Wtedy ${\cal A}=\{[a]_{\sim}:a\in X\}$ jest partycją zbioru $X$ (zwaną podziałem zbioru $X$ na klasy abstrakcji relacji $\sim$). Ponadto, $\sim=R_{{\cal A}}$.

Dowód. 1. Zbiory z ${\cal A}$ są niepuste i pokrywają $X$, bo dla $a\in X$ mamy $a\sim a$, czyli $a\in [a]_{\sim}$.

2. Jeśli $a\sim b$, to $[a]_{\sim}=[b]_{\sim}$. By tego dowieść najpierw pokażemy, że $[a]_{\sim}\subseteq[b]_{\sim}$. W tym celu załóżmy, że $c\in[a]_{\sim}$, tzn. $c\sim a$. Wtedy z $a\sim b$ i przechodniości dostajemy $c\sim b$, czyli $c\in[b]_{\sim}$. Podobnie pokazujemy, że $[b]_{\sim}\subseteq[a]_{\sim}$.

3. Jeśli $a\not\sim b$ (tzn. $\neg a\sim b$), to $[a]_{\sim}\cap[b]_{\sim}=\emptyset$. Tu prowadzimy dowód nie wprost. Przypuśćmy, że pewne $c\in[a]_{\sim}\cap[b]_{\sim}$. Wtedy (na mocy definicji klasy abstrakcji i symetryczności $\sim$): $a\sim c$ i $c\sim b$, więc z przechodniości $a\sim b$, sprzeczność.

Stąd dostajemy, że różne zbiory należące do ${\cal A}$ są parami rozłączne, tzn. jeśli $[a]_{\sim}\neq[b]_{\sim}$, to $[a]_{\sim}\cap[b]_{\sim}=\emptyset$. Istotnie, rozumujemy tu nie wprost. Przypuśćmy, że $[a]_{\sim}\cap[b]_{\sim}\neq\emptyset$. Na mocy 3. i prawa transpozycji dostajemy stąd $a\sim b$, czyli (na mocy 2.) $[a]_{\sim}=[b]_{\sim}$. $\Box$

Wniosek 9..3   Dla $a,b\in X$, $a\sim b\iff[a]_{\sim}=[b]_{\sim}$.

Wniosek 9..4   Jeśli relacje równoważności $\sim_1$ i $\sim_2$ na zbiorze $X$ mają te same klasy abstrakcji, to $\sim_1=\sim_2$.

Zasada abstrakcji. W przykładzie 2. podział zbioru ludzi na klasy abstrakcji odbywał się według znanej cechy: wzrostu. Załóżmy, że $\sim$ jest relacją równoważności na zbiorze $X$. Możemy traktować klasę abstrakcji elementu $a\in X$ jako nowy obiekt, swoistą cechę elementu $a$ wspólną dla wszystkich elementów w tej samej klasie abstrakcji (w przykładzie 0. tą cechą był wzrost). Zasada abstrakcji polega własnie na definiowaniu w ten sposób nowych pojęć, nowych własności różnych obiektów.

W ten sposób definiuje się na przykład kierunek prostej $l$ na płaszczyźnie: jest to klasa abstrakcji prostej $l$ względem relacji równoległości prostych z przykładu 4, czyli wspólna cecha klasy prostych równoległych. Opis klas abstrakcji relacji z pozostałych przykładów pozostawiamy jako ćwiczenie.

Rodzina klas abstrakcji wyznacza relację równoważności, podobnie jak tabelka wartości logicznych wyznacza spójnik logiczny. W rachunku zdań określaliśmy wręcz nowe abstrakcyjne spójniki logiczne zadając dowolnie ich tabelki wartości. Teraz sytuacja jest podobna: wychodząc od dowolnego podziału ${\cal A}$ zbioru $X$ na zbiory rozłączne i niepuste dostajemy relację równoważności $R_{{\cal A}}$, której klasami abstrakcji są dokładnie te zbiory.

Funkcje. Jeśli każdemu elementowi $x$ zbioru $X$ przypisany jest jeden element $y$ zbioru $Y$ (niekoniecznie ten sam dla różnych elementów $x$), to mówimy, że na zbiorze $X$ określona jest funkcja (inaczej: przekształcenie lub odwzorowanie) przekształcająca zbiór $X$ w zbiór $Y$, zaś $y$ jest wartością tej funkcji dla argumentu $x$. Oznaczając taką funkcję przez $f$, piszemy wtedy

$$f:X\to Y\mbox{\ \ i\ \ } f(x)=y.$$

Funkcje oznaczamy często literami $f,g,h$.

Innymi słowy, funkcja $f:X\to Y$ jest to dowolna relacja $f$ między elementami zbioru $X$ a elementami zbioru $Y$, której dziedzina to cały zbiór $X$, taka że dla każdego $x\in X$ istnieje dokładnie jeden $y\in Y$ taki, że $f(x)=y$. Z tego względu, gdy zbiory $X$ i $Y$ są skończone, możemy przedstawić funkcję $f$ w postaci diagramu. Strzałka od $x$ do $y$ oznacza, że $f(x)=y$.

Definicja 9..5   Załóżmy, że $f:X\to Y$.
(1) Zbiór $X$ nazywamy dziedziną funkcji $f$. Dziedzinę funkcji $f$ oznaczamy też przez $Dom(f)$.
(2) Zbiór $Rng(f)=\{y\in Y:(\exists x\in X)f(x)=y\}$ nazywamy obrazem lub zbiorem wartości funkcji $f$.
(3) Zbiór $\{\langle x,y\rangle\in X\times Y:f(x)=y\}$ nazywamy wykresem funkcji $f$.

Uwaga 9..6   Wprost z definicji wynika, że dwie funkcje $f$ i $g$ na zbiorze $X$ są równe dokładnie wtedy, gdy mają te same wartości dla wszystkich argumentów. Formalnie:

$$f=g\Leftrightarrow(\forall x\in X)(f(x)=g(x)).$$

Przykład 0. Funkcja zdaniowa $\varphi(x),x\in X$, to funkcja przypisująca elementom $x$ zbioru $X$ zdania $\varphi(x)$.

Przykład 1. Funkcja pusta $\emptyset:\emptyset\to Y$, dziedziną i obrazem tej funkcji jest również zbiór pusty.

Przykład 2. Dla dowolnego zbioru $X$ funkcja identycznościowa $id_X:X\to X$ dana jest wzorem $id_X(x)=x$. Funkcja stała to funkcja, która dla wszystkich argumentów przyjmuje tę samą stałą wartość.

Przykład 3. Niech $X=\{$krzesło, stół, ławka$\},\ Y=\{$bratek, stokrotka$\}$. By określić funkcję $f:X\rightarrow Y$ wystarczy wypisać jej wartości dla wszystkich argumentów. Zamiast tego można też narysować jej diagram. Przykładowo możemy określić $f$ przez zdefiniowanie:

$f($krzesło$)=$ bratek, $f($stół$)=$ stokrotka i $f($ławka$)=$ bratek.

Diagram tak określonej funkcji $f$ wygląda następująco:

Jest 8 różnych funkcji $f:X\rightarrow Y$. Istotnie, skoro zbiór $Y$ ma dwa elementy, dla każdego $x\in X$ wartość $f(x)$ możemy wybrać na dwa sposoby. Zbiór $X$ ma trzy elementy, razem więc funkcję $f$ można określić na $2\times 2\times 2=8$ sposobów.

Przykład 4. Funkcje $\pi_X:X\times Y\to X$ i $\pi_Y:X\times Y\to Y$ określone wzorami

$$\pi_X(\langle x,y\rangle)=x\mbox{\ \ \ i\ \ \ }\pi_Y(\langle x,y\rangle)=y$$

nazywamy rzutami na pierwszą i drugą oś odpowiednio.

Z każdą funkcją $f:X\to Y$ związana jest pewna relacja $R_f$ na zbiorze $X$ określona wzorem

$$x_1R_fx_2\Leftrightarrow f(x_1)=f(x_2).$$

Łatwo sprawdzić, że $R_f$ jest relacją równoważności. W przypadku, gdy $f=\pi_X:X\times Y\to X$, klasy abstrakcji relacji $R_f$ to zbiory par $\langle x,y\rangle$ o tej samej pierwszej współrzędnej.

Definicja 9..7   Niech $f:X\to Y$.
(1) $f$ jest różnowartościowa (inaczej: 1-1, wzajemnie jednoznaczna, jest injekcją), gdy dla różnych argumentów ma różne wartości, tzn.

$$(\forall x_1,x_2\in X)(x_1\neq x_2\Rightarrow f(x_1)\neq f(x_2)).$$

Przez transpozycję warunek ten możemy równoważnie zapisać w postaci

$$(\forall x_1,x_2\in X)(f(x_1)= f(x_2)\Rightarrow x_1=x_2).$$

Piszemy wówczas $f:X\stackrel{1-1}{\to}Y$.

(2) $f$ jest ``na'' (inaczej: jest surjekcją), gdy cały zbiór $Y$ jest zbiorem wartości $f$. Symbolicznie:

$$(\forall y\in Y)(\exists x\in X)f(x)=y.$$

Piszemy wówczas $f:X\stackrel{\mbox{\scriptsize \lq\lq na''}}{\to}Y$.
(3) $f$ jest bijekcją, gdy jest 1-1 i ``na'', tzn. jest zarówno injekcją, jak i surjekcją. Piszemy wówczas $f:X\stackrel{1-1,\mbox{\scriptsize \lq\lq na''}}{\longrightarrow}Y$.

Czytelnik powinien stwierdzić, jak przy pomocy diagramu funkcji $f:X\to Y$ (gdy zbiory $X,Y$ są skończone) rozpoznać, czy funkcja jest bijekcją, injekcją czy surjekcją.

Uwaga 9..8   Jeśli $f:X\to Y$ jest różnowartościowa, to $f:X\to Rng(f)$ jest bijekcją.

Dowód. Z założenia, $f$, traktowana jak funkcja przekształcająca zbiór $X$ w $Rng(f)$, jest $1-1$. Z określenia zbioru $Rng(f)$ mamy, że jest również ``na''. $\Box$

Przykład 1. $X=[0,\pi],\ Y=[0,1]\subseteq {\mathbb{R}},\ f:X\to Y$ dana jest wzorem $f(x)=\sin(x)$. Wówczas $f$ jest ``na'', jednak nie jest 1-1, bo np. $f(0)=f(\pi)=0$.

Przykład 2. $X=[0,2\pi]\times [0,\infty),\ f:X\to{\mathbb{R}}^2$ określona jest wzorem

$$\mbox{dla }\langle\varphi,\rho\rangle\in X,\ f(\langle\varphi... ...&=&\rho\cos{\varphi}\\ y&=&\rho\sin{\varphi}\end{array}\right.$$

Zatem

$$x^2+y^2=\rho^2(\cos^2{\varphi}+\sin^2{\varphi})=\rho^2.$$

Przy ustalonym $\rho$, dla $\varphi\in[0,2\pi]$ wartości funkcji $f$ przebiegają więc okrąg o środku $(0,0)$ i promieniu $\rho$. $f$ jest więc ``na'', ale nie jest 1-1.

Definicja 9..9   Załóżmy, że $f:X\to Y$ jest bijekcją. Wtedy każdemu $y\in Y$ przypisane jest jedyne $x\in X$ takie, że $y=f(x)$. W ten sposób określona jest funkcja $f^{-1}:Y\to X$, która spełnia dla wszystkich $x\in X,y\in Y$ zdanie

$$f(x)=y\Leftrightarrow x=f^{-1}(y).$$

Funkcję $f^{-1}$ nazywamy funkcją odwrotną do $f$.

Uwaga 9..10   $f^{-1}:Y\to X$ jest również bijekcją oraz $f$ jest funkcją odwrotną do $f^{-1}$ (tzn. $(f^{-1})^{-1}=f$).

Dowód. (1) $f^{-1}$ jest 1-1: niech $y_1,y_2\in Y$. Wybierzmy $x_1,x_2\in X$ takie, że

$$(*)\ \ f(x_1)=y_1\mbox{\ \ i\ \ }f(x_2)=y_2.$$

Znaczy to, że $f^{-1}(y_1)=x_1$ i $f^{-1}(y_2)=x_2$. Zatem jeśli $f^{-1}(y_1)=f^{-1}(y_2)$, to $x_1=x_2$, więc w tym przypadku $y_1=y_2$ (na mocy $(*)$).

(2) $f^{-1}$ jest ``na''. Niech $x\in X$ oraz $y=f(x)$. Widzimy, że $y\in Y$ i $f^{-1}(y)=x$. Dlatego $x\in Rng(f^{-1})$, czyli $Rng(f^{-1})=X$.

(3) $f$ jest odwrotna do $f^{-1}$, gdyż mamy $f(x)=y\Leftrightarrow x=f^{-1}(y)$. $\Box$

Przykład. $f:{\mathbb{R}}\to{\mathbb{R}}$ dana jest wzorem $f(x)=3x+1$. Zatem jest to bijekcja. Wzór na funkcję odwrotną znajdujemy następująco. Mamy następujący ciąg równoważnych funkcji zdaniowych zmiennych $x,y\in\mathbb{R}$:

$$f(x)=y$$

$$\Updownarrow$$

$$3x+1=y$$

$$\Updownarrow$$

$$x={1\over 3}y-{1\over 3}$$

Dlatego funkcja $f^{-1}$ dana jest wzorem $f^{-1}(y)={1\over 3}y-{1\over 3}$, czy też równoważnie (po zamianie zmiennej $y$ w ostatnim wzorze na równie dobrą zmienną $x$) $f^{-1}(x)={1\over 3}x-{1\over 3}$.

Składanie funkcji. Załóżmy, że $f:X\to Y$ oraz $g:Y\to Z$. Wtedy definiujemy funkcję $g\circ f:X\to Z$ wzorem $(g\circ f)(x)=g[f(x)]$. Prawa strona tego wzoru ma sens, bo dla $x\in X,\ f(x)\in Y$ oraz $Y$ jest dziedziną $g$, więc $g[f(x)]$ istnieje. Funkcję $g\circ f$ nazywamy złożeniem (lub superpozycją) funkcji $f$ i $g$. Piszemy też $gf$ zamiast $g\circ f$.

Uwaga 9..11   Jeśli $f:X\to Y,\ g:Y\to Z,\ h: Z\to T$ to $h\circ(g\circ f)=(h\circ g)\circ f$.

Uwaga ta mówi o łączności składania funkcji. Z tego względu w wielokrotnych złożeniach funkcji wolno opuszczać nawiasy.
Dowód. Funkcje $h\circ(g\circ f)$ i $(h\circ g)\circ f$ mają wspólną dziedzinę: zbiór $X$. Są one równe dokładnie wtedy, gdy mają te same wartości dla wszystkich argumentów. Niech więc $x\in X$ będzie dowolnym argumentem.

Z definicji złożenia funkcji dostajemy

$$(h\circ(g\circ f))(x)=h[(g\circ f)(x)]=h[(g(f(x))]=(h\circ g)(f(x))=((h\circ g)\circ f)(x).$$

$\Box$

Dla $f:X\to X$ możemy wykonywać wielokrotną superpozycję $f$ z sobą. Dla $n>0$ przyjmujemy oznaczenia:

$$\underbrace{f\circ\dots\circ f}_n=f^n\mbox{\ \ i\ \ }\underbrace{f^{-1}\circ\dots\circ f^{-1}}_n=f^{-n},$$

o ile $f^{-1}$ w drugim wzorze istnieje. Przyjmujemy też $f^0=id_X$.

Obcinanie (ograniczanie) i rozszerzanie funkcji.

Załóżmy, że $f:X\to Y$ , $Y\subseteq Z$ oraz $X_0\subseteq X\subseteq X_1$.
(1) Definiujemy funkcję $f\vert _{X_0}:X_0\to Y$. Dla argumentów $x\in X_0$ wartości $f\vert _{X_0}$ są te same, co wartości $f$, tzn. $f\vert _{X_0}(x)=f(x)$. Funkcję tę nazywamy obcięciem (ograniczeniem) funkcji $f$ do zbioru $X_0$.
(2) Funkcję $f_1:X_1\to Z$ nazywamy rozszerzeniem funkcji $f\Leftrightarrow$ dla każdego $x\in X$ mamy $f_1(x)=f(x)$ (innymi słowy, gdy $f$ jest obcięciem funkcji $f_1$ do $X$).

Załóżmy teraz, że $f:X_1\times\dots\times X_n\to Y$. Wartość $y$ funkcji $f$ dla $\langle x_1\dots,x_n\rangle\in X_1\times\dots\times X_n$ zapisujemy w postaci $f(x_1,\dots,x_n)=y$. Funkcję $f$ nazywamy wtedy $n$-argumentową, zaś elementy $x_1\in X_1,\dots,x_n\in X_n$ nazywamy argumentami funkcji $f$.