Rodzaje relacji heterogenicznych

Relacje lewo- i prawostronnie unikalne

Dwoma podstawowymi rodzajami relacji są relacje unikalne z lewej i prawej strony. Relacja lewostronnie unikalna to taka, dla której każde b : B jest w relacji z co najwyżej jednym a : A. Analogicznie definiujemy relację prawostronnie unikalną.

Najbardziej elementarną intuicję stojącą za tymi koncepcjami można przedstawić na przykładzie relacji równości: jeżeli dwa obiekty są równe jakiemuś trzeciemu obiektowi, to muszą być także równe sobie nawzajem. Pojęcie to jest jednak bardziej ogólne i dotyczy także relacji, które nie są homogeniczne. W szczególności jest ono różne od pojęcia relacji przechodniej, które pojawi się już niedługo.

Składanie zachowuje oba rodzaje relacji unikalnych. Nie ma tu co za dużo filozofować — żeby się przekonać, narysuj obrazek. TODO.

Już na pierwszy rzut oka widać, że pojęcia te są w pewien sposób symetryczne. Aby uchwycić tę symetrię, możemy posłużyć się operacją Rinv. Okazuje się, że zamiana miejscami argumentów relacji lewostronnie unikalnej daje relację prawostronnie unikalną i vice versa.

Koniunkcja relacji unikalnej z inną daje relację unikalną, ale dysjunkcja nawet dwóch relacji unikalnych nie musi dawać w wyniku relacji unikalnej. Wynika to z interpretacji operacji na relacjach jako operacji na kolekcjach par. Wyobraźmy sobie, że relacja R : hrel A B to kolekcja par p : A * B. Jeżeli para jest elementem kolekcji, to jej pierwszy komponent jest w relacji R z jej drugim komponentem. Dysjunkcję relacji R i S w takim układzie stanowi kolekcja, która zawiera zarówno pary z kolekcji odpowiadającej R, jak i te z kolekcji odpowiadającej S. Koniunkcja odpowiada kolekcji par, które są zarówno w kolekcji odpowiadającej R, jak i tej odpowiadającej S. Tak więc dysjunkcja R i S może do R "dorzucić" jakieś pary, ale nie może ich zabrać. Analogicznie, koniunkcja R i S może zabrać pary z R, ale nie może ich dodać. Teraz interpretacja naszego wyniku jest prosta. W przypadku relacji lewostronnie unikalnych jeżeli każde b : B jest w relacji z co najwyżej jednym a : A, to potencjalne zabranie jakichś par z tej relacji niczego nie zmieni. Z drugiej strony, nawet jeżeli obie relacje są lewostronnie unikalne, to dodanie do R par z S może spowodować wystąpienie powtórzeń, co niszczy unikalność.

Negacja relacji unikalnej również nie musi być unikalna. Spróbuj podać interpretację tego wyniku z punktu widzenia operacji na kolekcjach par.

Ćwiczenie

Znajdź przykład relacji, która:

• nie jest unikalna ani lewostronnie, ani prawostronnie
• jest unikalna lewostronnie, ale nie prawostronnie
• jest unikalna prawostronnie, ale nie nie lewostronnie
• jest obustronnie unikalna

Relacje lewo- i prawostronnie totalne

Kolejnymi dwoma rodzajami heterogenicznych relacji binarnych są relacje lewo- i prawostronnie totalne. Relacja lewostronnie totalna to taka, że każde a : A jest w relacji z jakimś elementem B. Definicja relacji prawostronnie totalnej jest analogiczna. Za pojęciem tym nie stoją jakieś wielkie intuicje: relacja lewostronnie totalna to po prostu taka, w której żaden element a : A nie jest "osamotniony".

TODO

TODO

Równość jest relacją totalną, gdyż każdy term x : A jest równy samemu sobie.

Między lewo- i prawostronną totalnością występuje podobna symetria jak między dwoma formami unikalności: relacja odwrotna do lewostronnie totalnej jest prawostronnie totalna i vice versa. Totalność jest również zachowywana przez składanie.

Negacja relacji totalnej nie może być totalna. Nie ma się co dziwić — negacja wyrzuca z relacji wszystkie pary, których w niej nie było, a więc pozbywa się czynnika odpowiedzialnego za totalność.

Związki totalności z koniunkcją i dysjunkcją relacji są podobne jak w przypadku unikalności, lecz tym razem to dysjunkcja zachowuje właściwość, a koniunkcja ją niszczy. Wynika to z tego, że dysjunkcja nie zabiera żadnych par z relacji, więc nie może uszkodzić totalności. Z drugiej strony koniunkcja może zabrać jakąś parę, a wtedy relacja przestaje być totalna.

Ćwiczenie

Znajdź przykład relacji, która:

• nie jest totalna ani lewostronnie, ani prawostronnie
• jest totalna lewostronnie, ale nie prawostronnie
• jest totalna prawostronnie, ale nie nie lewostronnie
• jest obustronnie totalna

Bonusowe punkty za relację, która jest "naturalna", tzn. nie została wymyślona na chama specjalnie na potrzeby zadania.

Rodzaje relacji heterogenicznych v2

Poznawszy cztery właściwości, jakie relacje mogą posiadać, rozważymy teraz relacje, które posiadają dwie lub więcej z tych właściwości.

Relacje funkcyjne

Lewostronną totalność i prawostronną unikalność możemy połączyć, by uzyskać pojęcie relacji funkcyjnej. Relacja funkcyjna to relacja, która ma właściwości takie, jak funkcje — każdy lewostronny argument a : A jest w relacji z dokładnie jednym b : B po prawej stronie.

Z każdej funkcji można w prosty sposób zrobić relację funkcyjną, ale bez dodatkowych aksjomatów nie jesteśmy w stanie z relacji funkcyjnej zrobić funkcji. Przemilczając kwestie aksjomatów możemy powiedzieć więc, że relacje funkcyjne odpowiadają funkcjom.

Równość jest rzecz jasna relacją funkcyjną. Funkcją odpowiadającą relacji @eq A jest funkcja identycznościowa @id A.

Złożenie relacji funkcyjnych również jest relacją funkcyjną. Nie powinno nas to dziwić — wszakże relacje funkcyjne odpowiadają funkcjom, a złożenie funkcji jest przecież funkcją. Jeżeli lepiej mu się przyjrzeć, to okazuje się, że składanie funkcji odpowiada składaniu relacji, a stąd już prosta droga do wniosku, że złożenie relacji funkcyjnych jest relacją funkcyjną.

Odwrotność relacji funkcyjnej nie musi być funkcyjna. Dobrą wizualicją tego faktu może być np. funkcja f(x) = x^2 na liczbach rzeczywistych. Z pewnością jest to funkcja, a zatem relacja funkcyjna. Widać to na jej wykresie — każdemu punktowi dziedziny odpowiada dokładnie jeden punkt przeciwdziedziny. Jednak po wykonaniu operacji Rinv, której odpowiada tutaj obrócenie układu współrzędnych o 90 stopni, nie otrzymujemy wcale wykresu funkcji. Wprost przeciwnie — niektórym punktom z osi X na takim wykresie odpowiadają dwa punkty na osi Y (np. punktowi 4 odpowiadają 2 i -2). Stąd wnioskujemy, że odwrócenie relacji funkcyjnej f nie daje w wyniku relacji funkcyjnej.

Ani koniunkcje, ani dysjunkcje, ani negacje relacji funkcyjnych nie muszą być wcale relacjami funkcyjnymi. Jest to po części konsekwencją właściwości relacji lewostronnie totalnych i prawostronnie unikalnych: pierwsze mają problem z Rand, a drugie z Ror, oba zaś z Rnot.

Ćwiczenie

Możesz zadawać sobie pytanie: po co nam w ogóle pojęcie relacji funkcyjnej, skoro mamy funkcje? Funkcje muszą być obliczalne (ang. computable) i to na mocy definicji, zaś relacje — niekonieczne. Czasem prościej może być najpierw zdefiniować relację, a dopiero później pokazać, że jest funkcyjna. Czasem zdefiniowanie danego bytu jako funkcji może być niemożliwe. Funkcję Collatza klasycznie definiuje się w ten sposób: jeżeli n jest parzyste, to f(n) = n/2. W przeciwnym przypadku f(n) = 3n + 1. Zaimplementuj tę funkcję w Coqu. Spróbuj zaimplementować ją zarówno jako funkcję rekurencyjną, jak i relację. Czy twoja funkcja dokładnie odpowiada powyższej specyfikacji? Czy jesteś w stanie pokazać, że twoja relacja jest funkcyjna? Udowodnij, że f(42) = 1.

Relacje injektywne

Relacje funkcyjne, które są lewostronnie unikalne, odpowiadają funkcjom injektywnym.

Właściwości relacji injektywnych są takie, jak funkcji injektywnych, gdyż te pojęcia ściśle sobie odpowiadają.

Ćwiczenie

Udowodnij, że powyższe zdanie nie kłamie.

Relacje surjektywne

Relacje funkcyjne, które są prawostronnie totalne, odpowiadają funkcjom surjektywnym.

Właściwości relacji surjektywnych także są podobne do tych, jakie są udziałem relacji funkcyjnych.

Relacje bijektywne

Relacje funkcyjne, które są lewostronnie totalne (czyli injektywne) oraz prawostronnie totalne (czyli surjektywne), odpowiadają bijekcjom.

Właściwości relacji bijektywnych różnią się jednym szalenie istotnym detalem od właściwości relacji funkcyjnych, injektywnych i surjektywnych: odwrotność relacji bijektywnej jest relacją bijektywną.

Nieco więcej o relacjach funkcyjnych (TODO)

Pojęcie relacji funkcyjnej jest dość zwodnicze, więc pochylimy się nad nim nieco dłużej.

Relacje funkcyjne a aksjomat wyboru (TODO)

Tutaj zademonstrować różnicę między Functional a poniższym tworem:

Relacje funkcyjne a funkcje (TODO)

Tutaj powtórka historyjki z rozdziału o rozstrzygalności. Dowiedzieliśmy się tam, że fakt, że zdanie jest określone, nie oznacza jeszcze, że jest ono rozstrzygalne. Zdanie jest określone, gdy zachodzi dla niego wyłączony środek, zaś rozstrzygalne, gdy istnieje program, który sprawdza, która z tych dwóch możliwości zachodzi. Podobna sytuacja ma miejsce dla przeróżnych porządków: to, że relacja jest np. trychotomiczna, nie znaczy jeszcze, że potrafimy napisać program, który sprawdza, który z argumentów jest większy. Z relacjami funkcyjnymi jest podobnie: to, że relacja jest funkcyjna, nie znaczy od razu, że potrafimy znaleźć funkcję, której jest ona wykresem.

Relacje wykresowe (TODO)

Zależności między różnymi rodzajami relacji