Relacja dwuargumentowa

Relacja dwuargumentowa, dwuczłonowa^[1] albo binarna – dowolny podzbiór iloczynu kartezjańskiego dwóch zbiorów^[2].

Wprowadzenie do zagadnienia można znaleźć w artykule o relacjach skończonej liczby argumentów.

Definicje

Relacja dwuargumentowa ${\displaystyle \varrho }$ jako podzbiór iloczynu kartezjańskiego ${\displaystyle X}$ i ${\displaystyle Y}$ jest zbiorem par uporządkowanych postaci ${\displaystyle (x,y)}$ należących do zbioru ${\displaystyle X\times Y;}$ czasami zamiast ${\displaystyle (x,y)\in \varrho }$ pisze się ${\displaystyle x\ \varrho \ y}$ i mówi, że element ${\displaystyle x}$ jest w relacji ${\displaystyle \varrho }$ z elementem ${\displaystyle y,}$ bądź między elementami ${\displaystyle x,y}$ zachodzi relacja ${\displaystyle \varrho .}$ Istnieje pewna rozbieżność względem nazewnictwa dotyczącego zbiorów; tutaj dziedziną i przeciwdziedziną nazywane będą odpowiednio zbiory ${\displaystyle X}$ i ${\displaystyle Y;}$ z kolei zbiór

${\displaystyle \mathrm {D_{L}} (\varrho )={\Big \{}x\in X\colon \exists _{y\in Y}\;(x,y)\in \varrho {\Big \}},}$

tzn. zbiór złożony ze wszystkich poprzedników par należących do relacji ${\displaystyle \varrho ,}$ nazywany będzie dziedziną lewostronną (często nazywa się ją nieprecyzyjnie po prostu dziedziną), zaś zbiór

${\displaystyle \mathrm {D_{R}} (\varrho )={\Big \{}y\in Y\colon \exists _{x\in X}\;(x,y)\in \varrho {\Big \}},}$

tzn. zbiór złożony ze wszystkich następników par należących do relacji ${\displaystyle \varrho ,}$ nazywany będzie dziedziną prawostronną lub obrazem tej relacji (zob. Własności). Sumę dziedzin lewostronnej i prawostronnej (dziedziny i obrazu) nazywa się polem relacji. Zbiór ${\displaystyle \mathrm {Rel} (X,Y)}$ wszystkich relacji dwuargumentowych między zbiorami ${\displaystyle X,Y}$ ma moc ${\displaystyle |\mathrm {Rel} (X,Y)|=2^{|X||Y|}.}$

Własności

Całkowita, niesuriektywna relacja funkcyjna będąca iniekcją

Odpowiedniość jednoznaczna tylko prawostronnie

Jednoznaczność

• jednoznaczność lewostronna lub iniektywność,

  ${\displaystyle \forall _{x,z\in X}\;\forall _{y\in Y}\;x\ \varrho \ y\land z\ \varrho \ y\Rightarrow x=z;}$

• jednoznaczność prawostronna lub funkcyjność,

  ${\displaystyle \forall _{x\in X}\;\forall _{y,z\in Y}\;x\ \varrho \ y\land x\ \varrho \ z\Rightarrow y=z;}$

• jednoznaczność obustronna bądź wzajemna (1-1),

  iniektywność i funkcyjność.

Całkowitość

• całkowitość lewostronna lub krótko całkowitość,

  ${\displaystyle \forall _{x\in X}\;\exists _{y\in Y}\;x\ \varrho \ y,}$

• całkowitość prawostronna lub suriektywność,

  ${\displaystyle \forall _{y\in Y}\;\exists _{x\in X}\;x\ \varrho \ y,}$

• odpowiedniość,

  całkowitość i suriektywność.

Funkcją nazywa się dowolną relację funkcyjną całkowitą (lewostronnie), jeśli ${\displaystyle X=Y,}$ to funkcję nazywa się zwykle działaniem jednoargumentowym; z kolei wzajemnie jednoznaczną odpowiedniość, nazywaną bijektywnością, nazywa się funkcją wzajemnie jednoznaczną lub bijekcją. W przypadku funkcji pojęcia dziedziny, przeciwdziedziny i obrazu pokrywają się z definicjami dla relacji; nazywanie wtedy dziedziną dziedziny lewostronnej nie prowadzi do niejasności, gdyż są one sobie równe.

Relacje w zbiorze

Jeżeli ${\displaystyle Y=X,}$ tzn. ${\displaystyle \varrho \subseteq X^{2},}$ to o relacji ${\displaystyle \varrho }$ mówi się, że jest określona w/na zbiorze ${\displaystyle X.}$ Zbiór par ${\displaystyle \{(x,x)\colon x\in X\}}$ nazywa się wtedy przekątną. W tym przypadku możliwe jest określenie kolejnych własności tego rodzaju relacji:

• zwrotność,

  ${\displaystyle x\ \varrho \ x,}$

• przeciwzwrotność (ścisłość),

  ${\displaystyle \neg (x\ \varrho \ x),}$

• symetryczność,

  ${\displaystyle x\ \varrho \ y\Rightarrow y\ \varrho \ x,}$

• antysymetryczność (słaba antysymetryczność),

  ${\displaystyle x\ \varrho \ y\land y\ \varrho \ x\Rightarrow x=y,}$

• przeciwsymetryczność lub asymetryczność (ścisła antysymetryczność),

  ${\displaystyle x\ \varrho \ y\Rightarrow \neg (y\ \varrho \ x),}$

• przechodniość,

  ${\displaystyle x\ \varrho \ y\land y\ \varrho \ z\Rightarrow x\ \varrho \ z,}$

• spójność (dokładniej: porównywalność lub całkowitość),

  ${\displaystyle x\ \varrho \ y\lor y\ \varrho \ x,}$

• spójność,

  ${\displaystyle x\ \varrho \ y\lor y\ \varrho \ x\lor x=y,}$

• trychotomiczność,

  ${\displaystyle x\ \varrho \ y\ {\underline {\lor }}\ y\ \varrho \ x\ {\underline {\lor }}\ x=y,}$

• euklidesowość (prawostronna),

  ${\displaystyle x\ \varrho \ y\land x\ \varrho \ z\Rightarrow y\ \varrho \ z.}$

Relacje dwuargumentowe według własności

Nazwa relacji	Zwrot.	Symetr.	Przech.	Symbol	Przykład
graf skierowany				${\displaystyle \to }$
graf nieskierowany	Nie	Tak
turniej	Nie	Nie			porządek dziobania
zależność	Tak	Tak
słaby porządek			Tak	${\displaystyle \leqslant }$
praporządek	Tak		Tak	${\displaystyle \leqslant }$	preferencja
częściowy porządek	Tak	Nie	Tak	${\displaystyle \leqslant }$	zawieranie
częściowa równoważność		Tak	Tak
równoważność	Tak	Tak	Tak	${\displaystyle \sim ,\approx ,\simeq ,\cong ,\equiv }$	równość
ostry częściowy porządek	Nie	Nie	Tak	${\displaystyle <}$	zawieranie właściwe

Relacja jest:

• trychotomiczna wtedy i tylko wtedy, gdy jest przeciwzwrotna, antysymetryczna i spójna (nie: porównywalność);
• przeciwsymetryczna wtedy i tylko wtedy, gdy jest antysymetryczna i przeciwzwrotna;
• antysymetryczna wtedy, gdy jest przeciwzwrotna i przechodnia;
• zwrotna wtedy, gdy jest porównywalna (spójna);
• pod założeniem symetryczności – euklidesowa wtedy i tylko wtedy, gdy jest przechodnia;
• symetryczna i przechodnia wtedy, gdy jest euklidesowa i zwrotna.

Rodzaje

Ustalone kombinacje powyższych własności mają swoje własne nazwy:

• tolerancja lub podobieństwo – zwrotność i symetryczność; zależność – dodatkowo skończone pole;
• opozycja – przeciwzwrotność i symetryczność; niezależność – dodatkowo skończone pole;
• równoważność – zwrotność, symetryczność i przechodniość; zwrotność i euklidesowość;
• równość – równoważność i antysymetryczność (relacja równa przekątnej);
• praporządek lub quasi-porządek – zwrotność i przechodniość;
• częściowy porządek – zwrotność, antysymetryczność i przechodniość; wariant ostry: przeciwzwrotność bądź antysymetryczność i przechodniość (zob. wyżej);
• porządek liniowy albo całkowity lub łańcuch – antysymetryczność, przechodniość i porównywalność/całkowitość (spójność); wariant ostry: przechodniość i trychotomiczność.

Wśród pozostałych własności można wymienić dobre ufundowanie i konfluentości: słabą i silną, seryjność oraz gęstość; relacjami, definiowanymi za pomocą wymienionych wyżej własności, są m.in. dobry porządek (dobre ufundowanie, ostry porządek liniowy) i relacja równoważności (seryjność, symetryczność, przechodniość).

Przykłady

Niespójna figura geometryczna na płaszczyźnie jako przykład relacji na zbiorze liczb rzeczywistych.

Najprostszą relacją, którą można określić na dowolnych dziedzinach, jest relacja pusta równa zbiorowi pustemu ${\displaystyle \varnothing .}$ Określona na jednym zbiorze jest symetryczna, antysymetryczna, przeciwsymetryczna, przeciwzwrotna i przechodnia, ale nie spójna ani zwrotna (chyba że jest określona na zbiorze pustym), jest ona bijekcją zbioru pustego, szczególnym przypadkiem tzw. funkcji pustej.

Na „drugim biegunie” można znaleźć relację pełną równą ${\displaystyle X\times Y.}$ Określona na zbiorze jest tam zwrotna, symetryczna, spójna, przechodnia (relacja równoważności o jednej klasie abstrakcji), nie jest przeciwzwrotna, antysymetryczna, przeciwsymetryczna (o ile nie jest określona na zbiorze pustym).

W zbiorze liczb rzeczywistych ${\displaystyle \mathbb {R} }$ obok struktury algebraicznej jaką jest ciało wprowadza się również relacje równoważności i porządku (zob. ciało uporządkowane), np. równość ${\displaystyle =,}$ czy porządek liniowy ${\displaystyle \leqslant }$ („mniejsze-równe”) liczb rzeczywistych. Relacje na zbiorze liczb rzeczywistych można traktować jak figury na płaszczyźnie: relacją pustą jest wtedy figura pusta, relacją pełną jest cała płaszczyzna, a przekątną tworzy prosta będąca wykresem funkcji tożsamościowej (w modelu analitycznym płaszczyzny euklidesowej, czyli z wybranym układem współrzędnych); relacjami równoważności na płaszczyźnie są np. przystawanie, czy podobieństwo.

Przypisy

1. Birkhoff i Mac Lane 1966 ↓, s. 41.
2. relacja, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-10-10] .

Bibliografia

• Garrett Birkhoff, Saunders Mac Lane: Przegląd algebry współczesnej. Warszawa: Państwowe Wydawnictwo Naukowe, 1966.

Linki zewnętrzne

• Binary relation (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-11-05].

Encyklopedie internetowe (relacja):

• Britannica: topic/binary-relation