Binární relace

Z Wikipedie, otevřené encyklopedie

Jako binární relaci nazveme v matematice libovolnou podmnožinu kartézského součinu dvou množin. Binární relace je nejčastějším příkladem relace. U binárních relací obvykle přívlastek „binární“ vynecháváme a mluvíme pouze o relacích.

Obsah

[editovat] Definice

Množina R se nazývá binární relace, právě když

(\forall x) (x \in R \Rightarrow (\exists y)(\exists z) x=[y,z]).

Binární relaci R mezi množinami A a B zapisujeme jako uspořádanou trojici [R; A, B]. Není-li nezbytně nutné uvádět konkrétní množiny, postačuje zápis R.

Místo zápisu [x,y] ∈ R většinou píšeme xRy. Místo [5,7] ∈ < tedy používáme 5 < 7.

Je-li [x,y] prvkem relace, říkáme, že prvek x je v (binární) relaci s prvkem y - což zapisujeme xRy. Není-li [x,y] prvkem relace, říkáme, že prvek x není v (binární) relaci s prvkem y - což značíme x\bar{R}y.

[editovat] Definiční obor a obor hodnot

Definičním oborem relace (také prvním oborem nebo levým oborem), nebo také vzorem Dom(R) relace [R; A, B] nazýváme množinu právě těch prvků x z A, z nichž ke každému existuje alespoň jeden takový prvek y z B, že x je v relaci s y, tedy

\mathrm{Dom}(R)=\{x \in A; \exists y \in B : xRy\}

Výstupním oborem relace (také druhým oborem, pravým oborem nebo oborem hodnot), nebo také obrazem Rang(R) relace [R; A, B] nazýváme množinu právě těch prvků y z B, z nichž ke každému existuje alespoň jeden takový prvek x z A, že x je v relaci s y, tedy

\mathrm{Rang}(R)=\{y \in B; \exists x \in A : xRy\}

Oborem množiny A se nazývá množina

\mathrm{Dom} (A) \cup \mathrm{Rang} (A)

Relace v množině A je taková relace, která má za definiční obor podmnožinu A.

Relace na množině A je taková relace, která má za definiční obor celou množinu A.

[editovat] Vlastnosti

Binární relace je

  • identická nebo identita (idA), právě když pro všechny prvky x množiny A z přiřazení x idA y plyne x = y ∈ A
  • reflexivní, právě když pro všechna x z množiny A platí, že x je v relaci s x
  • ireflexivní, právě když pro všechna x z množiny A platí, že x není v relaci s x
  • symetrická, právě když pro všechna x a y z množiny A platí, že je-li x v relaci s y, pak je y v relaci s x
  • antisymetrická, právě když pro všechna x a y z množiny A platí, že je-li x v relaci s y, pak y není v relaci s x
  • slabě antisymetrická, právě když pro všechna přiřazení xRy a yRx plyne x=y
  • tranzitivní, právě když z každých dvou přiřazení xRy a yRz plyne xRz
  • atransitivní, právě když z každých n (n ≥ 2) navazujících přiřazení x1Rx2, x2Rx3, …, xnRxn+1 plyne, že x1 není v relaci s xn+1
  • úplná, právě když platí xRy nebo yRx nebo x=y
  • univerzální, právě když obsahuje všechna přiřazení xRy, yRx a xRx
  • cyklická, právě když \bigcup_{i=1}^{\infty}R^i\subseteq R_{-1}
  • acyklická, právě když \left(\bigcup_{i=1}^{\infty}R^i\right) \cap R_{-1} = \emptyset
  • diagonální Δ = ΔX = { (x,x) | x ∈ X }

[editovat] Operace

Na množině binárních relací jsou definovány následující operace - jejich výsledkem je opět relace

  • Inverzní relace k relaci R je taková relace R-1 (R-1) mezi množinami B a A, obsahující právě ty [y,x] ∈ B × A, že [x,y] ∈ R.
  • Relace složená z relací R a S je relace T = S \circ R (R složeno s S) z množiny A do množiny C, která obsahuje právě taková [x,z] ∈ A × C, pro něž existuje takový prvek y v množině B, že [x,y] ∈ R a [y,z] ∈ S, tedy
R \circ S = \{[x,z]; \exists y \in B: [x,y] \in R \and [y,z] \in S
  • Průnik relací R a S je relace RS obsahující pouze takové uspořádané dvojice, které se nacházejí současně v obou relacích. Tedy RS = {[x,y]; [x,y]∈R ∧ [x,y]∈S}
  • Sjednocení relací R a S je relace RS obsahující takové uspořádané dvojice, které se nacházejí alepoň v jedné z relací. Tedy RS = {[x,y]; [x,y]∈R ∨ [x,y]∈S}

[editovat] Druhy

Binární relace se nazývá:

  • tolerance, právě když je reflexivní a symetrická.
  • ekvivalence, právě když je reflexivní, symetrická a tranzitivní
  • kvaziuspořádání, právě když je reflexivní a tranzitivní
  • částečné uspořádání, uspořádání nebo neostré uspořádání, právě když je reflexivní, slabě antisymetrická a tranzitivní
  • ostré uspořádání, právě když je ireflexivní, antisymetrická a tranzitivní
  • úplné uspořádání, právě když je uspořádáním (je reflexivní, slabě antisymetrická a tranzitivní) a pro každé dva prvky x,y platí buď xRy, nebo yRx.
  • úplné ostré uspořádání, právě když je ostrým uspořádáním (je ireflexivní, antisymetrická a tranzitivní) a pro každé dva prvky x,y platí buď xRy, nebo yRx.
  • zobrazení, pokud xRy a xRz, pak y=z