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 ${\displaystyle A=\{1,5,8\}}$, ${\displaystyle B=\{3,5,6\}}$. Definujeme vztah (binární relaci) „je větší“ prvků z ${\displaystyle A}$ k prvkům z ${\displaystyle B}$. Vidíme, že číslo ${\displaystyle 8}$ z množiny ${\displaystyle A}$ „je větší“ než číslo ${\displaystyle 3}$ z množiny ${\displaystyle B}$. Říkáme, že prvek ${\displaystyle 8}$ je v binární relaci „je větší“ s prvkem ${\displaystyle 3}$, zkráceně ${\displaystyle (8}$ „je větší“ ${\displaystyle 3)}$. Většinou prvky, které jsou v binární relaci, značíme jen jako uspořádanou dvojici ${\displaystyle [8,3]}$. Binární relaci z tohoto příkladu lze popsat jako množinu uspořádaných dvojic ${\displaystyle R=\{[8,3],[8,5],[8,6],[5,3]\}}$. Na množinu ${\displaystyle R}$ lze nahlížet jako na podmnožinu kartézského součinu ${\displaystyle A\times B}$. Trojici množin ${\displaystyle [R,A,B]}$ lze považovat za definici binární relace.

Definice

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

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

Druhy relací

Binární relace^[1] je:

• reflexivní: pokud pro každé ${\displaystyle x}$ platí ${\displaystyle xRx}$. (Prvek ${\displaystyle 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á.

• antireflexivní: pokud pro každé ${\displaystyle x}$ neplatí ${\displaystyle xRx}$. (Prvek ${\displaystyle x}$ není v relaci sám se sebou.)

• symetrická: pokud platí ${\displaystyle xRy}$, pak platí ${\displaystyle yRx}$.

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

• silně antisymetrická: pokud platí ${\displaystyle xRy}$, pak neplatí ${\displaystyle yRx}$.

• slabě antisymetrická: pokud platí ${\displaystyle xRy}$ a ${\displaystyle yRx}$, pak platí ${\displaystyle x=y}$.

• trichotomická: pokud platí ${\displaystyle xRy}$ nebo ${\displaystyle yRx}$ nebo ${\displaystyle x=y}$.

• tranzitivní: pokud platí ${\displaystyle xRy}$ a ${\displaystyle yRz}$, pak platí ${\displaystyle 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.

Relaci, která je reflexivní, symetrická, a tranzitivní nazýváme relace ekvivalence.

Relaci, která je reflexivní, slabě antisymetrická a tranzitivní nazýváme neostré uspořádání.

Relaci, která je antireflexivní a tranzitivní nazýváme ostré 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 ${\displaystyle R}$ mezi množinami ${\displaystyle B}$ a ${\displaystyle A}$ je relace ${\displaystyle R^{-1}=\{[y,x]\in B\times A\ |\ [x,y]\in R\}}$

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

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

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