Cesko.wiki Binární relace
Author
Albert FloresBiná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. +more 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]. 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. Množiny (A, B, R) lze použít jako definici binární relace.
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.
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.
Druhy relací
Binární relace je:
* symetrická, pokud platí (x R y), pak platí (y R x). :Příkladem může být relace R „je sourozenec“. +more Je-li A i 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á.
* antisymetrická pokud (x R y) a současně (y R x), pak platí x = y.
* 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šší". +more 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í (x R x). (Prvek x je v relaci sám se sebou. +more) :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 \land [y,z] \in S\}
* Průnik relací R a S je relace R \cap S = \{[x,y] \ | \ [x,y] \in R \land [x,y] \in S\}
* Sjednocení relací R a S je relace R \cup S = \{[x,y] \ | \ [x,y] \in R \lor [x,y] \in S\}