Binární relace

Z Wikipedie, otevřené encyklopedie

Binární relace je pojem z matematiky, vyjadřuje vztah (relaci) prvků jedné množiny k prvkům v množině druhé.

Příklad: Mějme množiny čísel $A = (1,5,8)$ , $B = (3,5,6)$ . Definujeme vztah (binární relaci) „je větší“ prvků z $A$ k prvkům z $B$ . Vidíme, že číslo $8$ (z množiny $A$ ) „je větší“ než číslo $3$ z $B$ . A říkáme, že prvek $8$ je v binární relaci „je větší“ s prvkem $3$ , zkráceně $(8$ „je větší“ $3)$ . Většinou prvky které jsou v binární relaci značíme jen jako uspořádanou dvojici $[8,3]$ . Všechny binární relace z tohoto příkladu lze popsat jako množinu uspořádaných dvojic $R = ([8,3],[8,5],[8,6],[5,3])$ . Na množinu $R$ lze nahlížet jako na podmnožinu kartézského součinu $A\times B$ . Množiny $(A, B, R)$ lze použít jako definici binární relace.

[editovat] Formální definice

Binární relace je uspořádána trojice $[A,$ $B,$ $R]$ , kde $A$ a $B$ jsou libovolné množiny a $R$ je podmnožina kartézského součinu $A\times B$ . Množině $A$ se říká definiční obor, množině $B$ obor hodnot a množinu $R$ nazýváme graf relace.

[editovat] Značení relací

Binární relace značíme uspořádanou dvojicí $[x,$ $y]$ nebo pokud chceme rozlišit o kterou relaci se jedná pak $(x$ $R$ $y)$ , kde $x\in A, y\in B$ a $R$ je označení příslušné množiny z definice.

[editovat] Druhy relací

Binární relace je

symetrická pokud platí $(x$ $R$ $y)$ , pak $(y$ $R$ $x)$ .

Příkladem může být relace

R =

„je sourozenec“. Je-li

A

B

množinou všech mých příbuzných, pak musí existovat (já R sestra) a také (sestra R já). (Pokud sourozence nemám, je množina relací prázdná, i taková relace je symetrická).

tranzitivní pokud $(x$ $R$ $y)$ a současně $(y$ $R$ $z)$ , pak platí $(x R z)$ .

Příkladem může být už zmíněná relace "je sourozenec" nebo relace "je vyšší". Já jsem vyšší než Petr,(a současně) Petr je vyšší než Ondřej, z toho plyne: Já jsem vyšší než Ondřej. Tranzitivní relací například není relace "být kamarád". Já jsem kamarád Petra, on je kamarád Ondřeje, z toho ale nevyplývá kamarádství mezi mnou a Ondřejem.

reflexivní pokud pro všechny x patřící X platí $(x$ $R$ $x)$ , to znamená pokud je prvek $x$ v relaci sám se sebou. (Samozřejmě, že první $x$ pochází z množiny $A$ a druhé $x$ pochází z $B$ . Mohou to být stejné množiny.)

Příklad reflexivní relace je "je stejný", příklad nereflexivní je "je vyšší". Neplatí, že (já "je vyšší"(než) já).

antisymetrická pokud $(x$ $R$ $y)$ a současně $(y$ $R$ $x)$ , pak platí $x = y$ .

Relaci, která je reflexivní, symetrická, a tranzitivní nazýváme relace ekvivalence.
Relaci, která je reflexivní, antisymetrická a tranzitivní nazýváme částečné uspořádání.
Další typy: úplné uspořádání, dobré uspořádání.

[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 R?S obsahující pouze takové uspořádané dvojice, které se nacházejí současně v obou relacích. Tedy R?S = {[x,y]; [x,y]?R ? [x,y]?S}
Sjednocení relací R a S je relace R?S obsahující takové uspořádané dvojice, které se nacházejí alepoň v jedné z relací. Tedy R?S = {[x,y]; [x,y]?R ? [x,y]?S}

Citováno z „http://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_relace“

Kategorie: Teorie množin