Relacje równoważności

Relacja równoważności jest relacją binarną na zbiorze, która jest refleksyjna, symetryczna i przechodnia.

Uzasadnienie

Relacja równoważności jest swego rodzaju udoskonaleniem relacji równości. Zawsze możemy zdecydować, że dwa elementy zbioru są równe, tj. że a = a. Ale czasami warto sprawdzić, czy dwa elementy są tylko podobne, niekoniecznie równe. Lub - czy mają tę samą istotną właściwość. Na przykład dwie książki można uznać za podobne, jeśli mają ten sam gatunek - lub przez równoważność: dwie książki są równoważne, jeśli mają ten sam gatunek.

Czego moglibyśmy oczekiwać od takiej równoważności? Weźmy inny przykład. Dwa słowa są podobne/równoważne, jeśli mają tę samą długość.

Prawdopodobnie spodziewalibyśmy się, że jeśli zmierzymy podobieństwo dwóch słów, to wyjdą one podobne. Tak więc musi być prawdą dla wszystkich słów, że są one podobne/równoważne do siebie. W języku relacyjnym: relacja równoważności musi być refleksyjna.

Co więcej, jeśli słowo "potok" jest podobne/równoważne słowu "Agata", to z pewnością oczekujemy, że słowo "Agata" będzie równoważne słowu "potok". Innymi słowy, kolejność nie ma znaczenia. W języku relacyjnym: relacja równoważności musi być symetryczna.

Wreszcie, jeśli słowo "śmierć" jest podobne/równoważne słowu "ptak", a słowo "ptak" jest równoważne słowu "stopa", to oczekujemy, że pary słów "śmierć" i "stopa" również będą równoważne. Zatem relacja równoważności musi być również przechodnia.

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

Przykłady

Więcej przykładów równoważności:

• Mieszkać w tym samym mieście. Jirka na pewno mieszka w tym samym mieście co Jirka (refleksyjność). Jeśli Jirka mieszka w tym samym mieście co Ondra, to Ondra mieszka w tym samym mieście co Jirka (symetria). A jeśli Ondra mieszka w tym samym mieście co Martin, to Jirka mieszka w tym samym mieście co Martin (przechodniość).
• Piosenki z tym samym autorem. Piosenka "The Furious Monologue of the Son of the Hatch" z pewnością ma tego samego autora co piosenka "The Furious Monologue of the Son of the Hatch" (refleksyjność). Jeśli piosenki "The Furious Monologue of the Son of the Hatch" i "War on the Rags" mają tego samego autora, to "War on the Rags" i "The Furious Monologue of the Son of the Hatch" mają tego samego autora (symetria). A jeśli "The War on Staves" i "The Quest for the Truth of Filth" mają tego samego autora, to "The Furious Monologue of the Son of the Hatch" i "The Quest for the Truth of Filth" mają tego samego autora (przechodniość).
• [a, b] ∈ R Właśnie wtedy, gdy a − b jest liczbą parzystą; a, b są liczbami całkowitymi. Refleksyjność: a − a = 0, zero jest liczbą parzystą. Symetria: oznacz c = a − b. Wtedy b − a = −(a − b) = −c. Jeśli c jest parzyste, to −c musi być parzyste. Przechodniość: oznacz p = a − b, a następnie q = b − c. Wiemy, że p i q są liczbami parzystymi. Teraz musimy udowodnić, że a − c jest liczbą parzystą. Podstawiamy c = b − q: a−(b − q), która jest równa a − b + q, do tego równania po c. Z założeń wiemy, że a − b jest liczbą parzystą. Jeśli dodamy kolejną liczbę parzystą do liczby parzystej q, otrzymamy ponownie liczbę parzystą.
• Równość. Równość to równoważność, to także najmniejsza równoważność na dowolnym zbiorze M.

Trywialna równoważność

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

Z pewnością jest symetryczny, ponieważ sesja R nie ma elementów, warunek symetrii jest automatycznie i trywialnie spełniony. Podobnie jest z przechodniością. Problem jest z refleksyjnością. Definicja mówi, że dla wszystkich elementów x zbioru M prawdą jest, że [x, x] ∈ R. Czy warunek ten jest spełniony? Zbiór M jest niepusty, więc zawiera jakiś element, na przykład q. Czy para [q, q] jest w sesji R? Nie jest. Zatem sesja R nie jest refleksyjna.

Jaka jest najmniejsza sesja spełniająca warunek refleksyjności? Sesja równości. Sesja R musi zawierać co najmniej parę [x, x] dla wszystkich elementów M. Co jest po prostu sesją tożsamości. Czy taka sesja jest symetryczna? Łatwo zauważyć, że tak. Podobnie łatwo zauważyć, że jest przechodnia. Zatem najmniejsza relacja równoważności na zbiorze M jest relacją tożsamości, oznaczaną id_M, i zawiera pary [x, x] dla wszystkich x ∈ M.

Jaka jest największa możliwa relacja równoważności na zbiorze M? Największym podzbiorem jest cały zbiór M × M. Czy spełnia on warunki równoważności? Prawdopodobnie trywialne jest sprawdzenie, że tak.

Klasa równoważności

Każda równoważność dzieli zbiór M na system rozłącznych zbiorów, które następnie nazywamy klasami równoważności.

Rozważmy zbiór wszystkich słów M i równoważność R o tej samej długości słowa. To znaczy, [a, b] ∈ R tylko wtedy, gdy słowa a i b mają tę samą długość. Równoważność ta dzieli zbiór słów na kilka mniejszych zbiorów, które zawsze będą zawierać słowa o tej samej długości. Możemy rozróżnić różne klasy równoważności za pomocą indeksu dolnego, który będzie również rozróżniał długość słów w zbiorze:

• M₁ = {a, i, o, e, …}
• M₂ = {ve, do, se, my, mi, …}
• M₃ = {ale, bez, ten, tam, …}
• M₄ = {smrt, park, lest, niva, …}
• ...

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

W ten sposób każdy element jednoznacznie definiuje swoją klasę równoważności. Zwykle zapisujemy to za pomocą notacji M[x], gdzie x ∈ M. Gdybyśmy napisali M[ale], jednoznacznie zdefiniowalibyśmy klasę równoważności, którą już oznaczyliśmy jako M₃.

Jak właściwie znaleźć klasę równoważności, jeśli znamy x ∈ M? Przechodzimy przez wszystkie elementy w M i dowiadujemy się, które z tych elementów są równoważne elementowi x. Będą to wszystkie elementy, które będą częścią klasy równoważności M[x].

W przypadku M[ale], przechodzimy przez wszystkie słowa w M i przechowujemy w M₃ te słowa, które mają długość trzech.

Definicja i właściwości klasy równoważności

Możemy zdefiniować klasę równoważności w następujący sposób. Rozważmy zbiór M i zdefiniowaną na nim równoważność R. Następnie rozumiemy klasę rozkładu, która zawiera element x ∈ M:

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

Definicja mówi, że są to wszystkie y, które są równoważne określonemu elementowi x. Ponieważ relacja równoważności jest refleksyjna, element x dostaje się tam w ten sposób - ponieważ x jest równoważny samemu sobie.

Dekompozycja równoważności jest zatem zbiorem wszystkich klas równoważności. Tak więc dekompozycja zbioru wszystkich słów byłaby zbiorem {M₁, M₂, M₃, …}.

Podstawowe własności klas równoważności:

• [a, b] ∈ R a, b Jeśli mamy dwa elementy M[a] = M[b], które są równoważne, to ich klasy równoważności muszą być równe.
• I odwrotnie, jeśli [a, b] ∈ M, to także M[a] ≠ M[b], a dokładniej M[a] ∩ M[b] = ∅. Jeśli mamy dwa elementy, które nie są równoważne, to ich klasy rozkładu są rozłączne.
• Związek wszystkich klas równoważności musi dać oryginalny zbiór M: M₁ ∪ M₂ ∪ … ∪ M_n = M(Poprzednia notacja dotyczy tylko skończonej liczby klas równoważności, ale w ogólności może być ich nieskończenie wiele).

Przykłady dekompozycji równoważności

Pierwszy przykład, liczby nieparzyste i parzyste:

Rozważmy prostą równoważność R zdefiniowaną na liczbach naturalnych N. [a, b] ∈ R tylko wtedy, gdy a i b są nieparzyste lub a i b są parzyste. Przykłady elementów: [1, 7], [13, 9], [4, 6], [8, 136]. Określmy teraz rozkład tej równoważności na klasy równoważności.

Zaczniemy sekwencyjnie. Co będzie równe klasie N[1]? Musimy znaleźć wszystkie liczby, które są równoważne jedynce. Zgodnie z warunkiem równoważności, wszystkie te liczby są nieparzyste, więc N[1] = {1, 3, 5, 7, 9, …}.

Jaka będzie klasa N[2]? Znajdujemy wszystkie liczby, które są równe dwa. Są to liczby parzyste: N[2] = {2, 4, 6, 8, 10, …}.

Teraz N[3]. Jakie liczby są równe trzy? Wszystkie liczby nieparzyste. Ale to daje nam zbiór N[1], który obliczyliśmy w poprzednim akapicie. Podobnie dla N[4], znów mamy zbiór liczb parzystych.

Widzimy, że od tego momentu te same zbiory będą się powtarzać. Widać to również po tym, że jakąkolwiek inną liczbę naturalną n, weźmiemy, będzie już prawdą, że n ∈ N[1] lub n ∈ N[2]. Nie mamy liczb naturalnych innych niż liczby nieparzyste i parzyste, więc te dwa zbiory tworzą rozkład równoważności.

Jest to podobne do wyobrażenia sobie równoważności na zbiorze osób a i b jest mężczyzną lub a i b jest kobietą. Wtedy otrzymalibyśmy zbiór kobiet i zbiór mężczyzn jako dekompozycję.

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

Miejmy równoważność R na zbiorze liczb całkowitych Z zdefiniowaną w następujący sposób: [a, b] ∈ R tylko jeśli |a| = |b|. (Pionowe linie oznaczają wartość bezwzględną):

• Z[0] = {0}. Zero jest w relacji tylko z zerem.
• Z[1] = {−1, 1}. Jeden jest w relacji z jeden i minus jeden, ponieważ |1| = |−1|.
• Z[2] = {−2, 2}. Dwa jest w relacji z dwa i z minus dwa.
• Z[3] = {−3, 3}.
• ...

Myślę, że jest jasne, jak to pójdzie. Więc cała dekompozycja byłaby zbiorem klas:

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

(czyli wszystkich par a, −a, gdzie a jest nieujemną liczbą całkowitą.) Widać, że klas jest nieskończenie wiele.