W matematyce , A binarny zależność między dwa zestawy E i F, (lub po prostu powiązanie między E i F ) jest utworzona przez podzbiór o iloczyn kartezjański E x F , to znaczy zbiór par której pierwszym składnikiem jest e , a drugi w F . Ta kolekcja jest oznaczona wykresem relacji . Składniki pary należące do wykresu relacji R wyrażone w relacji przez R . Relacja binarna jest czasami określana jako korespondencja między dwoma zestawami.
Na przykład w geometrii płaszczyzny relacja padania między punktem a linią płaszczyzny „punkt A leży na prostej d ” jest relacją binarną między zbiorem punktów a zbiorem prostych płaszczyzny. Te funkcje lub aplikacje z zestawu E na zbiór F mogą być postrzegane jako szczególnych przypadkach relacji binarnych między E i F .
Kiedy F = E , kolejność dwóch składników pary jest ważna. Na przykład relacja „... jest ściśle mniej niż ...”, zauważył, <, na zbiorze N z liczb naturalnych jest relacją na N ; oznaczamy przez n < p, aby wskazać, że n i p są w relacji. Para (1, 2) jest elementem grafu, w przeciwieństwie do pary (2, 1).
Pojęcie relacji można uogólnić na więcej niż dwa argumenty, patrz „ Relacja (matematyka) ”.
Nieformalnie relacja między dwoma zbiorami jest propozycją, która łączy pewne elementy pierwszego zbioru z innymi elementami drugiego zbioru.
W zestawie F składającym się z dziewcząt i zestawie G złożonym z chłopców, moglibyśmy na przykład zdefiniować relację „Alice lubi Bernarda” lub inną relację „Béatrice zna Pawła”… Możemy zatem postrzegać relację jako bycie gwintów łączących elementy dwóch zestawów.
Jeśli relacja jest wewnętrzną kompozycją w obrębie tego samego zbioru lub pomiędzy dwoma zbiorami, z których jeden całkowicie lub częściowo zakrywa drugi, reprezentacją strzałkową może być raczej reprezentacja grafu skierowanego , aby tylko jeden raz umieścić w tym samym miejscu na grafie węzły reprezentujące elementy występujące w dwóch zbiorach. (Kierunek strzałek musi być wyraźnie określony, a powiązania węzła ze sobą dla każdego z elementów powiązanych zwrotnie nie powinny być pomijane, chyba że są domniemane dla wszystkich elementów relacji wewnętrznej).
W przypadku zbioru skończonego możemy następnie spróbować przedstawić relację za pomocą diagramu. Jeśli F = {Lucie, Béatrice, Delphine, Alice} i jeśli G = {Bernard, Antoine, Paul, Charles}, relację miłosną można scharakteryzować za pomocą załączonego diagramu (taki diagram nazywamy diagramem strzałkowym ).
Możemy również przedstawić tę relację, tabelę dwudzielną, z pierwszą listą kolumn z elementów zbioru F , a na czele elementów przybycia G . Pary są reprezentowane przez krzyżyki w kratkach na przecięciu rzędu pierwszego elementu i kolumny drugiego elementu.
. | Bernarda | Antoine | Paweł | Karol |
---|---|---|---|---|
Lucy | X | X | X | . |
Beatrice | . | X | . | . |
Delfina | . | . | . | . |
Alicja | X | . | X | . |
Możemy ubolewać nad tym, że Delphine nikogo nie kocha, że Lucie ma hojne serce i że Charles może czuć się samotny.
Możemy również spróbować wymienić pary w tym związku (dla większej wygody zachowamy tylko dwie pierwsze litery imienia):
Gr = {(Lu, Be), (Lu, An), (Lu, Pa), (Bé, An), (Al, Pa), (Al, Be)}W matematyce „para” składa się z dwóch elementów umieszczonych w nawiasach w określonej kolejności. Relację definiuje się jako zbiór par, to znaczy, jeśli dwa elementy są ze sobą powiązane, to para jest elementem zbioru relacji . Jeśli nazwiemy F zbiorem dziewcząt, a G zbiorem chłopców, to zbiór wszystkich możliwych par nazywamy „iloczynem kartezjańskim F przez G ” i oznaczamy go przez F × G, a relacja polubień jest wtedy definiowana przez zbiór F , zbiór G i podzbiór F × G .
Binarny stosunek R w zbiorze E dla zestawu F jest określona przez część G z E x F .
Jeśli ( x , y ) G , mówimy , że x jest w związku z y i oznaczamy " x R y " ( notacja infiksowa ) , " R ( x , y ) , " R xy " ( notacja przedrostkowa ) .
Zauważ, że w przypadku relacji binarnej konieczne jest określenie zbioru E (nazywanego zbiorem początkowym ), zbioru F (nazywanego zbiorem przybycia ) oraz części G z E × F zwanej wykresem relacji.
Kiedy relacja binarna jest definiowana ze zbioru E do siebie samego (innymi słowy E = F w poprzedniej definicji, a więc definiowana przez część G z E 2 ), nazywana jest również relacją wewnętrzną na E lub po prostu relacją na E .
PrzykładyZestawu definicji , lub domeny o R jest obraz jego wykres przez pierwszy występ , to jest w zestawie: Obraz lub zbiór wartości, w R jest obrazem jej wykres przez drugi występ , to znaczy zestaw:
Jeśli R i S są dwiema relacjami od E do F , mówi się, że S jest dokładniejszy niż R, jeśli jego wykres jest zawarty w wykresie R , tj. jeśli x S y ⇒ x R y .
Relacja binarna może być również postrzegana jako „ funkcja wielowartościowa ”, zwana także „korespondencją”, a słownictwo w tym kontekście oznacza te same pojęcia (w szczególności: wykres, zbiór definicji, obraz, odwrotność).
Jeżeli spełniona jest nierówność E w F i z F na G , można określić zależność od E do G przez:
Punktacja: jeśli jest relacją wewnętrzną na zbiorze E, a n liczbą naturalną, to jest to złożenie ze sobą n razy, z konwencją oznaczającą relację równościową na E .
Jeśli jest relacją E do F , możemy zdefiniować relację F do E zwaną relacją odwrotną , odwrotną lub odwrotną , przez:
Przykłady:
„Mniejsze niż” (≤) i „większe niż” (≥) są wzajemnymi relacjami (dla dowolnej relacji rzędu ≤); „Kocha” i „jest kochany przez” również są odwzajemnione.Reprezentacja wzajemnej relacji jest po prostu wywnioskowana z reprezentacji początkowej korespondencji:
Z założenia odwrotność relacji binarnej ma następujące właściwości:
Co więcej, relacja wewnętrzna jest symetryczna (odp. Odruchowa , odp. Antyrefleksyjna ), jeśli (i tylko wtedy) jest jej odwrotność.
Jeśli jest relacją od E do F , możemy zdefiniować relację od E do F zwaną relacją komplementarną lub logicznym uzupełnieniem przez:
Przykłady:
„Mniejsze niż” (≤) i „ściśle większe niż” (>) są relacjami komplementarnymi względem siebie dla dowolnego porządku całkowitego ≤ (takiego jak porządek po liczbach rzeczywistych); „Lubię” i „nie lubię” również się uzupełniają.Przedstawienie relacji komplementarnej R jest po prostu wydedukowane z R :
Z założenia dopełnienie relacji binarnej ma następujące właściwości:
Ponadto relacja wewnętrzna to:
Gdy dla dowolnego elementu x z E , x pozostaje w relacji tylko z 0 lub 1 elementem y z F , mówimy, że relacja jest funkcjonalna . Jest to elementarny sposób definiowania pojęcia funkcji . W języku formalnym poprzedzająca właściwość jest napisana:
Ważny przykład:
Przekątnej od e jest określona przez: Jest to wykres relacji równości na E , oznaczany = E , lub = w przypadku braku niejednoznaczności na danym zbiorze. Ten związek jest również funkcją The identyczność z E , oznaczoną id E .W szczególnym przypadku, gdy E = F , mówimy, że R jest relacją binarną zdefiniowaną na E lub w E .
Mówi się, że relacja na E jest zwrotna, jeśli dowolny element E jest w relacji ze sobą, to znaczy, jeśli:
Relacja bezrefleksyjnaRelacja na E jest antyrefleksyjna lub antyrefleksyjna, jeśli żaden element E nie jest w relacji ze sobą, to znaczy, jeśli:
Relacja nie może być ani refleksyjna, ani antyrefleksyjna.
Relacja jest symetryczna, jeśli:
Relacja antysymetrycznaRelacja jest powiedziana:
Relacja nie może być ani symetryczna, ani antysymetryczna.
Relacja na E jest przechodnia , jeśli pierwszy element E jest w relacji z samym drugim elementem w relacji z trzecim, pierwszy element jest również w relacji z trzecim, to znaczy, jeśli:
lub znowu, jeśli jego graf zawiera graf jego złożenia z samym sobą, który jest napisany:
Nazywamy czasownik przechodni zamknięcie lub zamknięcie w stosunku
Jest to najmniejsza (w sensie włączenia grafów) zawierająca zależność przechodnia .
Relacja na E jest całkowita (in), jeśli:
lub ponownie, jeśli Unia jej wykres z jego odwrotność jest równa kartezjańskiej placu z E , co jest napisane:
.Ten kwalifikator jest najczęściej używany w związku z relacjami porządkowymi .
Każdy całkowity związek jest refleksyjny .
Relacja równoważności to relacja zwrotna , przechodnia i symetryczna .
Relacja zamówienie jest zwrotna , przechodnia i relacja antysymetryczna .
Jeśli relacja porządku jest całkowita , mówimy, że jest to porządek całkowity . W przeciwnym przypadku mówi się, że tylko częściowe zamówienie.
Turniej jest binarną relacją sumaryczną i skośną .
Tę definicję należy porównać (bez pełnego jej odniesienia) do definicji turnieju w teorii grafów: turniej to graf weryfikujący
Turniej umożliwia modelowanie turniejów w rywalizacji sportowej, w której każda drużyna gra przeciwko wszystkim innym bez remisu.
Rozważmy zbiór skończony E o kardynalnym n i skończony zbiór F o kardynalnym p . Jest tyle relacji binarnych od E do F, ile jest map od E × F do {0, 1}, co daje 2 np relacji.
W szczególności, jeśli E = F , znajdujemy 2 ( n 2 ) relacje binarne na E , z których
Liczba relacji równoważności jest równa liczbie partycji w zestawie, czyli liczbie Bella .
Relacje binarne i układ relacji tworzą kategorię, którą nazywamy kategorią relacji i którą oznaczamy przez Rel .