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 

.

Partycją (podziałem) zbioru 

 nazywamy kaŜdą rodzinę niepustych, parami rozłącznych podzbiorów

zbioru 

, pokrywających w sumie cały zbiór 

. Innymi słowy, zbiór 

 nazywamy partycją

zbioru 

, gdy:

(a) kaŜdy zbiór 

 jest niepusty, tzn. 

,

(b) róŜne zbiory 

 są rozłączne, tzn. 

 oraz

(c) kaŜdy element 

 naleŜy do jakiegoś 

, tzn.

.

Z kaŜdą partycją 

 zbioru 

 wiąŜemy pewną relację 

 na zbiorze 

 określoną następująco:

Zwróćmy uwagę, Ŝe relacja 

 jest zwrotna, symetryczna i przechodnia.

Przykład 0. Niech 

. Podział zbioru 

 na zbiory

 i 

 to przykład partycji

. Partycja ta ma trzy elementy. W szczególności,

 oraz 

, jednak 

. W tym przykładzie moŜemy łatwo wypisać

wszystkie elementy relacji 

:

Jako ćwiczenie pozostawiamy czytelnikowi sprawdzenie, ile jest róŜnych partycji zbioru 

 w tym

przykładzie. Szczególną partycją jest partycja zbioru 

 składająca się z jednego zbioru, mianowicie

samego zbioru 

.

Przykład 1. Niech 

. Dla 

 niech 

. Zatem 

jest partycją płaszczyzny 

 na proste równoległe do osi 

. Relacja 

 na zbiorze 

odpowiadająca tej partycji ma tu proste określenie: dla 

 mamy

Przykład 2. ZałóŜmy, Ŝe 

 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 

 niech

Wówczas 

 i 

 jest partycją zbioru ludzi składającą się ze zbiorów ludzi tego

samego wzrostu. Relację 

 na zbiorze 

 moŜemy tu określić następująco:

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

Z drugiej strony zbiór 

 rozpada się tu na rozłączne podzbiory złoŜone z ludzi tego samego wzrostu:

elementy partycji 

. W kaŜdym z takich podzbiorów kaŜde dwie osoby są względem siebie w relacji 

,

osoby z róŜnych grup nie są względem siebie w relacji.

Okazuje się, Ŝe ta własność relacji 

 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 

 na zbiorze 

 nazywa się relacją równowaŜności, gdy jest zwrotna,

symetryczna i przechodnia.

Widzimy więc, Ŝe kaŜda z relacji 

 wyznaczonych przez partycje zbioru 

 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 

.

Przykład 4. Relacja równoległości 

 na zbiorze prostych na płaszczyźnie.

Przykład 5. Relacja 

 na zbiorze liczb całkowitych.

Przykład 6. Relacja `` 

 i   mają tych samych rodziców'' na zbiorze ludzi.

Przykład 7. Niech 

. Relacja 

 na 

 określona przez

Zwróćmy uwagę, Ŝe gdy   jest wektorem jednotkowym na osi 

, relacja 

 pokrywa się z relacją 

 z

przykładu 1.

Relacje równowaŜności często oznaczamy symbolami podobnymi do 

, takimi jak na przykład 

.

ZałóŜmy teraz, Ŝe 

 jest relacją równowaŜności na zbiorze 

. Elementy 

 takie, Ŝe 

nazywamy równowaŜnymi (w sensie relacji 

). Na mocy symetryczności znaczy to równieŜ, Ŝe 

.

Dla dowolnego 

 definiujemy zbiór

innymi słowy, 

 to zbiór wszystkich elementów zbioru 

 równowaŜnych   (w szczególności 

). Zbiór ten nazywamy klasą abstrakcji (lub klasą równowaŜności) elementu   (względem relacji 

).

Zbiory 

 dla 

 nazywamy klasami abstrakcji (lub równowaŜności) relacji 

.

Klasy abstrakcji relacji 

 na zbiorze 

 to po prostu zbiory-elementy partycji 

. Okazuje się, Ŝe klasy

abstrakcji dowolnej relacji równowaŜności tworzą partycję.

Uwaga 9..2   ZałóŜmy, Ŝe 

 jest relacją równowaŜności na zbiorze 

. Wtedy 

 jest

partycją zbioru 

 (zwaną podziałem zbioru 

 na klasy abstrakcji relacji 

). Ponadto, 

.

Dowód. 1. Zbiory z 

 są niepuste i pokrywają 

, bo dla 

 mamy 

, czyli 

.

2. Jeśli 

, to 

. By tego dowieść najpierw pokaŜemy, Ŝe 

. W tym celu załóŜmy,

Ŝe 

, tzn. 

. Wtedy z 

 i przechodniości dostajemy 

, czyli 

. Podobnie

pokazujemy, Ŝe 

.

3. Jeśli 

 (tzn. 

), to 

. Tu prowadzimy dowód nie wprost. Przypuśćmy, Ŝe

pewne 

. Wtedy (na mocy definicji klasy abstrakcji i symetryczności 

): 

 i 

,

więc z przechodniości 

, sprzeczność.

Stąd dostajemy, Ŝe róŜne zbiory naleŜące do 

 są parami rozłączne, tzn. jeśli 

, to

. Istotnie, rozumujemy tu nie wprost. Przypuśćmy, Ŝe 

. Na mocy 3. i

prawa transpozycji dostajemy stąd 

, czyli (na mocy 2.) 

. 

Wniosek 9..3   Dla 

, 

.

Wniosek 9..4   Jeśli relacje równowaŜności 

 i 

 na zbiorze 

 mają te same klasy abstrakcji, to

.

Zasada abstrakcji. W przykładzie 2. podział zbioru ludzi na klasy abstrakcji odbywał się według znanej
cechy: wzrostu. ZałóŜmy, Ŝe 

 jest relacją równowaŜności na zbiorze 

. MoŜemy traktować klasę

abstrakcji elementu 

 jako nowy obiekt, swoistą cechę elementu   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   na płaszczyźnie: jest to klasa abstrakcji prostej 
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 
zbioru 

 na zbiory rozłączne i niepuste dostajemy relację równowaŜności 

, której klasami abstrakcji

są dokładnie te zbiory.

Funkcje. Jeśli kaŜdemu elementowi   zbioru 

 przypisany jest jeden element   zbioru 

 (niekoniecznie

ten sam dla róŜnych elementów  ), to mówimy, Ŝe na zbiorze 

 określona jest funkcja (inaczej:

przekształcenie lub odwzorowanie) przekształcająca zbiór 

 w zbiór 

, zaś   jest wartością tej funkcji

dla argumentu  . Oznaczając taką funkcję przez  , piszemy wtedy

Funkcje oznaczamy często literami 

.

Innymi słowy, funkcja 

 jest to dowolna relacja   między elementami zbioru 

 a elementami

zbioru 

, której dziedzina to cały zbiór 

, taka Ŝe dla kaŜdego 

 istnieje dokładnie jeden 

taki, Ŝe 

. Z tego względu, gdy zbiory 

 i 

 są skończone, moŜemy przedstawić funkcję   w

postaci diagramu. Strzałka od   do   oznacza, Ŝe 

.

Definicja 9..5   ZałóŜmy, Ŝe 

.

(1) Zbiór 

 nazywamy dziedziną funkcji  . Dziedzinę funkcji   oznaczamy teŜ przez 

.

(2) Zbiór 

 nazywamy obrazem lub zbiorem wartości funkcji  .

(3) Zbiór 

 nazywamy wykresem funkcji  .

Uwaga 9..6   Wprost z definicji wynika, Ŝe dwie funkcje   i   na zbiorze 

 są równe dokładnie wtedy,

gdy mają te same wartości dla wszystkich argumentów. Formalnie:

Przykład 0. Funkcja zdaniowa 

, to funkcja przypisująca elementom   zbioru 

 zdania

.

Przykład 1. Funkcja pusta 

, dziedziną i obrazem tej funkcji jest równieŜ zbiór pusty.

Przykład 2. Dla dowolnego zbioru 

 funkcja identycznościowa 

 dana jest wzorem

. Funkcja stała to funkcja, która dla wszystkich argumentów przyjmuje tę samą stałą wartość.

Przykład 3. Niech 

krzesło, stół, ławka

bratek, stokrotka . By określić funkcję

 wystarczy wypisać jej wartości dla wszystkich argumentów. Zamiast tego moŜna teŜ

narysować jej diagram. Przykładowo moŜemy określić   przez zdefiniowanie:

krzesło

 bratek, 

stół

 stokrotka i 

ławka

 bratek.

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

Jest 8 róŜnych funkcji 

. Istotnie, skoro zbiór 

 ma dwa elementy, dla kaŜdego 

wartość 

 moŜemy wybrać na dwa sposoby. Zbiór 

 ma trzy elementy, razem więc funkcję   moŜna

określić na 

 sposobów.

Przykład 4. Funkcje 

 i 

 określone wzorami

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

Z kaŜdą funkcją 

 związana jest pewna relacja 

 na zbiorze 

 określona wzorem

Łatwo sprawdzić, Ŝe 

 jest relacją równowaŜności. W przypadku, gdy 

, klasy

abstrakcji relacji 

 to zbiory par 

 o tej samej pierwszej współrzędnej.

Definicja 9..7   Niech 

.

(1)   jest róŜnowartościowa (inaczej: 1-1, wzajemnie jednoznaczna, jest injekcją), gdy dla róŜnych

argumentów ma róŜne wartości, tzn.

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

Piszemy wówczas 

.

(2)   jest ``na'' (inaczej: jest surjekcją), gdy cały zbiór 

 jest zbiorem wartości  . Symbolicznie:

Piszemy wówczas 

.

(3)   jest bijekcją, gdy jest 1-1 i ``na'', tzn. jest zarówno injekcją, jak i surjekcją. Piszemy wówczas

.

Czytelnik powinien stwierdzić, jak przy pomocy diagramu funkcji 

 (gdy zbiory 

 są

skończone) rozpoznać, czy funkcja jest bijekcją, injekcją czy surjekcją.

Uwaga 9..8   Jeśli 

 jest róŜnowartościowa, to 

 jest bijekcją.

Dowód. Z załoŜenia,  , traktowana jak funkcja przekształcająca zbiór 

 w 

, jest 

. Z

określenia zbioru 

 mamy, Ŝe jest równieŜ ``na''. 

Przykład 1. 

 dana jest wzorem 

. Wówczas   jest

``na'', jednak nie jest 1-1, bo np. 

.

Przykład 2. 

 określona jest wzorem

Zatem

Przy ustalonym  , dla 

 wartości funkcji   przebiegają więc okrąg o środku 

 i promieniu

.   jest więc ``na'', ale nie jest 1-1.

Definicja 9..9   ZałóŜmy, Ŝe 

 jest bijekcją. Wtedy kaŜdemu 

 przypisane jest jedyne

 takie, Ŝe 

. W ten sposób określona jest funkcja 

, która spełnia dla

wszystkich 

 zdanie

Funkcję 

 nazywamy funkcją odwrotną do  .

Uwaga 9..10   

 jest równieŜ bijekcją oraz   jest funkcją odwrotną do 

 (tzn.

).

Dowód. (1) 

 jest 1-1: niech 

. Wybierzmy 

 takie, Ŝe

Znaczy to, Ŝe 

 i 

. Zatem jeśli 

, to 

, więc w tym

przypadku 

 (na mocy 

).

(2) 

 jest ``na''. Niech 

 oraz 

. Widzimy, Ŝe 

 i 

. Dlatego

, czyli 

.

(3)   jest odwrotna do 

, gdyŜ mamy 

. 

Przykład. 

 dana jest wzorem 

. 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 

:

Dlatego funkcja 

 dana jest wzorem 

, czy teŜ równowaŜnie (po zamianie zmiennej 

w ostatnim wzorze na równie dobrą zmienną  ) 

.

Składanie funkcji. ZałóŜmy, Ŝe 

 oraz 

. Wtedy definiujemy funkcję

 wzorem 

. Prawa strona tego wzoru ma sens, bo dla

 oraz 

 jest dziedziną  , więc 

 istnieje. Funkcję 

 nazywamy złoŜeniem

(lub superpozycją) funkcji   i  . Piszemy teŜ 

 zamiast 

.

Uwaga 9..11   Jeśli 

 to 

.

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 

 i 

 mają wspólną dziedzinę: zbiór 

. Są one równe dokładnie

wtedy, gdy mają te same wartości dla wszystkich argumentów. Niech więc 

 będzie dowolnym

argumentem.

Z definicji złoŜenia funkcji dostajemy

Dla 

 moŜemy wykonywać wielokrotną superpozycję   z sobą. Dla 

 przyjmujemy

oznaczenia:

o ile 

 w drugim wzorze istnieje. Przyjmujemy teŜ 

.

Obcinanie (ograniczanie) i rozszerzanie funkcji.

ZałóŜmy, Ŝe 

 , 

 oraz 

.

(1) Definiujemy funkcję 

. Dla argumentów 

 wartości 

 są te same, co

wartości  , tzn. 

. Funkcję tę nazywamy obcięciem (ograniczeniem) funkcji   do zbioru

.

(2) Funkcję 

 nazywamy rozszerzeniem funkcji 

 dla kaŜdego 

 mamy

 (innymi słowy, gdy   jest obcięciem funkcji 

 do 

).

ZałóŜmy teraz, Ŝe 

. Wartość   funkcji   dla 

zapisujemy w postaci 

. Funkcję   nazywamy wtedy  -argumentową, zaś elementy

 nazywamy argumentami funkcji  .