Binární relace

Binární relace je pojem z matematiky. Vyjadřuje vztah (relaci) prvků jedné množiny k prvkům množiny 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 množiny $B$. Ří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]$. Binární relaci 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$. Trojici množin $[A,B,R]$ lze považovat za definici binární relace.

Definice

Binární relace je uspořádaná 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.

To, že prvek $x$ je v relaci $R$ s prvkem $y$ značíme zápisem $[x,y]\in R$, nebo zápisem $xRy$, kde $x\in A$ a $y\in B$.

Druhy relací

Binární relace je:

• symetrická: pokud platí $xRy$, pak platí i $yRx$.

Příkladem může být relace $R$ „je sourozenec“. Je-li $A$ i $B$ množinou všech mých příbuzných, a platí-li (já $R$ sestra), pak také platí (sestra $R$ já). Pokud sourozence nemám, je graf relace prázdnou množinou. I taková relace je symetrická.

• antisymetrická: pokud $xRy$ a současně $yRx$, pak platí $x=y$.

• tranzitivní: pokud $xRy$ a současně $yRz$, pak platí $xRz$.

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 každé $x$ platí $xRx$. (Prvek $x$ je v relaci sám se sebou.)

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

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

Operace s relacemi

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$ mezi množinami $B$ a $A$ je relace $R^{-1}=\{[y,x]\in B\times A|[x,y]\in R\}$

• Relace složená z relací $R$ a $S$ je relace $R\circ S=\{[x,z]|[x,y]\in R\wedge [y,z]\in S\}$

• Průnik relací $R$ a $S$ je relace $R\cap S=\{[x,y]|[x,y]\in R\wedge [x,y]\in S\}$

• Sjednocení relací $R$ a $S$ je relace $R\cup S=\{[x,y]|[x,y]\in R\vee [x,y]\in S\}$

Externí odkazy

• Šablona:Commonscat