Jeśli ~ jest relacją równoważności w zbiorze X, to przyjmujemy oznaczenie

[x] = {y Î X : x ~ y}.

O zbiorze [x] mówimy: klasa abstrakcji lub klasa równoważności elementu x, ze względu na relację ~. O elemencie x mówimy, że jest reprezentantem klasy [x].

Przykład 5.2.1

1. W zbiorze liczb naturalnych N określmy relację r następująco: (x,y)Î r wttw x+y jest liczbą parzystą. Taka relacja jest zwrotna, bo x+x = 2x jest liczbą parzystą. Jest to relacja symetryczna, ze względu na przemienność dodawania. Jest to też relacja przechodnia, bo jeśli x + y jest liczbą parzystą i y + z jest liczbą parzystą, to

• albo x i y są obie parzyste, a wtedy y i z muszą też obie być parzyste,
• albo x i y są obie nieparzyste, ale wtedy y i z też muszą być nieparzyste.

Wynika stąd, że suma liczb x + z jest w obu przypadkach parzysta. Klasa abstrakcji liczby 0 zawiera wszystkie liczby parzyste, [0] = P. Klasa abstrakcji liczby 1 zawiera wszystkie liczby nieparzyste, [1] = NP. Te dwie klasy wyczerpują wszystkie liczby naturalne.

2. Niech X będzie zbiorem wszystkich niezerowych wektorów na płaszczyźnie zaczepionych w początku układu współrzędnych O. Każdy taki wektor w może być scharakteryzowany jednoznacznie przez współrzędne (w.x, w.y) punktu końcowego. Rozważmy relację w zbiorze X określoną następująco:

   w₁ ~ w₂ wttw istnieje różna od zera liczba rzeczywista z, taka że w₁.x = z * w₂.x i w₁.y = z*w₂.y,

   dla dowolnych wektorów w₁, w₂ należących do X.

   Z podanej definicji wynika, że dwa wektory ze zbioru X są w relacji wtedy i tylko wtedy, gdy ich punkty końcowe leżą na tej samej prostej przechodzącej przez początek układu współrzędnych. Oczywiście jest to relacja równoważności.

   Klasa abstrakcji wektora w, którego punktem końcowym jest (1,0), to zbiór tych wektorów, które leżą na osi Ox układu współrzędnych. Rozważana relacja ma nieskończenie wiele klas abstrakcji. Każdą klasę abstrakcji charakteryzuje jakaś prosta przechodząca przez początek układu współrzędnych.

Następujący lemat ustala podstawowe własności klas abstrakcji. Po pierwsze, każda klasa abstrakcji jest niepusta, po drugie, jeśli dwa elementy są ze sobą w relacji, to ich klasy abstrakcji są identyczne, i po trzecie, dowolne różne klasy abstrakcji są rozłączne.

Pytanie 5.2.1: Ile klas abstrakcji ma relacja równoważności określona w zbiorze liczb całkowitych warunkiem: x r y wttw x mod 4 = y mod 4?

Dowód.

Ad(1) Własność (1) wynika natychmiast ze zwrotności relacji ~.

Ad(2) Dla dowodu własności (2) załóżmy, że x ~ y. Wtedy zachodzą następujące równoważności:

z Î [x] wttw z ~ x wttw z ~ y wttw z Î [y].

Czyli [x] = [y].

Odwrotnie, załóżmy teraz, że [x] = [y]. Ponieważ na mocy (1) x Î [x], to x Î [y], a stąd i z definicji klasy abstrakcji wynika x ~ y.

Ad(3) Załóżmy [x] ¹ [y]. Gdyby [x] Ç [y] ¹ Æ , to istniałby element z taki, że z Î [x] i z Î [y]. Stąd mielibyśmy z ~ x i z ~ y. Zatem, z symetrii i przechodniości relacji ~, otrzymalibyśmy x ~ y, co na mocy punktu (2) tego lematu doprowadza do sprzeczności z założeniem.

Uwaga. Dowody takie, jak przedstawiony w punkcie (3) powyższego lematu, nazywamy dowodami "nie wprost" lub "przez sprowadzanie do sprzeczności" lub "apagogicznymi". O dowodach tego typu będziemy mówili dokładniej w wykładzie VII.

W poprzednim paragrafie tego wykładu uzasadnialiśmy, że każda funkcja pozwala zdefiniować relację równoważności (por. lemat 5.1.1). Okazuje się, że jest też odwrotnie: każda relacja równoważności w niepustym zbiorze X wyznacza pewną funkcję f~, odwzorowującą zbiór X w zbiór potęgowy P(X), określoną następująco: f_~(x) = [x]. Funkcja ta nazywa się odwzorowaniem kanonicznym. Jest to oczywiście funkcja całkowita, bo każdy element należy do klasy abstrakcji, której jest reprezentantem i, na ogół, nie jest różnowartościowa, bo dla wszystkich y ~ x, f_~ (x) = [x]=[y]= f_~ (y). O własnościach tego odwzorowania będzie mowa w wykładzie XV.

Pytanie 5.2.2: Zdefiniowano relację równoważności przy pomocy pewnej funkcji f, tak jak w lemacie 5.1.1. Jaki warunek konieczny i dostateczny musi być spełniony aby klasy abstrakcji tej relacji były jednoelementowe?

« poprzedni punkt

następny punkt »