Relacja dwuargumentowa

Ten artykuł dotyczy relacji dwuargumentowej. Zobacz też: relacje trójargumentowe i relacje skończenieargumentowe.

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

 Zobacz też: iloczyn kartezjański i para uporządkowana.

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

 Zobacz też: funkcja, funkcja wzajemnie jednoznaczna i działanie jednoargumentowe.

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

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

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].