Relacje

Iloczyn kartezjański to zbiór par postaci , gdzie i . Zatem wybranie podzbioru (ustanowienie relacji) polega na połączeniu w pary pewnych elementów zbioru z elementami zbioru . Jeżeli elementy i są w relacji to piszemy .

Poniższy diagram stanowi schematyczną ilustrację relacji między dwoma zbiorami skończonymi i .

Jeżeli przez oznaczymy zbiór wszystkich książek, a przez zbiór wszystkich ludzi to w zbiorze mamy relację autorstwa, która łączy w pary książkę z jej autorami. Relacja ta jest dość skomplikowana, bo książki miewają wielu autorów, a autorzy często piszą wiele książek.

Osoby interesujące się informatyką z pewnością spotkały się z pojęciem relacyjnej bazy danych. Jest to sposób na przechowywanie i organizację dużych ilości danych opierający się na tabelach, których kolumny połączone są relacjami.

Zauważmy, że zgodnie z powyższą definicją funkcja jest zbiorem par postaci .

Używając języka diagramów o funkcjach myślimy jak o relacjach, w których z każdego elementu zbioru wychodzi dokładnie jedna strzałka.

Relacja przedstawiona na lewym diagramie nie jest funkcją, bo są elementy, z których nie wychodzi żadna strzałka oraz takie, z których wychodzi więcej niż jedna strzałka. Relacja z prawego diagramu jest funkcją.

Wybranie podzbioru oznacza ustanowienie relacji (związku) pomiędzy niektórymi elementami zbioru . Dokładniej, jeżeli .

Dobrze znacie kilka relacji w zbiorze . Np.: .
W tym przypadku relacje są podzbiorem zbioru , czyli płaszczyzny. Możemy więc rysować wykresy relacji: zaznaczamy w układzie współrzędnych wszystkie punkty, z których składa się relacja.

Na lewym diagramie naszkicowaliśmy wykres relacji „”, a na prawym wykres relacji „”.

W zbiorze wszystkich ludzi mamy relację znajomości: osoba jest w relacji z jeżeli zna .

W zbiorze liczb naturalnych jest bardzo ważna relacja podzielności „”, tzn. wtedy i tylko wtedy, gdy dzieli .

W zbiorze prostych na płaszczyźnie mamy relacje „” i „”.

W zbiorze wszystkich trójkątów na płaszczyźnie mamy relacje przystawania oraz podobieństwa.

Relacje „” i „” są zwrotne, przechodnie i słabo antysymetryczne.

Relacja „” prostopadłości prostych na płaszczyźnie jest symetryczna.

Relację będącą częściowym porządkiem często oznacza się symbolem „”. Warunki definiujące częściowy porządek wyglądają wtedy bardzo naturalnie: dla dowolnych

Relacja „” jest częściowym porządkiem w zbiorze oraz w każdym jego podzbiorze.

W zbiorze składającym się ze wszystkich podzbiorów zbioru relacją częściowego porządku jest inkluzja „”.

Spróbujmy się zastanowić jak porównywać ze sobą punkty płaszczyzny.
Pierwszą naiwną próbą mogłoby być porównywanie drugich współrzędnych, czyli relacja jeżeli . Jak łatwo sprawdzić (zróbcie to!) relacja ta nie jest jednak antysymetryczna, więc nie jest to częściowy porządek.
Mówiąc poglądowo, relacja ta jest zła, bo jest mnóstwo punktów, które z punktu widzenia tej nierówności są równe (punkty leżące na poziomych prostych).

Jeszcze jedno podejście do uporządkowania płaszczyzny: zamiast porównywać drugie współrzędne, porównujmy obie współrzędne na raz, tzn. przyjmijmy jeżeli jednocześnie i . Łatwo sprawdzić, że jest to relacja częściowego porządku.

Relacja inkluzji jest częściowym porządkiem, ale nie jest liniowym porządkiem, bo np. nie można przy jej pomocy porównać zbiorów i .

Zwykła nierówność „” jest liniowym porządkiem w zbiorze .

Widzieliśmy już, że nierówność na płaszczyźnie zdefiniowana warunkiem

jest częściowym porządkiem. Nie jest to jednak linowy porządek, bo przy jego pomocy nie da się porównać np. punktów i .

Czy na płaszczyźnie da się wprowadzić liniowy porządek? Tak, jest to np. porządek leksykograficzny zdefiniowany warunkiem

(porównujemy przede wszystkim pierwsze współrzędne, a tylko gdy są równe patrzymy na drugie). Oczywiście właśnie w ten sposób szukacie haseł w słowniku.

Tak jak relacja częściowego porządku stanowi uogólnienie nierówności, relacja równoważności stanowi uogólnienie równości. Różnicę między tymi dwoma pojęciami widać w definicji: mamy symetrię zamiast antysymetrii.

Relacja równoległości prostych na płaszczyźnie jest relacją równoważności.

Relacje przystawania i podobieństwa są relacjami równoważności.

Relacja równoważności ma działać jak uogólnienie równości, tzn. obiekty równoważne mają być „takie same z jakiegoś punktu widzenia”. Tak jest w podanych wyżej przykładach: w przypadku równoległości prostych relacja ustala równoważność prostych, które mają ten sam kierunek, a w przypadku podobieństwa trójkątów relacja utożsamia trójkąty, które są podobne. Przy takim rozumieniu równoważności podane wymagania, czyli zwrotność, symetria i przechodniość są dość naturalne.

O zbiorze myślimy jak o zbiorze mniejszym od . Tak jest, bo tworząc sklejamy wszystkie elementy zbioru będące w relacji w jeden element zbioru .

Powyższy schematyczny rysunek przedstawia zbiór podzielony na 6 klas abstrakcji pewnej relacji równoważności „”. W takiej sytuacji zbiór składa się z sześciu elementów.

Relacja „ten sam wzrost w cm” jest relacją równoważności w zbiorze wszystkich ludzi. Podobne relacje to np. „ten sam kolor oczu”, „wspólny pradziadek”, „to samo pierwsze imię”, „ten sam dzień urodzenia”. Każda z tych relacji dokonuje podziału zbioru wszystkich ludzi na klasy abstrakcji ze względu na interesującą nas cechę.

Jeżeli „” jest relacją „” równoległości prostych na płaszczyźnie, to zbiory elementów będących w relacji (czyli klasy abstrakcji tej relacji) to po prostu zbiory prostych, które są wzajemnie równoległe. Zbiorów tych jest tyle, ile możliwych kierunków na płaszczyźnie. Dlatego o zbiorze myślimy jak o zbiorze kierunków.

Spróbujmy na poprzedni przykład popatrzeć z drugiej strony. Zastanówmy się co to jest kierunek prostej? Trudno powiedzieć, co to dokładnie jest, ale wiemy, że niektóre proste mają ten sam kierunek, np. , , . I taki właśnie jest pomysł na definicję kierunku: jeden kierunek to coś, co mają wspólnego ze sobą proste , , i wszystkie inne o współczynniku kierunkowym , inny kierunek to coś, co mają ze sobą wspólnego wszystkie proste o współczynniku itd. Jeżeli teraz popatrzycie na opis zbioru powyżej to powinno być jasne, że jest to sposób na precyzyjną definicję zbioru kierunków na płaszczyźnie.
Przykład ten jest dość abstrakcyjny, ale dokładnie taka jest rola relacji równoważności i klas abstrakcji: pozwalają one precyzyjnie definiować abstrakcyjne pojęcia (kierunek w tym przypadku).

Jeżeli jest zbiorem trójkątów na płaszczyźnie, a „” relacją podobieństwa, to jak wyobrazić sobie zbiór ? Tworząc zbiór utożsamiamy ze sobą wszystkie trójkąty podobne, więc o zbiorze możemy myśleć jak o zbiorze wszystkich możliwych kształtów trójkątów. Np. trójkątowi równobocznemu odpowiada dokładnie jeden element zbioru pomimo, że w zbiorze (na płaszczyźnie) jest nieskończenie wiele trójkątów równobocznych.
Gdybyśmy zamiast podobieństwa wzięli relację przystawania, to zbiór byłby zbiorem wszystkich możliwych kształtów z uwzględnieniem rozmiaru.

Ustalmy liczbę naturalną . W zbiorze liczb całkowitych wprowadzamy relację „” wzorem

Mówiąc po ludzku: dwie liczby są w relacji wtedy i tylko wtedy, gdy dają tę samą resztę z dzielenia przez . Zbiór składa się elementów, które możemy wypisać:

Zbiór oznaczamy symbolem i jest to zbiór reszt z dzielenia przez .

Jeżeli przejrzycie swoje podręczniki do matematyki to okaże się, że nie znajdziecie w nich definicji liczb wymiernych. Tak jest, bo definicja ta wymaga użycia relacji równoważności. Mówiąc dokładniej, liczb wymiernych nie można zdefiniować jako napisów postaci , gdzie , bo przecież każda liczba wymierna może być w ten sposób napisana na nieskończenie wiele różnych sposobów. Np. czym jest ? Napisem ? A może jednym z napisów

Problem w tym przypadku jest podobny jak z definicją kierunku na płaszczyźnie: to co chcemy zdefiniować jest abstrakcyjne: ma to być „połowa całości”, a nie ten czy inny napis. Jak w takim razie zdefiniować połowę? – skoro jest to cecha wspólna wszystkich powyższych ułamków, to definiujemy jako wszystkie te ułamki na raz.
Mówiąc bardziej precyzyjnie, w zbiorze napisów postaci , gdzie (jeżeli ktoś się zastanawia co to jest „zbiór napisów”, to jest to zbiór par pisanych w taki oryginalny sposób) wprowadzamy relację „” w następujący sposób: napisy i są w relacji „” wtedy i tylko wtedy, gdy (jest to znany nam dobrze warunek równości ułamków). Można teraz sprawdzić, że „” jest relacją równoważności oraz z definicji .

Jeżeli „” jest relacją równoległości prostych na płaszczyźnie to klasa oznacza zbiór wszystkich prostych na płaszczyźnie ze współczynnikiem kierunkowym . Oczywiście ten sam zbiór możemy zapisać na wiele różnych sposobów, np.

Każda z prostych , , jest reprezentantem powyższej klasy abstrakcji (kierunku).

Definiując liczby wymierne zdefiniowaliśmy „połowę” jako zbiór wszystkich ułamków postaci

Formalnie „połowę” powinniśmy więc oznaczać jednym z symboli: , . Tak jednak nie robimy i piszemy krótko Zapis należy więc rozumieć jako skrót zapisu .
W pewnym sensie jest to duże osiągnięcie matematyki, że możemy posługiwać się symbolami ułamków nie wiedząc nawet co one oznaczają. .

Formalnie zbiór składa się z trzech elementów

Napisy są jednak niewygodne, więc wolelibyśmy pisać po prostu . Jest z tym jednak kłopot, bo np. napis (który oznacza po prostu, że obie liczby dają tę samą resztę z dzielenia przez 3) zamienia się na , co nie wygląda zbyt dobrze. Z tego powodu używa się specjalnej notacji: zamiast piszemy

(czytamy przystaje do 7 modulo 3). Czasami pisze się też krótko .