« poprzedni punkt | następny punkt » |
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 4.4
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.
w1 ~ w2 wttw istnieje taka liczba kÎ R różna od zera, że w1.x = k * w2.x i w1.y = k*w2.y,
dla dowolnych wektorów w1, w2 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 oś Ox układu współrzędnych. Rozważana relacja ma nieskończenie wiele klas abstrakcji. Każda klasa abstrakcji to 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 3: 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?
Lemat 4.2
Niech ~ będzie relacją równoważności w X oraz [x], [y] klasami abstrakcji elementów x i y wyznaczonymi przez relację ~. Wówczas
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 6.
W poprzednim paragrafie tego wykładu uzasadnialiśmy, że każda funkcja pozwala zdefiniować relację równoważności (por. lemat 4.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 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 10.
Pytanie 4: Zdefiniowano relację równoważności przy pomocy pewnej funkcji f, tak jak w lemacie 4.1. Jaki warunek konieczny i dostateczny musi być spełniony aby klasy abstrakcji tej relacji były jednoelementowe?
« poprzedni punkt | następny punkt » |