Binární relace

Binární relace je speciální typ relace s aritou dva. Mezi typické binární relace patří například menší než, rovnost, dělitelnost, větší než, apod.

Ukázky

Binární relace je jedna z typických a běžně se vyskytovaných relací. Zároveň má některé zajímavé vlastnosti, které si zde popíšeme.

Příkladem binární relace může být: vztah „otec — syn“, dvojice „dopravní prostředek — počet kol“ či obecnější „objekt — vlastnost objektu“. Objektem může být zvíře a vlastností počet nohou, průměrná délka života, počet chlupů na hlavě a podobně.

Binární relaci R mezi množinami M₁ a M₂ můžeme definovat takto: R ⊆ M₁ × M₂. Binární relace je tak množina dvojic, přičemž tato množina je podmnožinou kartézského součin dvou množin, mezi kterými relaci zavádíme. Takže relace „otec — syn“ může být relaci mezi množinami všech lidí, mezi množinami všech lidí v Evropě nebo v Praze. Množinu můžeme omezit i jiným směrem, můžeme říci, že tu relaci definujeme mezi množinami všech mužů, ne lidí obecně.

Pro binární relace obvykle používáme speciální značení. Místo toho, abychom psali [a, b] ∈ R, můžeme napsat aRb. Například místo [3, 1] ∈ > můžeme napsat 1 > 3. Podobně pro ostatní relace. Takže zápis aSb je ekvivalentní zápisu [a, b] ∈ S.

Inverzní relace

Inverzní relace je relace opačná k současné relace. (Pozor, neplést s doplňkem relace.). Jaká je opačná relaci k relaci menší než? Větší než. Pokud relace menší než obsahuje prvek [4, 7], tedy 4 < 7, tak inverzní prvek bude opačný: 7 > 4, v inverzní relaci bude inverzní dvojice [7, 4].

Máme-li relaci R ⊆ M₁ × M₂, tak inverzní relace R⁻¹ sestrojíme tak, že vezmeme všechny prvky [a, b] ∈ R a do R⁻¹ vložíme jejich inverzi. Tedy pokud relace R obsahuje prvek [a, b], tak relace R⁻¹ musí obsahovat prvek [b, a]. Platí to i naopak, pokud R⁻¹ obsahuje prvek [b, a], pak relace R musí obsahovat prvek [a, b].

Kdybychom to zadefinovali, tak relace R⁻¹ je inverzní k R právě když platí:

$$\forall a\in M_1,\forall b\in M_2:\quad [a, b]\in R \Leftrightarrow [b, a]\in R^{-1}$$

Platí tak, že 6 < 8 právě když 8 > 6. Podobně pro další dvojice.

Skládání relací

Binární relace můžeme mezi sebou skládat. Mějme dvě relace, první, R, bude „být otcem svého syna“ a druhá, S, „být bratrem své sestry“. Relace R tak obsahuje dvojice [otec, syn], druhá relace obsahuje dvojice [bratr, sestra].

V tuto chvíli zkusíme relace složit. Vznikne nám nová relace, označíme ji $R \circ S$, přičemž tato relace obsahuje prvek [a, c] právě když [a, b] ∈ R a zároveň [b, c] ∈ S. Všimněte si, že se v obou prvcích vyskytuje b, jednou na druhém místě a pak na prvním místě dvojice. To je jakýsi propojovací prvek skládání.

Příklad: R = {[Tonda, Marek], [Petr, Jakub]} a S = {[Marek, Jana], [Marek, Lenka], [Jakub, Lucie]}. Tonda je otcem Marka, Petr je otcem Jakuba. Marek má sestry Janu a Lenku a Jakub má sestru Lucii.

Nyní složíme relace: $R \circ S$. Hledáme takovou dvojici z R, která má na místě syna někoho, kdo je veden jako bratr v relaci S. Například tyto dvě dvojice: [Tonda, Marek] a [Marek, Jana]. Marek je propojovací element, ten dále nepotřebujeme a ze zbylých jmen vytvoříme novou dvojici: [Tonda, Jana]. Relace $R \circ S$ tak obsahuje dvojici [Tonda, Jana]. Marek má ještě jednu sestru, Lenku, tu také přidáme do složené relace: [Tonda, Lenka]. Nakonec zbývá syn Jakub. Ten má sestru Lucii. Takže máme dvě dvojice: [Petr, Jakub] a [Jakub, Lucie]. Tím vytvoříme další prvek: [Petr, Lucie].

Výsledkem je relace: $R \circ S = {[Tonda, Jana], [Tonda, Lenka], [Petr, Lucie]}$. Jak bychom mohli tuto relaci pojmenovat? Nejspíše „být otcem své dcery“.

Ještě jednou celá definice:

$$[a, c] \in (R \circ S) \Leftrightarrow \exists b\quad [a, b] \in R \wedge [b, c] \in S$$

Poznámka: někdy se používá obrácený zápis, to znamená, že pro stejnou definici by se místo $R \circ S$ použilo $S \circ R$.