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łaszczyz
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łaszczyz
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
A
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 .