Wstęp
Wiedząc już czym są relacje w ogólności, zajmijmy się dosyć ciekawym i o wiele bardziej eksploatowanym tematem, a mianowicie, relacjach binarnych.
Do dzieła więc!
Wtrącenie pojęciowe
Czasami zdarzy mi się użyć pojęcia, relacja określona/opisana na zbiorach/zbiorze. Pojęcie to będzie oznaczać, że owa relacja, jest podzbiorem iloczynu właśnie tych zbiorów, które tutaj wymienię, np. relacja \(R\) określona na \(A\) i \(B\), będzie oznaczała, że mam na myśli relację \(R \subseteq A \times B\), natomiast jeżeli powiem że relacja \(R\) określona na \(A\), to znaczy że jej dziedzinami jest zbiór \(A\), czyli będę miał na myśli relację \(R \subseteq A \times A\).
Rozwinięcie
Definicja.
A więc od początku. Relacją binarną/dwuargumentową nazywać będziemy zbiór par uporządkowanych. Formalnie będzie to wyglądać tak:
\(R \subseteq A \times B\)
Dziedziny.
Taka relacja, jako że jest zbiorem par uporządkowanych, będzie miała dwie dziedziny. Dziedziny te jednak będą miały swoje nazwy. Dziedzina pierwsza, będzie nazywana po prostu dziedziną, a dziedzina druga, będzie nazywana przeciwdziedziną. Usłyszeć też można czasami o dziedzinie lewo i prawostronnej, i jest to dokładnie to o czym myślimy, czyli dziedzina z lewej i prawej naszej pary uporządkowanej.
Często używa się angielskich odpowiedników, nawet w polskiej literaturze. Przetłumaczymy wtedy dziedzinę na domain, i zapiszemy:
\(dom(R)\)
A przeciwdziedzinę, przetłumaczymy na range, i zapiszemy:
\(rng(R)\)
Związki.
Jako że teraz jesteśmy mocno ograniczeni tym, że mamy tylko pary, możemy wprowadzić jeden fajny symbol. Będzie to symbol relacji dwóch elementów. Będzie to symbol jakim nazwaliśmy relację, np. litera \(R\) i otoczona będzie dwoma elementami, z lewej elementem dziedziny, a z prawej przeciwdziedziny. Oto jak się prezentuje:
\(a R b\)
Mówić będziemy wtedy, że element \(a\) jest w relacji \(R\) z \(b\).
Jako że jesteśmy już w parze, możemy nawiązać do pytania z poprzedniego artykułu, czy relacje matematyczne, mają coś wspólnego z relacjami, jakie mamy na co dzień, bo mając pary, jest to jeszcze bardziej intuicyjne.
Relacje, jak już powiedzieliśmy, w ogólności reprezentują zbiory \(n\)-tek uporządkowanych, ale definiuje się je często, właśnie żeby zdefiniować jakiś związek pomiędzy elementami. Tak np. mając relację binarną: \(R = \{(1, 2), (2, 3), (9, 0)\}\), która nie reprezentuje niczego konkretnego, zrobimy z nią nic, natomiast mając relację \(R = \{(1, 2), (1, 3), (1, 4)\}\), możemy powiedzieć, że zdefiniowaliśmy związek liczby \(1\), z liczbami większymi od niej w naszym ograniczonym zakresie. Możemy teraz na podstawie tej relacji powiedzieć, że \(2\) jest większe niż \(1\), albo że \(1\) jest w relacji mniejszości z \(2\). Relacja mniejszości jest pojęciem ścisłym, na razie jednak, by nie biegać po tematach, bez większych wyjaśnień weźmiemy je sobie na intuicję.
Obraz i przeciwobraz
Czasami zdarza się, że w naszych analizach, nie będziemy chcieli rozpatrywać całych relacji. Z różnych powodów, np. z powodu rozmiarów, lub małego znaczenia pewnych części owych relacji w naszych rozważanych przypadkach, dlatego czasami możemy na nie spojrzeć w inny sposób.
To owe spojrzenie sprowadzi się do ograniczenia jednej z dziedzin, lewej bądź prawej.
Obraz
W pierwszym przypadku, gdy ograniczymy dziedzinę naszej relacji do jakiegoś podzbioru, to wszystkie elementy przeciwdziedziny, które znajdą się w parach, które wpasują się w owe ograniczenie, nazwiemy obrazem relacji. Jednak nie musimy ograniczać absolutnie nic, żeby obraz relacji istniał, bowiem możemy powiedzieć, że cała dziedzina, jest jej podzbiorem, niewłaściwym, ale podzbiorem. Dlatego, gdy w żaden sposób nie ograniczymy dziedziny, jej obrazem będzie jej pełna przeciwdziedzina.
Pokażmy na przykładzie. Mając relację \(R = \{(1, 2), (2, 3), (3, 4), (4, 5)\}\), jej obrazem będzie \(\set{2, 3, 4, 5}\), natomiast, gdy dziedzinę ograniczymy do zbioru \(\set{1, 2}\), to jej obraz zmieni się na \(\set{2, 3}\).
Próbując sformalizować zapis, najpierw określmy sobie owe ograniczenie. Nazwijmy je \(A\) i określmy jako \(A \subseteq dom(R)\). Teraz pisząc formalnie, możemy napisać:
\(R[A] = \set{b \text{ takich że istnieje } (a, b) \in R \text{ gdzie } a \in A \text{ i } b \in rng(R)}\)
Gdzie \(R[A]\) będzie właśnie oznaczać obraz relacji, a ten zapis odczytamy, mówiąc że \(R[A]\) jest obrazem zbioru \(A\) w relacji \(R\).
Nie jest to oczywiście jedyna forma zapisu, można jeszcze użyć nawiasów okrągłych i napisać;
\(R(A)\)
I będzie to oznaczało dokładnie to samo.
Dodatkowo, jeżeli nasze \(A\), czyli ograniczenie dziedziny, nie będzie ograniczeniem, a będzie równać się dziedzinie, będzie można napisać z angielskiego image:
\(\operatorname{Im}(R)\)
I powiemy że \(\operatorname{Im}(R)\) jest obrazem relacji. Jednak jeżeli \(A = dom(R)\), to zapis \(R(A)\), tez będzie można nazwać obrazem relacji lub pełnym obrazem. Słowo image po prostu jest bardziej obrazowe (nomen omen).
Przeciwobraz
W drugim przypadku, gdy ograniczymy przeciwdziedzinę naszej relacji do jakiegoś podzbioru, to wszystkie elementy dziedziny, które znajdą się w parach, które wpasują się w owe ograniczenie, nazwiemy przeciwobrazem relacji. I dokładnie jak w przypadku obrazu, nie trzeba wprowadzać ograniczeń, żeby przeciwobraz istniał, dokładnie z tego samego powodu, jak w przypadku obrazu, tylko w odniesieniu do przeciwdziedziny.
Pokażmy na przykładzie. Mając relację \(R = \{(1, 2), (2, 3), (3, 4), (4, 5)\}\), jej przeciwobrazem będzie \(\set{1, 2, 3, 4}\), natomiast, gdy przeciwdziedzinę ograniczymy do zbioru \(\set{4, 5}\), to jej obraz zmieni się na \(\set{3, 4}\)
Próbując sformalizować zapis, najpierw określmy sobie owe ograniczenie. Nazwijmy je \(A\) i określmy jako \(B \subseteq rng(R)\). Teraz pisząc formalnie, możemy napisać:
\(R^{-1}[B] = \set{a \text{ takich że istnieje } (a, b) \in R \text{ gdzie } b \in B \text{ i } a \in dom(R)}\)
Gdzie \(R^{-1}[B]\) będzie właśnie oznaczać przeciwobraz relacji, a ten zapis odczytamy, mówiąc że \(R^{-1}[B]\) jest przeciwobrazem zbioru \(B\) w relacji \(R\). W tym przypadku dokładnie jak w przypadku obrazu, notacja z nawiasami okrągłymi też jest poprawna, czyli zapisując;
\(R^{-1}(B)\)
Też oznaczymy przeciwobraz.
Mając w pamięci angielski image i jego oznaczenie w obrazie, niestety tutaj nie spotkałem się z odpowiednikiem. Dlatego tutaj angielskiego odpowiednika i oznaczenie, nie będzie. Nie mniej, jeżeli nasze \(B = rng(R)\), to \(R^{-1}(B)\) będziemy mogli nazwać przeciwobrazem relacji, lub pełnym przeciwobrazem.
Złożenie.
Jedną z ciekawszych operacji jakich możemy dokonywać na relacjach binarnych, jest ich składanie.
Polega ona na połączeniu przeciwdziedziny pierwszej relacji, z dziedziną drugiej, po czym na odszukaniu par par, które połączy właśnie ta połączona dziedzina i przeciwdziedzina.
Może brzmieć trochę dziwnie, ale za moment się rozjaśni.
Podejście pierwsze.
Na początku, weźmy formalną definicję i spróbujmy ją rozwikłać. Brzmi ona tak:
\(\text{niech } R \subseteq A \times B \\ \text{oraz } \space \space S \subseteq C \times D \\ \text{wtedy:} \\ S \circ R = \{ (a, d) \subseteq A \times D \space \text{takie że istnieje takie} \space y \in B \cap C \space \text{że} \space (a, y) \in R \space \text{oraz} \space (y, d) \in S \}\)
Od początku.
Definiujemy dwie relacje, w tym przypadku \(R\) i \(S\), które są kolejno podzbiorami iloczynów kartezjańskich zbiorów \(A\) i \(B\) oraz \(C\) i \(D\).
Teraz.
Złożeniem relacji nazwiemy pary, które będą niejako połączeniem tych dwóch relacji, poprzez złączenie przeciwdziedziny relacji \(R\) i dziedziny relacji \(S\).
Na czym to będzie polegać?
Ano na tym, żeby wyszukać takie pary par uporządkowanych, po jednej z każdej relacji osobno, że będą one miały wspólny element owego połączenia, a tym wspólnym elementem będzie element przeciwdziedziny pary z relacji \(R\) i element dziedziny pary z relacji \(S\).
Mówiąc jeszcze inaczej, szukamy takich par par uporządkowanych, po jednej z każdej relacji osobno, że gdy ustawimy je obok siebie, to będą się "stykać" takim samym elementem, np: \((1, 2)(2, 1)\).
Teraz bierzemy pierwszy element z pary, którą znaleźliśmy w \(R\), oraz drugi z pary którą znaleźliśmy w \(S\) i tworzymy z nich parę.
Wszystkie utworzone w ten sposób pary, stworzą nam złożenie relacji.
Można sobie zadać pytanie, po co więc w definicji fragment o \(y \in B \cap C \space\)? Ano po to, żeby uściślić, że zbiór tego element styku, będzie właśnie połączeniem przeciwdziedziny pierwszej i dziedziny drugiej relacji. Trzeba to dodać, bo tak w toku rozumowania tego jak owo złożenie wykonać, naturalnie wyjdzie nam, że owe elementy połączeń właśnie w takim zbiorze się znajdą, bo skoro się stykają jakimś elementem, to musi się on znajdować i tu (przeciwdziedzina pierwszej relacji) i tu (dziedzina drugiej).
Nie definiując żadnych zbiorów, tylko operując na dowolnych relacjach, można utworzyć krótszą definicję, która zabrzmi tak:
\(S \circ R = \set{(r_1, s_2) \text{ takich że istnieje } (r_1, y) \text{ oraz } (y, s_2) \text{ gdzie } y \in dom(R) \cap rng(S) }\)
Gdzie małe litery \(r\) i \(s\), są elementami ich dużych odpowiedników, czyli \(S\) i \(R\), a indeksy dolne przy nich oznaczają, którą dziedzinę bierzemy.
Cudownie proste.
Przykład.
Spróbujmy więc z przykładem. Zdefiniujmy sobie \(4\) zbiory. A więc:
\(A = \set{1, 2, 3} \\ B = \set{2, 3, 4} \\ C = \set{2, 3} \\ D = \set{1, 5, 6}\)
Teraz na ich kanwie, utwórzmy relacje:
\(R \subseteq A\times B \subseteq \set{(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} \\ S \subseteq C\times D \subseteq \set{(2, 1), (2, 5), (2, 6), (3, 1), (3, 5), (3, 6)}\)
"Wspólną dziedziną", czyli \(B \times C\) będzie:
\(B \times C = \set{2, 3}\)
A teraz po kolei, bierzemy każdą parę z relacji \(R\) i próbujemy połączyć z każdym elementem relacji \(S\):
- \((1, 2)\) pasuje do:
- \((2, 1)\) tworząc \((1, 1)\)
- \((2, 5)\) tworząc \((1, 5)\)
- \((2, 6)\) tworząc \((1, 6)\)
- \((1, 3)\) pasuje do:
- \((3, 1)\) tworząc \((1, 1)\)
- \((3, 5)\) tworząc \((1, 5)\)
- \((3, 6)\) tworząc \((1, 6)\)
- \((1, 4)\) nie pasuje do żadnego elementu z \(S\)
- \((2, 2)\) pasuje do:
- \((2, 1)\) tworząc \((2, 1)\)
- \((2, 5)\) tworząc \((2, 5)\)
- \((2, 6)\) tworząc \((2, 6)\)
- \((2, 3)\) pasuje do:
- \((3, 1)\) tworząc \((2, 1)\)
- \((3, 5)\) tworząc \((2, 5)\)
- \((3, 6)\) tworząc \((2, 6)\)
- \((2, 4)\) nie pasuje do żadnego elementu z \(S\)
- \((3, 2)\) pasuje do:
- \((2, 1)\) tworząc \((3, 1)\)
- \((2, 5)\) tworząc \((3, 5)\)
- \((2, 6)\) tworząc \((3, 6)\)
- \((3, 3)\) pasuje do:
- \((3, 1)\) tworząc \((3, 1)\)
- \((3, 5)\) tworząc \((3, 5)\)
- \((3, 6)\) tworząc \((3, 6)\)
- \((3, 4)\) nie pasuje do żadnego elementu z \(S\)
Tak oto zbierając wszystkie utworzone pary w jeden zbiór, otrzymamy:
\(S \circ R = \set{(1, 1),(1, 5),(1, 6),(2, 1),(2, 5),(2, 6),(3, 1),(3, 5),(3, 6)}\)
Jeżeli chcielibyście sami poćwiczyć tworzenie złożeń, macie tutaj taki mały kalkulatorek, który może wam nieco pomóc w tym zagadnieniu.
INCLUDE_FILE_PATH_NULL
Dodatkowo, jeżeli dziwi was nieco to podejście, ze względu na przestawienie tych relacji w kolejności, spróbujemy teraz przywrócić im kolejność, pokazując, jak troszkę tę definicję zmienić.
Podejście drugie.
Teraz spróbujmy odwrócić kolejność parowania. Weźmy sobie jeszcze raz wzór, jednak teraz przestawmy zbiory:
\(\text{niech } S \subseteq A \times B \\ \text{oraz } \space R \subseteq C \times D \\ \text{wtedy:} \\ S \circ R = \{ (c, b) \subseteq C \times B \space \text{takie że istnieje takie} \space y \in C \cap B \space \text{że} \space (c, y) \in R \space \text{oraz} \space (y, b) \in S \}\)
Zmieniamy teraz nieco strategię. Teraz par będziemy szukać, parując skrajne elementy par relacji \(S\) i \(R\).
Przykład.
Zdefiniujmy sobie \(4\) zbiory. A więc:
\(A = \set{1, 2, 3} \\ B = \set{2, 3, 4} \\ C = \set{2, 3} \\ D = \set{1, 5, 6}\)
Teraz na ich kanwie, utwórzmy relacje:
\(S \subseteq A\times B \subseteq \set{(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} \\ R \subseteq C\times D \subseteq \set{(2, 1), (2, 5), (2, 6), (3, 1), (3, 5), (3, 6)}\)
"Wspólną dziedziną", czyli \(B \times C\) będzie:
\(A \times D = \set{1}\)
A teraz po kolei, bierzemy każdą parę z relacji \(S\) i próbujemy połączyć z każdym elementem relacji \(R\), łącząc elementy skrajne, czyli \(a\) i \(d\).
- \((1, 2)\) pasuje do:
- \((2, 1)\) tworząc \((2, 2)\)
- \((3, 1)\) tworząc \((3, 2)\)
- \((1, 3)\) pasuje do:
- \((2, 1)\) tworząc \((2, 3)\)
- \((3, 1)\) tworząc \((3, 3)\)
- \((1, 4)\) pasuje do:
- \((2, 1)\) tworząc \((2,4)\)
- \((3, 1)\) tworząc \((3, 4)\)
- \((2, 2)\) nie pasuje do żadnej pary z \(R\)
- \((2, 3)\) nie pasuje do żadnej pary z \(R\)
- \((2, 4)\) nie pasuje do żadnej pary z \(R\)
- \((3, 2)\) nie pasuje do żadnej pary z \(R\)
- \((3, 3)\) nie pasuje do żadnej pary z \(R\)
- \((3, 4)\) nie pasuje do żadnej pary z \(R\)
Tak oto zbierając wszystkie utworzone pary w jeden zbiór, otrzymamy:
\(S \circ R = \set{(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}\)
Odwracanie/Transpozycja
Kolejną ciekawą operacją, jaką będziemy robić na relacjach, będzie ich odwracanie. Utworzymy wtedy relację odwrotną, konwers relacji lub jej transpozycję. Będziemy owe odwracanie oznaczać, podnosząc symbolicznie naszą relację do potęgi \(-1\), bądź w owej potędze umieszczać literę \(T\). Polegać będzie natomiast, tak jak sugeruje nazwa, na zamienieniu elementów miejscami w każdej parze uporządkowanej relacji, czyli, jeżeli zdefiniujemy sobie relację \(R = \set{(1, 2), (3, 4), (5, 6)}\), to jej odwrotność zapiszemy jako:
\(R^{-1} = R^T = \set{(2, 1), (4, 3), (6, 5)}\)
Jeżeli jednak chcielibyśmy definiować relację jako podzbiór iloczynu kartezjańskiego jakichś dowolnych dwóch zbiorów, to również należy zamienić miejscami owe zbiory, bo przełoży się dokładnie na zamienienie owych elementów w parach. Czyli mówiąc formalnie, jeżeli \(R \subseteq A \times B\), to jej odwrotnością będzie:
\(R^{-1} = R^T \subseteq B \times A\)
Z ciekawszych oznaczeń, zdecydowanie rzadziej spotykanych, znalazłem również:
\(\displaystyle R^{C}, R^{\tilde{}}, R^{\circ}, R^{\lor}, \breve{R}\)
Własności ogólne
Pełność
O pełności mówiliśmy już we wstępie do relacji, dlatego tutaj podrzucam tylko definicję, która zawęzi ją do relacji binarnej, a mianowicie:
\(R \subseteq A \times B \text{ nazwiemy pełną, jeżeli } R = A \times B\)
Serialność/Lewostronna spójność/Lewostronna całkowitość/Całkowitość
Aby relacja \(R \subseteq A \times B\) była serialna, to dla każdego elementu jej zbioru \(A\), musi istnieć w relacji para z elementem zbioru \(B\). Mówiąc inaczej, żaden element ze zbioru \(A\), w naszej relacji, nie może pozostać bez pary, w której będzie z lewej strony. Przykładowo mając np. zbiory \(A = \set{1, 2}\) i \(B = \set{3, 4}\), to relacją serialną/lewostronnie spójną/lewostronnie całkowitą, będzie relacja \(R = \set{(1, 3), (2, 3)}\), a np. \(R = \set{(2, 3), (2, 4)}\), nie będzie bo będzie brakowało pary dla \(1\).
Formalnie przedstawia się to tak:
\(R \subseteq A \times B \text{ jest serialna/lewostronnie spójna/lewostronnie całkowita/całkowita, jeżeli dla każdego } a \in A \text{ istnieje takie } b \in B \text{, że } aRb\)
Prawostronna spójność/Prawostronna całkowitość/Surjektywność
Spójność prawostronna, będzie się różnić od lewostronnej, zbiorem który musi mieć pary dla swoich elementów. Więc skoro spójność lewostronna musiała mieć pary dla wszystkich elementów zbioru \(A\), tak spójność prawostronna będzie musiała mieć pary dla zbioru \(B\). Czyli mając np. zbiory \(A = \set{1, 2}\) i \(B = \set{3, 4}\), to relacją prawostronnie spójną/prawostronnie całkowitą/surjektywną, będzie relacja \(R = \set{(2, 3), (2, 4)}\), a np. \(R = \set{(1, 3), (2, 3)}\), nie będzie bo będzie brakowało pary dla \(4\).
Formalnie przedstawia się to tak:
\(R \subseteq A \times B \text{ jest surkecją/surjektywna/prawostronnie spójna/prawostronnie całkowita, jeżeli dla każdego } b \in B \text{ istnieje takie } a \in A \text{, że } aRb\)
Jednoznaczność lewostronna/injektywność
Jednoznaczność lewostronna relacji \(R \subseteq A \times B\) oznacza fakt, że każdy element przeciwdziedziny ma dokładnie jedną parę z dokładnie jednym elementem dziedziny. Wynika stąd, że mając parę \((a, b)\) nie znajdziemy w relacji już żadnej pary, która zawierałaby \(b\) z prawej strony, anie nie znajdziemy pary mającej \(a\) z lewej. Bardziej obrazowo, można spróbować powiedzieć, że jesteśmy w stanie przypisać każdemu elementowi przeciwdziedziny, element dziedziny w taki sposób, żeby móc zgadnąć jakie para ma elementy, mając tylko prawy element pary.
Wynika z tego że relacji injektywnej dziedzina i przeciwdziedzina są równe mocą.
Dodać można, patrząc w przyszłość, że prawe elementy z każdej pary będą miały różne wartości (dlaczego o tym wspomniałem, zauważycie w rozdziale o funkcjach).
Formalnie przedstawia się to tak:
\(R \subseteq A \times B \text{ injekcją/injektywna/lewostronnie jednoznaczna} \text{ jeżeli dla każdego } a \in dom(R) \text{ istnieje dokładnie jedno } b \in rng(R) \text{ takie że } aRb\)
Można to przedstawić jeszcze bardziej dokładnie, a mianowicie:
\(R \subseteq A \times B \text{ jest injekcją} \text{, jeżeli dla każdej pary } a, c \in dom(R) \text{, istnieje } b \in rng(R) \text{, takie że jeżeli } aRb \text{ i } cRb \text{, to oznacza, że } a = c\)
Jednoznaczność prawostronna/funcyjność
Jednoznaczność prawostronna jest prawie odwróceniem jednoznaczności lewostronnej. Oznacza to, że każdy element dziedziny ma dokładnie jedną parę z elementem przeciwdziedziny, jednakże nie z dokładnie jednym elementem z przeciwdziedziny. Bardziej obrazowo, w tym przypadku, można spróbować powiedzieć, że jesteśmy w stanie przypisać każdemu elementowi dziedziny, element z przeciwdziedziny w taki sposób, żeby móc zgadnąć jakie para ma elementy, mając tylko lewy element pary.
Formalnie przedstawia się to tak:
\(R \subseteq A \times B \text{ jest funkcyjna} \text{, jeżeli dla każdej pary } b, c \in rng(B) \text{, istnieje } a \in dom(R) \text{, takie że jeżeli } aRb \text{ i } aRc \text{, to oznacza, że } b = c\)
Jednoznaczność obustronna/wzajemna
Jak możemy się powoli domyślać, jednoznaczność obustronna/wzajemna to połączenie jednoznaczności prawostronnej i lewostronnej. Oznacza to, że każdy element dziedziny jest w relacji z dokładnie jednym elementem przeciwdziedziny i jest to odwzorowanie kompletne. Oznacza to że każdy element dziedziny ma dokładnie jedną parę, gdzie znajduje się po lewej stronie i każdy element przeciwdziedziny ma dokładnie jedną parę, gdzie znajduje się po prawej stronie. W takiej relacji żaden element z pola tej relacji nie pozostaje bez pary.
Relacje na jednym zbiorze
Okazuje się, że wiele przypadków relacji, niekoniecznie musi się opierać o więcej niż jeden zbiór. Weźmy np. taką relację mniejszości (na razie nieściśle), jeżeli chcielibyśmy poparować wszystkie elementy mniejsze, z większymi, by określić, który las jest większy pod względem liczności, potrzebowalibyśmy tylko liczb od \(0\) w górę, czyli naturalnych (na razie nieściśle). Nie musielibyśmy parować ich z np. połową drzewa, bo liczenie takiego, nie ma sensu. Dlatego wprowadzimy pewien szczególny przypadek relacji.
Ten szczególny przypadek, o którym mówiłem, to takie relacje, które tworzymy z jednego zbioru. Co to znaczy? Znaczy to tyle, że budując "normalną" relację, konstruujemy ją poddając dwa, niekoniecznie równe sobie zbiory, iloczynowi kartezjańskiemu. W tym przypadku jednak iloczyn kartezjański, tworzymy, "mnożąc" jeden zbiór ze sobą samym. Sprawia to, że dziedziną i przeciwdziedziną relacji staje się on sam. Zapisując to formalnie, dostaniemy:
\(R \subseteq A \times A\)
Albo korzystając z oznaczenia potęgi:
\(R \subseteq A^2\)
Własności.
Relacje "jednozbiorowe", mają pewne swoje własności, różne od już wcześniej wymienionych. Pomogą nam one w przyszłości definiować bardziej szczegółowo, jak relacje się zachowują oraz warunki w których będziemy formułować twierdzenia, albo założenia do różnorakich działań. Jest ich dosyć sporo, jedne będą bardziej, inne mniej eksploatowane, ale warto znać wszystkie.
Jako że owych własności jest masę, nie oczekuję, że ktoś będzie znał je wszystkie na pamięć, bo i ja nie znam, aczkolwiek warto je kojarzyć i wiedzieć, gdzie ewentualnie wrócić po definicję, dlatego ten podroździalik można potraktować, jako swego rodzaju listę/przypominajkę/cheatsheet, do którego można zawsze wrócić, żeby nie ulec przekonaniu, że jak nie będzie się czegoś pamiętać, to znaczy że się nie umie, czy nie rozumie. Można doskonale rozumieć, ale np. nie pamiętać, i tak proszę to traktować, żeby się nie zniechęcać natłokiem informacji, jaki teraz nadejdzie.
Do dzieła więc!
Zwrotność.
Relację nazywamy zwrotną, jeżeli każdy element ze zbioru, który tworzy relację, jest w relacji ze samym sobą. Np. Jeżeli zdefiniujemy sobie relację \(A = \set{1, 2}\), oraz relację \(R \subseteq A \times A = \set{(1, 2), (2, 1)}\), to relacja nie będzie zwrotna, bo znajdziemy element, np. \(2\), który nie ma swojej relacji, czyli \((2, 2)\). Natomiast, jeżeli zdefiniujemy naszą relację jako \(R \subseteq A \times A = \set{(1, 1), (1, 2), (2, 1), (2, 2)}\), to relacja staje się zwrotna, spełniając ten warunek. Każdy element, ma swoją relację, sam ze sobą. Formalnie ten warunek prezentujemy tak:
\(R\text{ jest zwrotna gdy } aRa \text{ dla wszystkich } a\in A\)
Przeciwzwrotność
Relacja będzie przeciwzwrotna, wtedy gdy spełni dokładnie odwrotne warunki jak w zwrotnej. Znaczy to tyle, że w naszej relacji, nie może być żadnej relacji elementów z samym sobą.
Przytaczając nasz poprzedni przykład, mając zbiór \(A = \set{1, 2}\) i tworząc z niego \(R \subseteq A \times A = \set{(1, 2), (2, 1)}\), otrzymamy relację przeciwzwrotną, ponieważ nie ma elementu w zbiorze \(A\), który ma relację ze samym sobą, natomiast \(R \subseteq A \times A = \set{(1, 1), (1, 2), (2, 1), (2, 2)}\), ma np. \((1, 1)\), co sprawia, że nie spełniamy warunków.
Formalnie prezentuje się to tak:
\(R\text{ jest przeciwzwrotna gdy nie zachodzi } aRa \text{ dla żadnego } a\in A\)
Ko-zwrotność
Ten termin wymyśliłem, bo nie znalazłem polskiego tłumaczenia na "Coreflexive".
Nie mniej, ko-zwrotność polega na tym, że relacja będąca ko-zwrotną, będzie posiadać relacje, tylko tych samych elementów. Idąc z konwencją przykładów, jeżeli na zbiorze \(A = \set{1, 2}\) określimy relację \(R = \set{(1, 1), (2, 2)}\), to będzie ona ko-zwrotna, natomiast relacja \(R = \set{(1, 1), (2, 1)}\), już nie.
Formalnie prezentuje się to tak:
\(R\text{ jest ko-zwrotna gdy dla każdego } a, b \in A \text{ jeżeli } aRb \text{ to } a = b\)
Kwazi-zwrotność
Ten termin też wymyśliłem, bo nie znalazłem polskiego tłumaczenia na "Quasi-reflexive".
Relację nazwiemy kwazi-zwrotną, jeżeli dla każdej kombinacji par elementów zbioru, na którym jest określona, jeżeli istnieje dla nich para w relacji, to znaczy, że istnieją też pary elementów owej kombinacji, z samymi sobą. Znaczy to tyle, że jeżeli w relacji kwazi-zwrotnej odnajdziemy parę uporządkowaną \((1, 2)\), to znajdziemy również pary \((1, 1)\) i \((2, 2)\), i tak dla każdej pary w owej relacji.
Np. mając zbiór \(A = \set{1, 2}\) i na nim określoną relację \(R = \set{(1, 2), (2, 2), (1, 1)}\), to będzie ona kwazi-zwrotna, natomiast relacja \(R = \set{(1, 2), (2, 1), (1, 1)}\), już nie będzie, bo brakuje nam pary \((2, 2)\).
Formalnie prezentuje się to tak:
\(R\text{ jest kwazi-zwrotna gdy dla każdego } a, b \in A \text{ jeżeli } aRb \text{ to istnieje również } aRa \text{ i } bRb\)
Symetria
Relację nazwiemy symetryczną, jeżeli dla wszystkich par jakie są zdefiniowane w relacji, istnieje dla nich para, która jest dla niej odwrotna, czyli taka, która ma zamienione miejscami elementy. Np. mając zbiór \(A = \set{1, 2}\) i tworząc z niego \(R \subseteq A \times A = \set{(1, 2), (2, 1)}\), otrzymamy relację symetryczną, bo nasze pary, mają sobie odwrotne pary. Natomiast jeżeli utworzymy, na kanwie tego samego zbioru \(A\), relację \(R \subseteq A \times A = \set{(1, 1), (1, 2), (2, 2)}\), to ona symetryczną nie będzie, ponieważ element \((1, 2)\) nie ma swojej odwrotności \((2, 1)\).
Formalnie prezentuje się to tak:
\(R\text{ jest symetryczna gdy dla każdego } a, b \in A \text{, jeżeli } aRb \text{ to również } bRa\)
Asymetria/Przeciwsymetria
Relację nazwiemy asymetryczną/przeciwsymetryczną jeżeli będzie dokładnie odwrotnie niż przy symetrii. Znaczy jeżeli nie będzie istniała żadna odwrotność, żadnej pary w relacji. Np. mając zbiór \(A = \set{1, 2, 3}\) i tworząc z niego \(R \subseteq A \times A = \set{(1, 2), (1, 3), (2, 3)}\), to relacja ta będzie asymetryczna, bo żadna para nie ma swojej odwrotności. Definiując jednak na kanwie \(A = \set{1, 2, 3}\) relację \(R \subseteq A \times A = \set{(1, 2), (1, 3), (3, 1)}\), nasza relacja nie będzie asymetryczna, ponieważ jedna para \((1, 3)\) posiada swoją odwrotność \((3, 1)\).
Formalnie prezentuje się to tak:
\(R\text{ jest asymetryczna gdy dla każdego } a, b \in A \text{, jeżeli } aRb \text{ to nie } bRa \text{ nie istnieje}\)
Antysymetria
Relację nazwiemy antysymetryczną, jeżeli będzie trochę symetryczna. Co to oznacza? Znaczy to tyle, że wszystkich pary, które będą miały swoją odwrotność/symetrię, będą parami o tych samych elementach. Mówiąc prościej, jedyne elementy jakie mogą być symetryczne w takiej relacji będą parami identycznych elementów, np. \((1, 1)\), \((3, 3)\). Np. mając zbiór \(A = \set{1, 2, 3}\), i tworząc relację \(R \subseteq A \times A = \set{(1, 2), (1, 3), (3, 3)}\), stworzymy relację antysymetryczną, bo jedyna symetria zachodzi dla pary z tych samych elementów. Natomiast definiując, również na kanwie \(A = \set{1, 2, 3}\) relację \(R \subseteq A \times A = \set{(1, 2), (2, 1), (3, 3)}\), to ona nie będzie antysymetryczna, ponieważ symetria zachodzi dla par \((1, 2)\) i \((2, 1)\).
Formalnie prezentuje się to tak:
\(R\text{ jest antysymetryczna gdy dla każdego } a, b \in A \text{, jeżeli } aRb \text{ oraz } bRa \text{, to } a= b\)
Przechodniość/Tranzytywność
Relację nazwiemy przechodnią, jeżeli dla wszystkich elementów w relacji, będzie dało się utworzyć takie trójki elementów, które stworzą "łańcuch" relacji. Łańcuch ten polegał będzie na tym, że relacja elementów skrajnych tej trójki, będzie wynikać z "przechodzenia" po owych elementach. Można też próbować rozumieć to w ten sposób, że z relacji dwóch par elementów, można wywnioskować trzecią relację, elementów z tych par.
Całe przechodzenie polega na tym, że mając trzy elementy zbioru, np: \(\set{1, 2, 3}\), gdy będziemy np. definiować relację elementów mniejszch od siebie, to jeżeli umieścimy w parze relacji \((1, 2)\) oraz \((2, 3)\), to wystąpi także para \((1, 3)\). Zostając w przykładzie relacji mniejszości, to przeczytamy to ten w sposób, że jeżeli \(1\) jest w relacji mniejszości z \(2\) (pierwsza para) i \(2\) jest w relacji mniejszości z \(3\) (druga para), to wyniknie z tego, że \(1\) jest w relacji mniejszości z \(3\) (trzecia para), no bo skoro \(2\) jest większe niż jeden, a \(3\) większe niż \(2\), to \(3\) musi być większe niż \(1\).
Mówiąc jeszcze inaczej, jeżeli dwa elementy są w relacji, a prawy z tej pary, jest w relacji z innym elementem, tylko że z lewej strony, to musi istnieć para, lewego elementu z pierwszej pary i prawego elementu z drugiej.
Formalnie prezentuje się to tak:
\(R \text{ jest przechodnia, jeżeli dla każdego } a, b, c \in A \text{, jeżeli } aRb \text{ oraz } bRc \text{, to } aRc\)
Nieprzechodniość
Relacja nieprzechodnia będzie dokładnym przeciwieństwem relacji przechodniej. Czyli nie będzie się w takiej relacji, dało utworzyć takich trójek elementów, które stworzą "łańcuch" relacji, czy też owego przechodzenia.
Formalnie prezentuje się to tak:
\(R \text{ jest nieprzechodnia, jeżeli dla każdego } a, b, c \in A \text{, jeżeli } aRb \text{ oraz } bRc \text{, to nie istnieje } aRc\)
Koprzechodniość
Ten termin też wymyśliłem, bo nie znalazłem polskiego tłumaczenia na "Cotransitive".
Termin ten można określić jako taką "półprzechodniość". Czemu tak twierdzę? Ano dlatego, że mówiąc o przechodniości, mówimy o wynikaniu, z dwóch par uporządkowanych, trzeciej, w tym jednak przypadku, będziemy stwierdzać obecność jednej z dwóch, na podstawie tej trzeciej.
Co to znaczy?
Pamiętamy, że jeżeli para jest przechodnia, to jesteśmy w stanie stworzyć "łańcuch" relacji, na podstawie owego "przechodzenia" po elementach, tutaj weźmiemy efekt tego przechodzenia i sprawdzimy, czy istnieje chociaż jeden element z dwóch, który mógłby do tego przejścia dopuścić.
Pokazując przykład, weźmy zbiór \(A =\set{1, 2, 3}\) i na nim określmy relację \(R = \set{(1, 2), (1, 3), (2, 3)}\). Widzimy od razu, że jest przechodnia (jeżeli nie wierzysz, to sprawdź, gorąco do tego zachęcam). Teraz odbierzmy jej przechodniość, zabierając środkową parę. Mamy teraz więc relację \(R = \set{(1, 2), (2, 3)}\), która nie jest przechodnia, ale spełnia warunek koprzechodniości. Do pary \((2, 3)\) dałoby się doprowadzić, mając \((1, 2)\) i jeszcze jedną parę. Więc relacja jest koprzechodnia.
Formalnie prezentuje się to tak:
\(R \text{ jest koprzechodnia, jeżeli dla każdego } a, b, c \in A \text{, jeżeli } aRc \text{ to istnieje } aRb \text{ lub } bRc\)
Kwaziprzechodniość
Ten termin też wymyśliłem, bo nie znalazłem polskiego tłumaczenia na "Quasitransitive".
Ta jest trochę zagmatwana, można ją potraktować w sumie jako ciekawostkę, bo nie widziałem jej użycia prawie nigdzie.
Od początku i powoli więc.
Relację nazwiemy kwaziprzechodnią, jeżeli dla każdej trójki ze zbioru, który opisuje relację, jeżeli istnieje taka para par uporządkowanych, z "punktem styku", czyli taka która zapoczątkowała by proces tworzenia "przechodzenia", czyli np. \((1, 2)\) i \((2, 3)\) ALE nie istnieją do nich pary odwrotne, czyli \((2, 1)\) i \((3, 2)\), to znaczy że nie będzie istniała para odwrotna, pierwszego elementu z pierwszej pary i drugiego z drugiej, czyli w tym przypadku \((3, 1)\).
Formalnie prezentuje się to tak:
\(R \text{ jest kwaziprzechodnia, jeżeli dla każdego } a, b, c \in A \text{, jeżeli istnieje } aRb \text{ i } bRc \text{ ale nie istnieje ani } bRa \text{ ani } cRb \text{ to nie istnieje } cRa\)
Spójnościowy komentarz
Spotkałem się z dwoma wariantami definicji spójności, o których muszę wspomnieć.
Bywa, że spójność mocna i słaba jest określana po prostu spójnością. Warto to wiedzieć, bo autorzy różnych pism i artykułów, mogą używać rożnych definicji i można się naciąć, dlatego zawsze warto uściślić o jaką spójność chodzi. My jednak wprowadzimy rozróżnienie między spójnością mocną i słabą.
Spójność mocna
Relację nazwiemy mocno spójną, jeżeli dla każdej dwójki elementów ze zbioru, będzie istniała para, która je połączy.
Np. mając zbiór \(A = \set{1, 2}\) i na nim określoną relację \(R = \set{(1, 2), (1, 3), (3, 2), (1, 1), (2, 2), (3, 3)}\), to będzie ona spójną, ponieważ nie ma takiej pary elementów ze zbioru \(A\), która nie miała by swojej pary uporządkowanej w tym zbiorze. Natomiast, jeżeli pozbawimy tę relację jednej pary, tworząc \(R = \set{(1, 2), (1, 3), (1, 1), (2, 2)}\), to zauważmy, że relacja już nie jest spójna, ponieważ istnieją pary elementów, \((3, 3)\) i \((2, 3)\), które nie mają swojej reprezentacji w tej relacji.
Formalnie prezentuje się to tak:
\(R \text{ jest mocno spójna, jeżeli dla każdego } a, b \in A \text{, istnieje } aRb \text{ lub } bRa\)
Spójność słaba
Spójność słaba będzie się różnić od mocnej tym, że w słabym wariancie, w relacji nie muszą występować pary o tych samych elementach. Można też powiedzieć, że relację nazwiemy słabo spójną, jeżeli dla każdej różnej dwójki elementów ze zbioru, będzie istniała para, która je połączy.
Np. mając zbiór \(A = \set{1, 2}\) i na nim określoną relację \(R = \set{(1, 2), (1, 3), (3, 2), (1, 1)}\), to będzie ona słabo spójna, ale gdy wyciągniemy z niej jedną parę różnych elementów, np. \(R = \set{(1, 2), (1, 3), (1, 1)}\) to już słabo spójna nie będzie, bo parze \((2, 3)\) brakuje w niej reprezentacji.
Formalnie prezentuje się to tak:
\(R \text{ jest słabo spójna, jeżeli dla każdego } a, b \in A \text{, istnieje } aRb \text{ lub } bRa \text{ lub } a = b\)
Półspójność
Relację nazwiemy półspójną, jeżeli dla wszystkich par różnych elementów ze zbioru, który relację określa, znajdziemy reprezentację w relacji. Np. mając zbiór \(A = \set{1,2,3}\) i relację \(R = \set{(1, 2), (1, 3), (2, 3)}\) to będzie ona półspójną, natomiast \(R = \set{(1, 2), (1, 3)}\) już nie będzie.
Formalnie prezentuje się to tak:
\(R \text{ jest półspójna, dla każdego } a, b \in A \text{ jeżeli } a \neq b \text{ to istnieje } aRb \text{ lub } bRa\)
Trychotomiczność
Słowo trychotomia oznacza podział na \(3\). Jest to o tyle ważne, że będzie trzonem tej własności.
Otóż owa trychotomia będzie odnosiła się do tego, że we trychotomiczności będzie musiał być spełniony dokładnie jeden warunek, który tę trychotomiczność określa.
Relację nazwiemy trychotomiczną, jeżeli dla każdej pary elementów ze zbioru na którym określamy relację owa para będzie TYLKO:
- miała swoją reprezentację w postaci pierwszego elementu z drugim
- miała swoją reprezentację w postaci drugiego elementu z pierwszym, czyli odwrotnie niż poprzednio
- będzie to para tych samych elementów
To TYLKO oznacza, że TYLKO jedna z wymienionych cech może być spełniona, nie więcej. Jeżeli nie będzie spełniona żadna, albo dwie z nich, to owa trychotomia nie zajdzie. Idąc z przykładem, mając relację \(R = \set{(1, 2), (1, 3), (3, 2)}\) w takiej postaci, nazwiemy ją trychotomiczną, bo każda para spełnia tylko jeden warunek (jeżeli mi nie wierzysz, do czego zachęcam, rozpisz sobie to na kartce). Natomiast dodając jedną parę, i tworząc relację \(R = \set{(1, 2), (2, 1), (1, 3), (3, 2)}\), to ta już nie będzie trychotomiczna, ponieważ para elementów \((1, 2)\) będzie miała swoją reprezentację w parach \((1, 2)\) i \((2, 1)\).
Formalnie prezentuje się to tak:
\(R \text{ jest trychotomiczna, jeżeli dla każdego } a, b \in A \text{, spełniony jest tylko jeden warunek z wymienionych: } \\ \quad \bullet \text{ istnieje } aRb \\ \quad \bullet \text{ istnieje } bRa \\ \quad \bullet \space a = b\)
Niespójność
Relacja będzie niespójna, jeżeli nie będzie spójna. Tak po prostu.
Formalnie prezentuje się to tak:
\(R \text{ jest niespójna, jeżeli dla każdego } a, b \in A \text{, nie istnieje ani } aRb \text{ ani } bRa\)
Prawoeuklidesowość/Euklidesowość
Relację nazwiemy euklidesową/prawoeuklidesową, jeżeli dla każdej trójki liczb ze zbioru tworzącego relację, jeżeli uda nam się stworzyć takie pary par, że połączy je pierwszy element każdej z nich, tzn. po swojej lewej stronie będą miały ten sam element, natomiast różny z prawej, np. \((1, 2)\) i \((1, 3)\), to w relacji wystąpi para złożona z prawych elementów tych dwóch par które znaleźliśmy, czyli w tym przypadku \((2, 3)\).
Np. jeżeli a kanwie zbioru \(A= \set{1, 2, 3}\), stworzymy relację \(R = \set{
(1, 2), (1, 3), (2, 3), (3, 2)
}\), to będzie ona euklidesowa, natomiast, jeżeli, uszczuplimy tę relację do \(R = \set{
(1, 2), (1, 3), (3, 2)
}\), to nie będzie euklidesowa, bo, dla \(\set{1,2, 3}\), mamy \((1, 2)\) i \((1, 3)\), ale nie mamy \((2, 3)\), która spełniła by warunek.
Formalnie prezentuje się to tak:
\(R \text{ jest euklidesowa, jeżeli dla każdego } a, b, c \in A \text{ jeżeli } aRb \text{ i } aRc \text{ to } bRc\)
Lewoeuklidesowość
Przy lewoeuklidesowości musimy niejako odwrócić prawoeuklidesowość. Mówiąc to mam na myśli to, że jeżeli w prawoeuklidesowości szukaliśmy par, które połączą się pierwszym elementem, to tutaj, muszą się połączyć drugim, np. \((2, 1)\), \((3, 1)\). Dodatkowo, jeżeli wynikową parę, jaka musiała się znaleźć w relacji tworzyliśmy z prawych elementów, tej pary par którą odnaleźliśmy, tak tutaj będziemy ją tworzyć z lewych, w tym przypadku \((2, 3)\).
Np. jeżeli a kanwie zbioru \(A= \set{1, 2, 3}\), stworzymy relację \(R = \set{
(2, 1), (3, 1), (2, 3), (1, 3)
}\), to będzie ona lewoeuklidesowa, natomiast, jeżeli, uszczuplimy tę relację do \(R = \set{
(2, 1), (3, 1), (1, 3)
}\) , to nie będzie euklidesowa, bo, dla \(\set{1, 2, 3}\), mamy \((1, 2)\) i \((1, 3)\), ale nie mamy \((2, 3)\), która spełniła by warunek.
\(R \text{ jest lewoeuklidesowa, jeżeli dla każdego } a, b, c \in A \text{ jeżeli } bRa \text{ i } cRa \text{ to } bRc\)
Gęstość
Relację nazwiemy gęstą, jeżeli dla każdej pary elementów, ze zbioru, z którego tworzymy relację, znajdziemy trzeci element, który po umieszczeniu pomiędzy nimi, stworzy trójkę, w taki sposób, że stworzą one dwie pary, które istnieją w relacji. Będziemy szukać takiego "łącznika", coś podobnego jak przy przechodniości. Ważnym obostrzeniem jest założenie, że relacja gęsta, nie może być pusta.
Co to znaczy?
Znaczy to tyle, że mając np. zbiór \(A = \set{1, 2, 3}\), dla każdej możliwej pary uporządkowanej elementów z tego zbioru, będą istniały dwie pary uporządkowane w tej relacji, takie że pierwszy element pary i łącznik utworzą jedną parę uporządkowaną oraz że łącznik i drugi element z pary utworzą drugą parę uporządkowaną. Np. dla pary \((1, 2)\) będą istniały pary uporządkowane \((1, 3)\) i \((3, 2)\).
Formalnie prezentuje się to tak:
\(R \text{ jest gęsta, jeżeli nie jest pusta oraz} \text{, jeżeli dla każdego } a, b \in A \text{, istnieje element } c \text{, taki że } aRc \text{ i } cRb\)
Kolistość
Relację nazwiemy kolistą/kołową, jeżeli dla wszystkich możliwych trójek liczb ze zbioru tworzącego relację, jeżeli znajdą się pary pierwszego elementu z drugim, i drugiego z trzecim, to musi się znaleźć również para trzeciego z pierwszym. Znaczy to tyle, że jeżeli mamy np. trójkę \((1, 2, 3)\), to w relacji, którą próbujemy określić jako kolistą, wystąpią pary \((1, 2)\), \((2, 3)\) i \((3, 1)\), czyli połączą koniec z początkiem tej trójki par, pierwszym elementem, tworząc jakoby pętlę/koło. Przykładem takiej relacji może być np. relacja na kanwie zbioru \(A= \set{1, 2, 3}\), która będzie wyglądać tak \(R= \set{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}\).
Formalnie prezentuje się to tak:
\(R \text{ jest kolista, jeżeli dla każdego } a, b, c \in A \text{ jeżeli } aRb \text{ i } bRc \text{ to } cRa\)
Zbieżność
Relację nazwiemy zbieżną, jeżeli dla każdej stworzonej trójki liczb ze zbioru tworzącego relację, jeżeli znajdziemy pary pierwszej z drugą i pierwszej z trzecią, to musi się znaleźć taki czwarty element, niekoniecznie różny od dwóch poprzednich, że utworzy on pary, jako prawy element, z drugim elementem i trzecim elementem. Np. jeżeli weźmiemy pod uwagę trójkę \((1, 2, 3)\), to jeżeli w relacji znajdzie się para \((1, 2)\) i \((1, 3)\), to żeby spełnić warunek zbieżności, musimy znaleźć taki element, np. \(4\), z którym znajdziemy pary \((2, 4)\) i \((3, 4)\).
Weźmy przykład z relacją. Jeżeli np. mamy zbiór \(A= \set{1, 2, 3, 4}\) i na jego kanwie relację \(R = \set{
(1, 2), (1, 3), (2, 4), (3, 4)
}\), to będzie ona zbieżna, natomiast jeżeli ją uszczuplimy do postaci \(R = \set{
(1, 2), (1, 3), (3, 4)
}\) to przestanie być zbieżna, bo zabraknie nam pary trzeciego elementu z czwartym.
Formalnie prezentuje się to tak:
\(R \text{ jest zbieżna, jeżeli dla każdego } a, b, c \in A
\text{ jeżeli } aRb \text{ i } aRc
\text{ to istnieje takie } d
\text{ że } bRd \text{ oraz } cRd\)
Relacje identycznościowe
Relacja identycznościowa, to jest szczególny przypadek relacji binarnej "jednozbiorowej", mający jedną ciekawą właściwość. A mianowicie taką jakby pełną symetrię. Będzie to oznaczało, że wszystkie pary relacji identycznościowej, będą parami tych samych elementów.
Formalnie prezentuje się to tak:
\(R \subseteq A \times A \text{ jest identycznościowa, jeżeli dla każdej pary } (a, b) \in R, \space a = b\)
Zakończenie
Wyszedł taki troszkę słowniczek pojęć, ale jest to rzecz niezbędna, żeby dokładniej, precyzyjniej i krócej wyrażać swoje myśli w dalszych artykułach i rozważaniach. Mamy teraz silną podstawę pod relacje binarne, nie jest to jednak jeszcze wyczerpany temat, dlatego będziemy w przyszłości jeszcze prawić na jego temat.
Dziękuję serdecznie za uwagę i do zobaczenia w następnych artykułach :)
Słaba spójność wydaje mi się równoważna półspójności. Implikacja w prawo. Ustalmy a i b. Załóżmy, że a jest różne od b. Z definicji słabej spójności aRb lub bRa lub a=b, ale a jest różne od b czyli aRb lub bRa i relacja jest półspójna. Implikacja w lewo. Ustalmy a i b. Jeśli a jest różne od b to z półspójności aRb lub bRa i relacja jest słabo spójna, a jeśli a=b to też.