Przykład 5.1.1

Niech X oznacza zbiór samochodów, które zostały wyprodukowane w latach 1951-2000. Zdefiniujemy w zbiorze X relację binarną ~ taką, że dla dowolnych x, y ÎX,

x ~ y wttw samochody x i y mają ten sam rok produkcji.

Relacja ta tworzy w zbiorze X pięćdziesiąt grup-klas. Oznaczmy te klasy kolejnymi liczbami rzymskimi I, II, III,... w taki sposób, że do klasy XL należą wszystkie te samochody, które zostały wyprodukowane w 1990 roku, a do klasy V - wszystkie te samochody, które zostały wyprodukowane w 1955r. Jeśli chcemy ustalić np. podatek drogowy, uzależniony od roku produkcji samochodu, to zamiast podawać wysokość podatku dla każdego xÎ X, wystarczy określić funkcję Podatek na klasach I, II,...,L. Podatek (IX) = x oznacza, że właściciele samochodów wyprodukowanych w 1959 roku płacą podatek w wysokości x zł.

Zauważmy, że relacja ~ jest zwrotna (dla wszystkich x, x~x), jest symetryczna (dla wszystkich x, y, jeśli x~y, to y~ x) oraz jest przechodnia (jeśli x~y i y ~z, to wszystkie trzy samochody zostały wyprodukowane w tym samym roku, czyli w szczególności, x i z są z tego samego roku). Własności zwrotności, symetrii i przechodniości przysługujące relacji = przeniosły się na relację ~.

Symbol relacji równoważności, jak to zwykle bywa w przypadku relacji binarnych, piszemy pomiędzy argumentami.

Przykładami relacji równoważności jest relacja równości, relacja równoległości prostych na płaszczyźnie, relacja podobieństwa trójkątów. Innym przykładem relacji równoważności jest relacja ~ zachodząca w zbiorze R^R wszystkich funkcji f : R ® R określona następująco: dla dowolnych funkcji f, g ze zbioru R^R ,

f ~ g wttw f(x) = g(x) dla wszystkich x Î R.

Na przykład, funkcje (x+1)*(x+1) i x² +2x +1 przyjmują te same wartości dla wszystkich argumentów, są więc w relacji ~. Relację tę oznacza się zwykle symbolem równości =.

Natomiast relacja r, określona w zbiorze R ^R warunkiem

f r g wttw f(x) = g(x) dla pewnego x Î R,

nie jest relacją równoważności. Chociaż jest to relacja zwrotna i symetryczna, to nie jest to jednak relacja przechodnia. Weźmy na przykład trzy funkcje f(x) = x, g(x) = x², h(x) = 2^x. Mamy (f, g) Î r , bo f(1) = g(1) =1, oraz (g, h) Î r, bo g(2) = h(2)= 4, ale nie istnieje takie xÎ R, dla którego 2 ^x = x (zawsze mamy x< 2 ^x ). Zwróćmy uwagę na różnicę między definicjami relacji ~ i relacji r. W pierwszym przypadku równość zachodziła dla wszystkich argumentów, natomiast w przypadku relacji r, wystarczy jeden punkt, w którym funkcje są zgodne. Taki warunek jest zbyt słaby by udowodnić przechodniość relacji r.

Rys. 5.1.1 (a) Funkcja f(i) = 10+i jest izomorfizmem odwzorowującym graf G' na G". (b) Przykład grafów nieizomorficznych (rożne liczby wierzchołków). (c) Przykład grafów nieizomorficznych (różne rzędy wierzchołków).

Pytanie 5.1.1: Czy relacja r określona dla dowolnych podzbiorów A, B zbioru X warunkiem

A r B wttw A È B = B,

jest relacją równoważności?

Przykład 5.1.2

(1) Niech będzie zbiór P programów napisanych w jakimś ustalonym języku programowania (np. w języku Java). Określimy relację binarną między programami następująco:

p₁ » p₂ wttw dla dowolnych danych d, program p₁ kończy obliczenie dla d wtedy i tylko wtedy, gdy p₂ kończy obliczenie dla d, oraz, jeżeli dla tych samych danych oba programy mają obliczenie skończone, to wyniki tych programów są identyczne.

Taka relacja jest oczywiście zwrotna, symetryczna i przechodnia. Jest więc relacją równoważności. Zwróćmy uwagę, że dwa programy równoważne w sensie tej definicji mogą się bardzo istotnie różnić, np. kosztem realizowanego algorytmu.

(2) Niech G'= <V', E'> i G" = <V", E"> będą dwoma grafami i f funkcją wzajemnie jednoznacznie odwzorowującą zbiór wierzchołków V' na V", f : V'® V", zachowującą relację sąsiedztwa, tzn. dla dowolnych v', u' Î V',

(v', u') Î E' wttw (f(v'), f(u'))Î E".

O przekształceniu f mówimy, że jest izomorfizmem odwzorowującym G' na G''.

Rozważmy teraz relację » zachodzącą między dwoma grafami wtedy i tylko wtedy, gdy istnieje izomorfizm odwzorowujący G' na G". O takich grafach mówimy, że są izomorficzne.

Grafy przedstawione na rysunku 5.1.1(a) są izomorficzne. Funkcja f(i)= 10*i ustala wzajemnie jednoznaczne przekształcenie pierwszego z grafów na drugi, zachowujące relację sąsiedztwa. Grafy przedstawione na rysunku 5.1.1(b) nie są izomorficzne, bo liczby wierzchołków w tych grafach są różne, a grafy przedstawione na rysunku 5.1.1(c) też nie są izomorficzne, bo jeden z nich ma wszystkie wierzchołki rzędu 3, a drugi tylko 2 wierzchołki rzędu 3.

Relacja » rozważana w dowolnym zbiorze grafów, jest relacją równoważności. Rzeczywiście,

• jest relacją zwrotną, bo każdy graf jest izomorficzny z samym sobą (izomorfizm ustala funkcja identycznościowa f(x) = x),

• jest relacją symetryczną, bo jeśli f ustala izomorfizm między G' i G" , to f ^-1 ustala izomorfizm między G" i G',

• jest relacją przechodnią, bo jeśli f jest izomorfizmem odwzorowującym G na G', a g izomorfizmem odwzorowującym G' na G", to f ° g jest izomorfizmem odwzorowującym G na G".

Zadanie 5.1.1

Udowodnić, że relacja podobieństwa trójkątów ~ zachodząca między dowolnymi dwoma trójkątami na płaszczyźnie wtedy i tylko wtedy, gdy mają takie same kąty, jest relacją równoważności.

Rozwiązanie. Relacja ta jest oczywiście zwrotna: każdy trójkąt jest podobny do samego siebie. Relacja ta jest też w oczywisty sposób symetryczna. Aby uzasadnić przechodniość, przyjmijmy, że D₁ ~ D₂ i D₂ ~ D₃. Wtedy, jeśli kąty trójkąta D ₁ wynoszą a, b i g stopni, to trójkąt D₂ ma jeden z kątów równy a , drugi równy b, a trzeci g. Podobnie, kąty trójkąta D₃ , jako równe kątom trójkąta D ₂, wynoszą też a, b i g. A zatem D₁ ~ D₃. Zauważmy, że jeśli f jest funkcją, która dowolnemu trójkątowi na płaszczyźnie przyporządkowuje zbiór liczb rzeczywistych {a, b, c} określających wartości (np. w stopniach) kątów tego trójkąta, to relację ~ można określić bardziej precyzyjnie przyjmując dla dowolnych D₁, D₂,

D₁ ~ D₂ wttw f(D₁) = f( D₂).

Dowód.

Zwrotność: Jeśli f jest funkcją całkowitą, to dla dowolnego x określona jest dokładnie jedna wartość f(x) i oczywiście f(x) = f(x).

Symetria: Ponieważ relacja = jest relacją symetryczną i wartości f(x) i f(x') są określone, to f(x) = f(x') implikuje f(x') = f(x). W konsekwencji x » x' wttw x' » x.

Przechodniość: Jeśli x » x' i x' » x'', to wartości funkcji f dla x, x' i x'' są takie same, a więc x » x''.J

Powyższy lemat daje prostą metodę konstruowania różnych relacji równoważności. Jeśli jednak f jest funkcją różnowartościową, to relacja równoważności wyznaczona przez f nie jest zbyt interesująca, gdyż żadne dwa różne elementy nie są w tej relacji.

Przykład 5.1.3

1. Rozważmy funkcję f(x) = x mod 3 określoną dla liczb naturalnych i o wartościach naturalnych. Wartością funkcji f dla argumentu x jest reszta z dzielenia x przez 3. Funkcja f wyznacza relację równoważności » ,

n » m wttw f(n) = f(m)

taką, że wszystkie liczby podzielne przez 3 są w relacji z liczbą 0 (bo przy dzieleniu przez 3 dają resztę 0), wszystkie liczby, które przy dzieleniu przez 3 dają resztę 1 są w relacji » z liczbą 1, i wreszcie, wszystkie liczby naturalne, które przy dzieleniu przez 3 dają resztę 2, są w relacji z 2. Relacja » wyznaczyła z zbiorze N podział na trzy grupy liczb, w zależności od tego jaką te liczby dają resztę przy dzieleniu przez 3.

(2) Dany jest graf niezorientowany G = <V, E>, gdzie V jest zbiorem wierzchołków, a E zbiorem krawędzi grafu G. Zdefiniujemy w zbiorze V relację (relacja osiągalności),

x ~ y wttw istnieje w G droga łącząca wierzchołki x i y.

Tak zdefiniowana relacja jest relacją równoważności w zbiorze wierzchołków tego grafu. Mówimy o niej, że jest tranzytywnym (tzn. przechodnim) domknięciem relacji sąsiedztwa w grafie. Zwrotność i symetria relacji ~ są oczywiste. Sprawdźmy przechodniość. Jeżeli x ~ y i y ~ z, tzn. istnieje droga od x do y i istnieje droga od y do z. Jeżeli wykorzystamy najpierw drogę od x do y, a potem drogę od y do z, to znajdziemy tym samym drogę od x do z, por. Rys.5.1.2(a). W grafie na rysunku 5.1.2(b) relacja ~ wyznacza podział zbioru wierzchołków na dwie grupy (nazywamy je spójnymi składowymi grafu). Graf relacji osiągalności przedstawiono na rysunku Rys. 5.1.2(b). Nie ma żadnych dróg łączących wierzchołki z różnych grup. Natomiast w każdej z grup, każdy wierzchołek jest osiągalny z każdego innego. Taką własność grafu nazywamy spójnością. Grafy przedstawione na rysunku 5.1.1 są spójne, a graf relacji osiągalności ~ jest grafem pełnym (tzn. każdy wierzchołek jest połączony krawędzią z każdym innym).

Rys. 5.1.2 Graf i jego tranzytywne domknięcie

1. w przypadku grafu spójnego,
2. w przypadku, gdy graf nie jest spójny.

Relację równoważności, jak każdą inną relację binarną, możemy przedstawić w postaci graficznej. Czytelnik zechce zwrócić uwagę na charakterystyczny kształt otrzymanego grafu :

zbiór wierzchołków grafu rozpada się na, wyraźnie od siebie oddzielone, grupy. Na rysunku 5.1.3 przedstawiono graficznie przykłady dwóch relacji równoważności zdefiniowanych za pomocą funkcji f(x) = x mod 3 i g(x)= x mod 4 w zbiorze {0,1,2,3,4,5,6}.

Rys. 5.1.3 Graficzne przedstawienie relacji równoważności wyznaczonej przez

1. funkcję f(x) = x mod 3,
2. funkcję g(x) = x mod 4, w zbiorze {0,1,...6}.

Pytanie 5.1.1: Czy suma dwóch relacji równoważności określonych w zbiorze X jest relacją równoważności?

Zadanie 5.1.2

Sprawdź, czy relacja r określona w zbiorze liczb rzeczywistych warunkiem: dla dowolnych x, yÎ R, (x, y) Î r wttw x-y Î Q, jest relacją równoważności.

Odpowiedź: Tak, to jest relacja równoważności. Relacja r jest zwrotna, bo 0 jest liczbą wymierną, a stąd (x - x) Î Q. Relacja r jest symetryczna, bo jeśli (x-y) jest liczbą wymierną, to jest nią liczba (y-x). Relacja r jest przechodnia, bo jeśli (x,y) Î r i (y,z)Î r, to (x-y) Î Q i (y-z) Î Q, skąd (dodając) otrzymamy, że (x-y)+(y-z) Î Q, czyli (x-z) Î Q.