Relacja równoważności

Relacja równoważności to relacja dwuargumentowa w zbiorze, która jest zwrotna, symetryczna i przechodnia.

Motywacja

Relacja równoważności jest czymś w rodzaju uogólnienia relacji równości. Zawsze możemy rozstrzygnąć, czy dwa elementy zbioru są takie same, tzn. czy a = b. Czasem jednak przydaje się sprawdzić, czy dwa elementy są do siebie tylko podobne, a niekoniecznie takie same. Innymi słowy — czy mają taką samą jakąś istotną własność. Na przykład dwie książki możemy uznać za podobne, jeśli należą do tego samego gatunku — albo za pomocą równoważności: dwie książki są równoważne, jeśli należą do tego samego gatunku.

Czego oczekiwalibyśmy od takiej równoważności? Weźmy inny przykład. Dwa słowa są podobne/równoważne, jeśli są tak samo długie.

Pewnie oczekiwalibyśmy, że jeśli zmierzymy podobieństwo dwóch takich samych słów, to wyjdzie nam, że są podobne. Czyli dla wszystkich słów musi zachodzić, że są podobne/równoważne same ze sobą. W języku relacji: relacja równoważności musi być zwrotna.

Dalej, jeśli słowo „potok” jest podobne/równoważne słowu „Agata”, to na pewno oczekujemy, że także słowo „Agata” będzie równoważne słowu „potok”. Innymi słowy kolejność nie ma znaczenia. W języku relacji: relacja równoważności musi być symetryczna.

I wreszcie jeśli słowo „lato” jest podobne/równoważne słowu „ptak”, a słowo „ptak” jest równoważne słowu „noga”, to oczekujemy, że także para słów „lato” i „noga” będzie równoważna. Relacja równoważności musi więc być też przechodnia.

Niczego więcej od równoważności nie oczekujemy.

Przykłady

Kolejne przykłady relacji równoważności:

• Mieszkać w tym samym mieście. Jurek na pewno mieszka w tym samym mieście co Jurek (zwrotność). Jeśli Jurek mieszka w tym samym mieście co Olek, to i Olek mieszka w tym samym mieście co Jurek (symetryczność). A jeśli Olek mieszka w tym samym mieście co Marcin, to i Jurek mieszka w tym samym mieście co Marcin (przechodniość).
• Piosenki tego samego autora. Piosenka „Biała flaga” ma na pewno tego samego autora co piosenka „Biała flaga” (zwrotność). Jeśli piosenki „Biała flaga” i „Telefony” mają tego samego autora, to i „Telefony” i „Biała flaga” mają tego samego autora (symetryczność). A jeśli „Telefony” i „Mamona” mają tego samego autora, to i „Biała flaga” i „Mamona” mają tego samego autora (przechodniość).
• (a, b) ∈ R wtedy i tylko wtedy, gdy a − b jest liczbą parzystą; a, b są liczbami całkowitymi. Zwrotność: a − a = 0, zero jest liczbą parzystą. Symetryczność: oznaczmy c = a − b. Wtedy b − a = −(a − b) = −c. Jeśli c jest parzyste, to także −c musi być parzyste. Przechodniość: oznaczmy p = a − b, dalej q = b − c. Wiemy, że p i q są liczbami parzystymi. Teraz mamy udowodnić, że a − c jest liczbą parzystą. Do tego wyrażenia za c podstawimy c = b − q: a−(b − q), co jest równe a − b + q. Z założeń wiemy, że a − b jest liczbą parzystą. Jeśli do liczby parzystej dodamy kolejną liczbę parzystą q, dostaniemy znowu liczbę parzystą.
• Równość. Równość jest relacją równoważności, jest to jednocześnie najmniejsza relacja równoważności w dowolnym zbiorze M.

Trywialne relacje równoważności

Mamy niepusty zbiór M. Jaka jest najmniejsza możliwa relacja równoważności R w zbiorze M? Najmniejszym możliwym podzbiorem iloczynu kartezjańskiego M × M jest zbiór pusty ∅. Czy zbiór pusty spełnia warunki relacji równoważności?

Na pewno jest symetryczny, ponieważ relacja R nie ma żadnych elementów, więc warunek symetryczności jest automatycznie i trywialnie spełniony. Podobnie przechodniość. Problem jest ze zwrotnością. Definicja mówi, że dla wszystkich elementów x zbioru M zachodzi (x, x) ∈ R. Czy to jest spełnione? Zbiór M jest niepusty, więc zawiera jakiś element, na przykład q. Czy para (q, q) jest w relacji R? Nie jest. Relacja R nie jest więc zwrotna.

Jaka jest najmniejsza relacja spełniająca zwrotność? Relacja równości. Relacja R musi zawierać co najmniej pary (x, x) dla wszystkich elementów M. A to jest właśnie relacja identyczności. Czy taka relacja jest symetryczna? Łatwo widać, że tak. Podobnie łatwo widać, że jest też przechodnia. Najmniejszą relacją równoważności w zbiorze M jest więc relacja identyczności, oznaczamy ją id_M, i zawiera ona pary (x, x) dla wszystkich x ∈ M.

Jaka jest największa możliwa relacja równoważności w zbiorze M? Największym podzbiorem jest cały zbiór M × M. Czy spełnia warunki relacji równoważności? Chyba widać od razu, że tak.

Klasa abstrakcji

Każda relacja równoważności dzieli zbiór M na rodzinę zbiorów rozłącznych, które nazywamy wtedy klasami abstrakcji (albo klasami równoważności).

Weźmy zbiór wszystkich słów M i relację równoważności R „tak samo długie słowo”. Czyli (a, b) ∈ R wtedy i tylko wtedy, gdy słowa a i b mają taką samą długość. Ta relacja równoważności podzieli zbiór słów na kilka mniejszych zbiorów, które będą zawsze zawierać słowa tej samej długości. Poszczególne klasy abstrakcji możemy rozróżnić za pomocą dolnego indeksu, który będzie jednocześnie oznaczał długość słów w danym zbiorze:

• M₁ = {a, i, o, w, …}
• M₂ = {we, do, na, my, mi, …}
• M₃ = {ale, bez, ten, tam, …}
• M₄ = {lato, park, ptak, noga, …}
• …

Zauważ dwie rzeczy: 1) poszczególne zbiory są wzajemnie rozłączne, nie mają żadnego wspólnego elementu. 2) wszystkie elementy w każdym poszczególnym zbiorze są wzajemnie równoważne. Wszystkie słowa w zbiorze M₃ są wzajemnie równoważne, bo wszystkie słowa mają długość trzy, czyli taką samą długość, co jest warunkiem równoważności.

Przy tym każdy element jednoznacznie wyznacza swoją klasę abstrakcji. Zwykle zapisujemy to za pomocą notacji M[x], gdzie x ∈ M. Gdybyśmy napisali M[ale], to jednoznacznie wyznaczymy tym klasę abstrakcji, którą oznaczyliśmy już jako M₃.

Jak właściwie znajdziemy klasę abstrakcji, jeśli znamy jakieś x ∈ M? Przejdziemy wszystkie elementy w M i sprawdzimy, które z tych elementów są równoważne z elementem x. To będą wszystkie elementy, które będą należeć do klasy abstrakcji M[x].

Dla M[ale] przeszlibyśmy wszystkie słowa w M i zatrzymali w M₃ takie słowa, które mają długość trzy.

Definicja i własności klasy abstrakcji

Klasę abstrakcji moglibyśmy zdefiniować tak. Weźmy zbiór M i zdefiniowaną w nim relację równoważności R. Wtedy przez klasę abstrakcji, która zawiera element x ∈ M, rozumiemy:

$$M[x] = {y \in M; (x, y) \in R}$$

Definicja mówi, że są to wszystkie y, które są równoważne z danym elementem x. Ponieważ relacja równoważności jest zwrotna, w ten sposób dostanie się tam także sam element x — bo x jest równoważny sam ze sobą.

Podziałem zbioru wyznaczonym przez relację równoważności (zbiorem ilorazowym) nazywamy wtedy zbiór wszystkich klas abstrakcji. Podziałem zbioru wszystkich słów byłby więc zbiór {M₁, M₂, M₃, …}.

Podstawowe własności klas abstrakcji:

• (a, b) ∈ R wtedy i tylko wtedy, gdy M[a] = M[b]. Jeśli mamy dwa elementy a, b, które są równoważne, to ich klasy abstrakcji muszą być równe.
• Odwrotnie, jeśli nie zachodzi (a, b) ∈ R, to także M[a] ≠ M[b], dokładniej M[a] ∩ M[b] = ∅. Jeśli mamy dwa elementy, które nie są równoważne, to ich klasy abstrakcji są rozłączne.
• Suma wszystkich klas abstrakcji musi dać wyjściowy zbiór M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Poprzedni zapis jest tylko dla skończonej liczby klas abstrakcji, ale w ogólności może ich być nieskończenie wiele.)

Przykłady podziałów na klasy abstrakcji

Pierwszy przykład, liczby nieparzyste i parzyste:

Weźmy prostą relację równoważności R zdefiniowaną na liczbach naturalnych N. (a, b) ∈ R wtedy i tylko wtedy, gdy a i b są nieparzyste albo a i b są parzyste. Przykłady elementów: (1, 7), (13, 9), (4, 6), (8, 136). Podzielmy teraz zbiór liczb naturalnych na klasy abstrakcji tej relacji.

Zaczniemy po kolei. Czemu będzie równa klasa N[1]? Musimy znaleźć wszystkie liczby, które są równoważne z liczbą jeden. Według warunku równoważności są to wszystkie liczby nieparzyste, więc N[1] = {1, 3, 5, 7, 9, …}.

Czemu będzie równa klasa N[2]? Znajdziemy wszystkie liczby, które są równoważne z dwójką. Są to wszystkie liczby parzyste: N[2] = {2, 4, 6, 8, 10, …}.

Teraz N[3]. Jakie liczby są równoważne z trójką? Wszystkie liczby nieparzyste. W ten sposób dostaniemy jednak zbiór N[1], który wyznaczyliśmy dwa akapity wcześniej. Podobnie dla N[4], tam znowu dostaniemy zbiór liczb parzystych.

Widzimy, że dalej powtarzałyby się już ciągle te same zbiory. Widać to też z tego, że jakąkolwiek kolejną liczbę naturalną n weźmiemy, będzie już zachodzić n ∈ N[1] albo n ∈ N[2]. Innych liczb naturalnych niż nieparzyste i parzyste nie mamy, więc te dwa zbiory tworzą podział wyznaczony przez tę relację równoważności.

Jest to podobne, jakbyśmy sobie wyobrazili relację równoważności w zbiorze ludzi: a i b są mężczyznami albo a i b są kobietami. Wtedy jako podział dostalibyśmy zbiór kobiet i zbiór mężczyzn.

Drugi przykład, wartość bezwzględna:

Weźmy relację równoważności R w zbiorze liczb całkowitych Z zdefiniowaną tak: (a, b) ∈ R wtedy i tylko wtedy, gdy |a| = |b|. (Te kreski pionowe to wartość bezwzględna.) Znowu pójdziemy po kolei:

• Z[0] = {0}. Zero jest w relacji tylko z zerem.
• Z[1] = {−1, 1}. Jedynka jest w relacji z jedynką i z minus jedynką, bo |1| = |−1|.
• Z[2] = {−2, 2}. Dwójka jest w relacji z dwójką i z minus dwójką.
• Z[3] = {−3, 3}.
• …

Chyba jasne jest, jak to będzie dalej wyglądać. Całym podziałem byłby więc zbiór klas:

$${{a, -a}; a \in \mathbb{Z}_0^+}$$

(Czyli wszystkie pary a, −a, gdzie a jest nieujemną liczbą całkowitą.) Widzisz, że klas jest nieskończenie wiele.