Relacja w matematyce

Mój drogi Czytelniku. Dziękuję, że kliknąłeś w link do tego artykułu, mimo że tytuł sugeruje, iż dzisiejszy wpis nie będzie dotyczył bezpośrednio programowania w Javie (ale częściowo dotyczy – doczytaj do końca a się przekonasz). Już dość dawno rozpocząłem cykl artykułów matematycznych. No dobra, napisałem tylko jeden wpis na ten temat. Ale chciałbym wrócić do tej tematyki. Matematyka jest piękna! Dodatkowo uważam, że programista bez znajomości matematyki wyższej nie zostanie wybitnym programistą. Ale mogę się mylić, zachęcam do dyskusji w komentarzach.

Relacja

We wspomnianym już artykule pod tytułem Wstęp do matematyki, zdefiniowałem czym jest iloczyn kartezjański. Dziś pokażę, jaki z niego pożytek. Dla krótkiego przypomnienia:

Definicja iloczynu kartezjańskiego

Iloczyn kartezjański dowolnych zbiorów A i B to zbiór, który definiujemy w następujący sposób:

    \[A \times B ~= ~\{(a,b)~:~a \in A \wedge b\in B\}\]

Możemy tę definicję odczytać:

Iloczyn kartezjański dwóch zbiorów A i B to jest zbiór par, z których pierwszy element należy do zbioru A a drugi do zbioru B.

Gdy mamy zbiory A = \{1,2,3\} oraz B = \{a,b,c,d\}. To wtedy:

    \[\begin{array}{lll} A \times B = & \{ & \\ && (1,a), (1,b), (1,c), (1,d), \\ & &(2,a),(2,b),(2,c),(2,d),\\ &&(3,a),(3,b),(3,c),(3,d)\\ & \}&\end{array}\]

Definicja relacji

Jak już pamiętamy, czym jest iloczyn kartezjański, to możemy zdefiniować relację R na zbiorach A i B jako podzbiór iloczynu kartezjańskiego:

    \[R \subset A \times B\]

Możemy powiedzieć, że element a ze zbioru A jest w relacji R z elementem b ze zbioru B, gdy te elementy spełniają jakiś warunek. Za chwilę przejdę do przykładów, ale pozwól mi najpierw pokazać, jak matematycznie zapisujemy, że elementy a i b są w relacji:

    \[aRb\]

lub też równoważnie:

    \[(a,b) \in R\]

Przykłady relacji

Przykład 1

  • A – zbiór samochodów
  • B – zbiór ludzi

Możemy zdefiniować relację R na zbiorach A i B w następujący sposób: samochód a \in A jest w relacji R z osobą b\in B, gdy b jest właścicielem a.

Przykład 2

  • A – zbiór widelców
  • B – zbiór noży
  • C – zbiór łyżek

Relację R możemy zdefiniować następująco: widelec a \in A, nóż b \in B oraz łyżka c \in C są ze sobą w relacji R ((a,b,c) \in R \subset A \times B \times C), gdy można je bez wstydu położyć przy jednym talerzu (czyli należą do jednego kompletu).

W matematyce wielkie znaczenie mają relację zdefiniowane na jednym zbiorze. Czyli R \subset A \times A = A^2.

Przykład 3

  • A zbiór osób

Osoba a \in A jest w relacji R z osobą b \in A, gdy a jest rodzicem b.

Przykład 4

  • A zbiór osób

Osoba a \in A jest w relacji R z osobą b \in A, gdy a jest małżonkiem b.

Przykład 5

  • A zbiór osób

Osoba a \in A jest w relacji R z osobą b \in A, gdy a jest spokrewniona z osobą b.

Może przejdę do przykładów bardziej matematycznych.

Przykład 6

  • A zbiór prostych

Proste a \in A i b\in B są ze sobą w relacji R, gdy a i b są do siebie prostopadłe.

Przykład 7

  • A zbiór prostych

Proste a \in A i b\in B są ze sobą w relacji R, gdy a i b są do siebie równoległe.

Przykład 8

  • A zbiór liczb całkowitych

Liczby a \in A i b\in B są ze sobą w relacji R, gdy a i b dają taką samą resztę przy dzieleniu przez siedem. Swoją drogą, to jest bardzo ważna relacja w matematyce i informatyce również!

Relacja równoważności

Jak już wspomniałem, w matematyce relacja określona na jednym zbiorze zajmuje szczególnie ważne miejsce. To właśnie wśród takich relacji wyróżnia się relację równoważności. Relacja R \in A^2 jest relacją równoważności, gdy spełnia trzy następujące warunki:

  • Jest zwrotna – każdy element a \in A jest w relacji R z samym sobą:

        \[\forall ~a\in A~:~~aRa\]

  • Jest symetryczna – jeżeli element a\in A jest w relacji R z elementem b \in A, to również element b jest w relacji R z elementem a:

        \[\forall ~a,b\in A~:~~aRb ~~\Rightarrow ~~bRa\]

  • Jest przechodnia – jeżeli element a\in A jest w relacji R z elementem b \in A oraz element b\in A jest w relacji R z elementem c \in A, to element a jest w relacji z elementem c:

        \[\forall ~a,b,c\in A~:~~aRb~\wedge~bRc~~\Rightarrow~~aRc\]

Przeanalizujmy teraz przykłady, które podałem przed chwilą i zastanówmy się, które z nich są relacjami równoważności.

Relacja bycia rodzicem

Siłą rzeczy, Alicja (dowolny element ze zbioru osób) nie może być swoim własnym rodzicem. Nie zachodzi więc warunek zwrotności i relacja bycia rodzicem nie jest relacją równoważności.

Relacja bycia małżonkiem

Z tego samego powodu, relacja bycia małżonkiem również nie jest relacją równoważności – nie można być małżonkiem samego siebie. Zwróćmy jednak uwagę, że tutaj zachodzi warunek symetrii: jeżeli Alicja jest małżonkiem (bardziej gramatycznie byłoby powiedzieć małżonką) Boba, to Bob jest również małżonkiem Alicji. W poprzedniej relacji warunek symetrii nie był spełniony. Jeżeli Alicja jest rodzicem Boba, to nie ma opcji żeby Bob był rodzicem Alicji (pomijając niektóre seriale o podróżach w czasie, pozdro dla kumatych)

Relacja pokrewieństwa

W tym wypadku zwrotność (uznajmy, że każdy jest spokrewniony z samym sobą) i symetria są spełnione. Jednak warunek przechodniości już nie bardzo… Bo może się zdarzyć, że Alicja jest spokrewniona z Bobem (na przykład jest jego siostrą cioteczną), Bob jest spokrewniony z Cezarym (są braćmi ciotecznymi), ale Alicja i Cezary mogą nie być ze sobą spokrewnieni. Tak, to jest bardzo wydumana sytuacja, ale właśnie to nie pozwala uznać relacji pokrewieństwa za relację równoważności.

Relacja prostopadłości

Tutaj mamy krótką piłkę – prosta nie może być prostopadła do siebie samej. Przez niespełniony warunek zwrotności nie możemy uznać tej relacji za relację równoważności.

Relacja równoległości

Ta relacja jest relacją równoważności. To będzie uzasadnienie przez machanie rękami, ale:

  • zwrotność – możemy przyjąć, że prosta jest równoległa do siebie samej
  • symetria – wszyscy widzimy, że zachodzi
  • przechodniość – również zachodzi

Relacja dawania tej samej reszty przy dzieleniu przez 7

W bardzo podobny sposób możemy uzasadnić, że to również jest relacja równoważności – wszystkie 3 warunki są spełnione.

Klasy równoważności

Bardzo ważną i interesującą obserwacją jest zauważenie, że relacja równoważności R dzieli zbiór A na rozłączne zbiory, które nazywamy klasami równoważności. Dla wybranego elementu a \in A definiujemy jego klasę równoważności jako zbiór wszystkich elementów ze zbioru A, które są w relacji R z tym elementem a. Za pomocą matematycznych hieroglifów można to zapisać jako:

    \[[a]_R~:=~\{b \in A~:~aRb\}\]

W powyższym zapisie element a nazywamy przedstawicielem klasy równoważności. Zwróć uwagę, że jako przedstawiciela klasy równoważności mogę wybrać dowolny element należący do tej klasy. Za chwilę sam do tego dojdziesz. Pozwól mi przestawić pewien tok rozumowania. Klasę równoważności mogę zdefiniować dla każdego elementu:

    \[[a]_R = \{x \in A~:~aRx\}\]

    \[[b]_R = \{x \in A ~:~bRx\}\]

Co otrzymamy, gdy aRb? Wtedy a\in[b]_R oraz b \in [a]_R. I po chwili zadumania nad tym faktem, możemy zauważyć, że [a]_R = [b]_R. Tak więc nie ma znaczenia, który z elementów wybierzemy na przedstawiciela klasy równoważności.

Idąc dalej, możemy zauważyć taką prawidłowość. Kiedy przecięcie zbiorów [a]_R i [b]_R będzie niepuste? Kiedy aRb. Ale wtedy to oznacza, że [a]_R=[b]_R. Co idzie dalej, że jeżeli a nie jest w relacji R z b, to wtedy [a]_R \cap [b]_R = \emptyset

Zbiór ilorazowy

Zdefiniujmy teraz dzielenie zbioru przez relację. Tak, okazuje się, że takie dzielenie jest możliwe. Co więcej, ma kilka ciekawych zastosowań. Ale o nich opowiem przy innej okazji.

Tak więc, gdy podzielimy zbiór A przez relację R to dostaniemy coś co nazywa się zbiorem ilorazowym. Będziemy go oznaczać A/R. Będzie to zbiór wszystkich klas równoważności relacji R. Czyli możemy to zapisać matematycznie:

    \[A/R ~:=~\{[a]_R~:~a \in A\}\]

Co ważne, każda klasa równoważności jest podzbiorem A (czyli [a]_R\subset A) oraz żadna klasa równoważności nie może być pusta (czyli [a]_R \neq \emptyset).

Co więcej, elementy zbioru A/R są zbiorami rozłącznymi, a ich suma mnogościowa daje w wyniku cały zbiór A. Matematycznie mówimy, że zbiór ilorazowy stanowi podział zbioru A. Podchodząc do tego tematu z drugiej strony, jeżeli mamy jakiś podział zbioru A, to ten podział definiuje jakąś relację równoważności.

Związek z Javą

Ostatnia myśl i kończę ten artykuł. Wspomniałem na początku, że dzisiejszy temat będzie związany niebezpośrednio z Javą. Teraz czas na to powiązanie. W październiku minionego roku napisałem artykuł: Porównywanie obiektów w Javie. Zdefiniowałem wtedy warunki, które musi spełniać prawidłowo napisana funkcja equals. Poznajesz teraz? Metoda equals powinna definiować relację równoważności na obiektach klasy, w której jest zdefiniowana.

Podsumowanie

Dziękuję, że doczytałeś do końca tego artykułu. Mam nadzieję, że nie czujesz się rozczarowany tematyką. Chciałbym, żebyś zauważył związek pomiędzy programowaniem a matematyką. Daj znać w komentarzu, czy podobają Ci się artykuły o tematyce matematycznej. Zachęcam do śledzenia mnie w mediach społecznościowych, bo następne artykuły pojawią się wcześniej niż myślisz!

Aspirujący twórca internetowy, który zna się na programowaniu i chce się dzielić wiedzą

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Scroll to top