Relacja dwuargumentowa


Relacja dwuargumentowa w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Spis treści

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

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

Definicje | edytuj kod

 Zobacz też: iloczyn kartezjańskipara uporządkowana.

Relacja dwuargumentowa ϱ {\displaystyle \varrho } jako podzbiór iloczynu kartezjańskiego X {\displaystyle X} i Y {\displaystyle Y} jest zbiorem par uporządkowanych postaci ( x , y ) {\displaystyle (x,y)} należących do zbioru X × Y ; {\displaystyle X\times Y;} czasami zamiast ( x , y ) ϱ {\displaystyle (x,y)\in \varrho } pisze się x   ϱ   y {\displaystyle x\ \varrho \ y} i mówi, że element x {\displaystyle x} jest w relacji ϱ {\displaystyle \varrho } z elementem y , {\displaystyle y,} bądź między elementami x , y {\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 X {\displaystyle X} i Y ; {\displaystyle Y;} z kolei zbiór

D L ( ϱ ) = { x X : y Y ( x , y ) ϱ } , {\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

D R ( ϱ ) = { y Y : x X ( x , y ) ϱ } , {\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 R e l ( X , Y ) {\displaystyle \mathrm {Rel} (X,Y)} wszystkich relacji dwuargumentowych między zbiorami X , Y {\displaystyle X,Y} ma moc | R e l ( X , Y ) | = 2 | X | | Y | . {\displaystyle |\mathrm {Rel} (X,Y)|=2^{|X||Y|}.}

Własności | edytuj kod

 Zobacz też: funkcja, funkcja wzajemnie jednoznacznadziałanie jednoargumentowe. Całkowita, niesuriektywna relacja funkcyjna będąca iniekcją Odpowiedniość jednoznaczna tylko prawostronnie
Jednoznaczność
  • jednoznaczność lewostronna lub iniektywność, x , z X y Y x   ϱ   y z   ϱ   y x = z ; {\displaystyle \forall _{x,z\in X}\;\forall _{y\in Y}\;x\ \varrho \ y\land z\ \varrho \ y\Rightarrow x=z;}
  • jednoznaczność prawostronna lub funkcyjność, x X y , z Y x   ϱ   y x   ϱ   z y = z ; {\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ść, x X y Y x   ϱ   y , {\displaystyle \forall _{x\in X}\;\exists _{y\in Y}\;x\ \varrho \ y,}
  • całkowitość prawostronna lub suriektywność, y Y x X x   ϱ   y , {\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 X = Y , {\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 | edytuj kod

Jeżeli Y = X , {\displaystyle Y=X,} tzn. ϱ X 2 , {\displaystyle \varrho \subseteq X^{2},} to o relacji ϱ {\displaystyle \varrho } mówi się, że jest określona w/na zbiorze X . {\displaystyle X.} Zbiór par { ( x , x ) : x X } {\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ść, x   ϱ   x , {\displaystyle x\ \varrho \ x,}
  • przeciwzwrotność (ścisłość), ¬ ( x   ϱ   x ) , {\displaystyle \neg (x\ \varrho \ x),}
  • symetryczność, x   ϱ   y y   ϱ   x , {\displaystyle x\ \varrho \ y\Rightarrow y\ \varrho \ x,}
  • antysymetryczność (słaba antysymetryczność), x   ϱ   y y   ϱ   x x = y , {\displaystyle x\ \varrho \ y\land y\ \varrho \ x\Rightarrow x=y,}
  • przeciwsymetryczność lub asymetryczność (ścisła antysymetryczność), x   ϱ   y ¬ ( y   ϱ   x ) , {\displaystyle x\ \varrho \ y\Rightarrow \neg (y\ \varrho \ x),}
  • przechodniość, x   ϱ   y y   ϱ   z x   ϱ   z , {\displaystyle x\ \varrho \ y\land y\ \varrho \ z\Rightarrow x\ \varrho \ z,}
  • spójność (dokładniej: porównywalność lub całkowitość), x   ϱ   y y   ϱ   x , {\displaystyle x\ \varrho \ y\lor y\ \varrho \ x,}
  • spójność, x   ϱ   y y   ϱ   x x = y , {\displaystyle x\ \varrho \ y\lor y\ \varrho \ x\lor x=y,}
  • trychotomiczność, x   ϱ   y   _   y   ϱ   x   _   x = y , {\displaystyle x\ \varrho \ y\ {\underline {\lor }}\ y\ \varrho \ x\ {\underline {\lor }}\ x=y,}
  • euklidesowość (prawostronna), x   ϱ   y x   ϱ   z y   ϱ   z . {\displaystyle x\ \varrho \ y\land x\ \varrho \ z\Rightarrow y\ \varrho \ z.}

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 | edytuj kod

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 | edytuj kod

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ą X × Y . {\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 R {\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.

Na podstawie artykułu: "Relacja dwuargumentowa" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy