Binární relace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 , . Definujeme vztah (binární relaci) „je větší“ prvků z k prvkům z . Vidíme, že číslo (z množiny ) „je větší“ než číslo z . A říkáme, že prvek je v binární relaci „je větší“ s prvkem , zkráceně „je větší“ . Většinou prvky které jsou v binární relaci značíme jen jako uspořádanou dvojici . Binární relaci z tohoto příkladu lze popsat jako množinu uspořádaných dvojic . Na množinu lze nahlížet jako na podmnožinu kartézského součinu . Množiny lze použít jako definici binární relace.

Formální definice[editovat | editovat zdroj]

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

Značení relací[editovat | editovat zdroj]

Binární relace značíme uspořádanou dvojicí nebo pokud chceme rozlišit o kterou relaci se jedná pak , kde a je označení příslušné množiny z definice.

Druhy relací[editovat | editovat zdroj]

Binární relace může být:

  • symetrická pokud platí , pak .
Příkladem může být relace „je sourozenec“. Je-li i 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 a současně , pak platí .
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í , to znamená pokud je prvek v relaci sám se sebou. (Samozřejmě, že první pochází z množiny a druhé pochází z . 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 a současně , pak platí .

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[editovat | editovat zdroj]

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 (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
  • 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í alespoň v jedné z relací. Tedy R?S = {[x,y]; [x,y]?R ? [x,y]?S}