Relacja dwuargumentowa

Relacja dwuargumentowa (binarna) to szczególny rodzaj relacji o arności dwa. Do typowych relacji dwuargumentowych należą na przykład mniejszy niż, równość, podzielność, większy niż itp.

Przykłady

Relacja dwuargumentowa to jedna z typowych i często spotykanych relacji. Ma przy tym kilka ciekawych własności, które tu opiszemy.

Przykładem relacji dwuargumentowej może być: związek „ojciec — syn”, para „środek transportu — liczba kół” albo ogólniejsza „obiekt — własność obiektu”. Obiektem może być zwierzę, a własnością liczba nóg, średnia długość życia, liczba włosów na głowie i tym podobne.

Relację dwuargumentową R między zbiorami M₁ i M₂ możemy zdefiniować tak: R ⊆ M₁ × M₂. Relacja dwuargumentowa jest więc zbiorem par, przy czym ten zbiór jest podzbiorem iloczynu kartezjańskiego dwóch zbiorów, między którymi relację wprowadzamy. Relacja „ojciec — syn” może więc być relacją między zbiorami wszystkich ludzi, między zbiorami wszystkich ludzi w Europie albo w Warszawie. Zbiór możemy ograniczyć także w inną stronę, możemy powiedzieć, że tę relację definiujemy między zbiorami wszystkich mężczyzn, a nie ludzi w ogóle.

Dla relacji dwuargumentowych zwykle używamy specjalnego zapisu. Zamiast pisać (a, b) ∈ R, możemy napisać aRb. Na przykład zamiast (3, 1) ∈ > możemy napisać 3 > 1. Podobnie dla innych relacji. Zapis aSb jest więc równoważny zapisowi (a, b) ∈ S.

Relacja odwrotna

Relacja odwrotna to relacja „obrócona” w stosunku do danej relacji. (Uwaga, nie mylić z dopełnieniem relacji.) Jaka relacja jest odwrotna do relacji mniejszy niż? Większy niż. Jeśli relacja mniejszy niż zawiera element (4, 7), czyli 4 < 7, to po odwróceniu dostaniemy 7 > 4, a w relacji odwrotnej będzie odwrócona para (7, 4).

Jeśli mamy relację R ⊆ M₁ × M₂, to relację odwrotną R⁻¹ zbudujemy tak, że weźmiemy wszystkie elementy (a, b) ∈ R i do R⁻¹ włożymy ich odwrócenia. Czyli jeśli relacja R zawiera element (a, b), to relacja R⁻¹ musi zawierać element (b, a). Zachodzi to także odwrotnie: jeśli R⁻¹ zawiera element (b, a), to relacja R musi zawierać element (a, b).

Formalnie: relacja R⁻¹ jest odwrotna do R wtedy i tylko wtedy, gdy zachodzi:

$$\forall a\in M_1,\forall b\in M_2:\quad (a, b)\in R \Leftrightarrow (b, a)\in R^{-1}$$

Zachodzi więc, że 6 < 8 wtedy i tylko wtedy, gdy 8 > 6. Podobnie dla innych par.

Składanie relacji

Relacje dwuargumentowe możemy ze sobą składać. Weźmy dwie relacje: pierwsza, R, będzie „być ojcem swojego syna”, a druga, S, „być bratem swojej siostry”. Relacja R zawiera więc pary (ojciec, syn), druga relacja zawiera pary (brat, siostra).

Teraz spróbujemy relacje złożyć. Powstanie nam nowa relacja, oznaczymy ją $R \circ S$, przy czym ta relacja zawiera element (a, c) wtedy i tylko wtedy, gdy (a, b) ∈ R i jednocześnie (b, c) ∈ S. Zauważ, że w obu elementach występuje b, raz na drugim, a potem na pierwszym miejscu pary. To taki element łączący przy składaniu.

Przykład: R = {(Antek, Marek), (Piotr, Jakub)} i S = {(Marek, Jana), (Marek, Lena), (Jakub, Łucja)}. Antek jest ojcem Marka, Piotr jest ojcem Jakuba. Marek ma siostry Janę i Lenę, a Jakub ma siostrę Łucję.

Teraz złożymy relacje: $R \circ S$. Szukamy takiej pary z R, która na miejscu syna ma kogoś, kto występuje jako brat w relacji S. Na przykład te dwie pary: (Antek, Marek) i (Marek, Jana). Marek jest elementem łączącym, nie jest nam dalej potrzebny, a z pozostałych imion utworzymy nową parę: (Antek, Jana). Relacja $R \circ S$ zawiera więc parę (Antek, Jana). Marek ma jeszcze jedną siostrę, Lenę, ją też dodamy do złożonej relacji: (Antek, Lena). Na koniec zostaje syn Jakub. Ma on siostrę Łucję. Mamy więc dwie pary: (Piotr, Jakub) i (Jakub, Łucja). W ten sposób utworzymy kolejny element: (Piotr, Łucja).

Wynikiem jest relacja: $R \circ S = {(Antek, Jana), (Antek, Lena), (Piotr, Łucja)}$. Jak moglibyśmy nazwać tę relację? Najpewniej „być ojcem swojej córki”.

Jeszcze raz cała definicja:

$$(a, c) \in (R \circ S) \Leftrightarrow \exists b\quad (a, b) \in R \wedge (b, c) \in S$$

Uwaga: czasem używa się odwrotnego zapisu, to znaczy, że przy tej samej definicji zamiast $R \circ S$ użyłoby się $S \circ R$.