Binární relace na množině

Binární relací na množině rozumíme binární relaci definovanou mezi dvěma stejnými množinami.

Příklady

Binární relace na množině je speciální typ binární relace, kdy obě nosné množiny jsou stejné. Binární relace na množině tak je relace R taková, že R ⊆ M × M.

Relace „větší než“ je binární relace na množině, protože na obou stranách pracujeme s čísly. Tedy platí, že > ⊆ ℝ × ℝ. Relace „otec — počet dětí“ není binární relace na množině, protože otce vybíráme z množiny všech lidí, kdežto počet dětí vybíráme z nějaké číselné množiny.

Vlastnosti

Binární relace R na množině M může mít některé zajímavé vlastnosti. Říkáme, že relace R je…

• reflexivní, pokud pro všechna a ∈ M platí, že [a, a] ∈ R.
• symetrická, pokud pro všechna a, b ∈ M platí, že je-li [a, b] ∈ R, pak i [b, a] ∈ R.
• antisymetrická, pokud pro všechna a, b ∈ M platí, že pokud je [a, b] ∈ R a zároveň je i [b, a] ∈ R, pak a = b.
• transitivní, pokud pro všechna a, b, c ∈ M platí, že pokud [a, b] ∈ R a zároveň [b, c] ∈ R, pak i [a, c] je v R.

Příklady reflexivity

Reflexivita znamená, že je prvek v relaci sám se sebou. Typickým příkladem je rovnost. Pokud máme definovanou rovnost na přirozených číslech, že jistě platí, že pro jakýkoliv prvek a: a = a. Dalším příkladem může být dělitelnost. Tam opět platí, že číslo a je dělitelné samo sebou, tedy dvojice [a, a] je v relaci dělitelnosti (sedmička dělí sedmičku).

Relace menší než už ovšem reflexivní není, protože neplatí, že a < a. To není možné, sedmička nemůže být menší než sedmička. Podobně relace být otcem svého dítěte — nemůžu být svým vlastním otcem. Takové relace reflexivní nejsou.

Důležité je, že reflexivita musí platit pro všechny prvky, nestačí najít jen některé. Například relace "mít někoho rád". Můžu mít jednak rád někoho, například revizora, ale můžu mít rád i sebe. Jistě se najde člověk, který má rád sebe. Ale stejně tak se najde člověk, který sám sebe nemá rád. Taková relace pak není reflexivní — všichni lidé by museli mít rádi sami sebe.

Příklady symetrie

U symetrické relace platí, že pokud je v relaci nějaká dvojice, pak je v relaci i inverzní dvojice. Například relace být sourozencem. Pokud je Honza sourozenec Jany, pak je i Jana sourozencem Honzy. Z číselných relací by to mohla být relace "býti opačným číslem". Tím myslím dvojice 2 a −2 nebo −7 a 7. Jsou to taková dvě čísla, která v součtu dají nulu. Taková relace je symetrická, protože na pořadí zkrátka nezáleží: [2, −2] a [−2, 2] jsou stále navzájem opačná čísla a v součtu dávají nulu.

Relace, která není symetrická, je menší než (nad reálnými čísly). Ta nemá ani jeden symetrický prvek, protože nikdy nemůže platit a < b a zároveň b < a. Pokud je 5 < 15, tak nemůže platit 15 < 5. Dále není symetrická relace "býti otcem svého syna". Můžete být otcem svého syna, ale pak už syn nemůže být otcem svého otce.

Tato vlastnost musí opět platit pro všechny případy. Pokud má být relace "mít někoho rád" (na množině všech lidí) symetrická, tak pokud já mám rád Agátu Hanychovou, tak by zároveň Aguš musela mít ráda mě. A protože mě ani nezná, tak nemůžu říci, že mě má ráda, což je škoda a relace není symetrická. Což je taky škoda.

Příklady antisymetrie

Klasickým příkladem antisymetrické relace je menší nebo rovno. Antisymetrie nám říká, že pokud jsou prvky [a, b] a [b, a] v relaci, pak jedině, když jsou si rovny, a = b. Relace menší nebo rovno to splňuje. Kdy platí a ≤ b a zároveň b ≤ a? Jedině v případě, že a = b. Když si dosadíme: platí 3 ≤ 5 a zároveň 5 ≤ 3? Ne. Ale platí 4 ≤ 4 a zároveň 4 ≤ 4.

Příkladem relace, která není antisymetrická, můžou být dvojice slov, která mají stejnou délku, například [sobota, sekera]. Taková relace není antisymetrická, protože nalezneme dvojici slov, která jsou v relaci, jejich inverzní prvek je taky v relaci a přitom jsou obě slova různá. Takže už zmíněný prvek [sobota, sekera] a jejich inverze: [sekera, sobota]. Obě jsou zřejmě v naší relaci, ale přitom sobota ≠ sekera, takže relace není antisymetrická.

Příklad transitivity

Transitivní je relace menší než. Transitivita nám říká, že pokud 3 < 4 a zároveň 4 < 5, tak potom musí jistě platit i 3 < 5. Pro spoustu relací je to poměrně přirozená vlastnost. Podobně pro příklad se stejnou délkou slov. Pokud jsou v relaci [sekera, sobota] a jsou v relaci [sobota, poleno], pak jsou v relaci i slova [sekera, poleno].

Transitivní není relace být otcem syna. Pokud je Tonda otcem Franty a Franta je otcem Mirka, tak Tonda není otcem Mirka, je jeho dědečkem. Podobně není transitivní relace mít někoho rád. Pokud mám rád Agátu a Agáta má ráda svého manžela, tak to neznamená, že i já mám rád Agátina manžela.

Transitivita se také řeší u klasických hracích kostek. Předpokládejme relaci kostka A je lepší než kostka B, pokud na kostce A padne častěji (s větší pravděpodobností) vyšší číslo než na kostce B. Je taková relace transitivní? Na to odpovídá článek netransitivní kostky.

Ekvivalence a uspořádání

Některé speciální typy binárních relací mají i svá jména:

• Ekvivalence je relace, která je reflexivní, symetrická a transitivní.
• Uspořádání je relace, která je reflexivní, antisymetrická a transitivní.