Počet relací

Binární relace jsou definovány jako podmnožiny kartézského součinu.

Vhodný postup pro určení počtu relací je

1. uvědomit si, kolik prvků může mít samotná relace
2. kolik možností výběru pro každý prvek máme

Mějme tedy konečné množiny $A$ a $B$ u kterých známe jejich počty prvků (mohutnost) $|A| = m$, $|B| = n$.

Velkou výhodou relací je, že se dají intuitivně reprezentovat pomocí matice, která má $n$ rádků a $m$ sloupců. Protože každý prvek matice může nabývat dvou hodnot (buď je v relaci, nebo není), vzniká nám pro $n \cdot m$ prvků vzorec $2^{mn}$.

Celkový počet relací $A×B$ je tedy $2^{mn}$

Reflexivní relace

Pokud máme relaci, která je definována jako podmnožina množiny $A × A$ (stejné množiny), pak reflexivní relací myslíme relaci obsahují každý prvek $(a, a)$. Tedy každý prvek je v relaci sám se sebou.

Například tato relace $R$, z množiny $A$ s prvky $\{1,2,3\}$ je reflexivní.

V této matici odpovídají hodnoty 1 přítomnosti $(a, a), (b, b)$ a $(c, c)$ v relaci. Hodnoty 0 znamenají, že ostatní páry nejsou v relaci. Nicméně toto není jediná varianta reflexivní tříprvkové množiny, představili jsme si nejmenší.

V obecném případě má množina $A$ prvků $n$ a reflexivní relace musí obsahovat i $n$ prvků tvaru $(a, a)$. Celá relace z $A × A$ obsahuje $n^2$ prvků. Z této úvahy bysme měli vidět, že nám zbývá $(n^2 - n)$ prvků, které mohou, ale nemusí být v relaci.

Takže existuje $2^{n^2 - n}$ možností, jak tyto prvky zařadit do relace.

Symetrická relace

Pro symetrickou relace na množině $A$ platí, že pokud $(a, b)$ je v relaci, pak také $(b, a)$ musí být v relaci.

Každou symetrickou relaci kterou reprezentujeme jako matici, je symetrická podél hlavní diagonály. To znamená, že pokud známe prvky pod hlavní diagonálou (nebo nad ní), můžeme určit celou matici.

Máme $\frac{n(n + 1)}{2}$ prvků na hlavní diagonále a pod ní (včetně diagonály), protože je to součet prvků v aritmetické posloupnosti od 1 do n.

Počet možných symetrických relací je tedy $2^{\frac{n(n + 1)}{2}}$ na množině s $n$ prvky. Pokud máte rádi kombinační číslo, tak totožně $2^{{n+1}\choose 2}$

Ireflexivní relace

Tento případ je obdobou reflexivní relace, akorát všechn $n$ prvků tvaru (a, a) nesmí být součástí relace.

Asymetrická relace

Důležitá vlastnost asymetrických relací je, že nemohou obsahovat žádné dvojice tvaru (a, a) - tedy, nemohou být reflexivní.

Musíme odečíst všechny možné reflexivní relace a všechny možné kombinace dvojic (a, b) a (b, a). Každý prvek v množině může být v relaci s n - 1 ostatními prvky (ne sám se sebou, kvůli asymetrii).

Takže máme $2^{n*(n - 1)}$ asymetrických relací.

Antisymetrická

Antisymetrická relace je taková relace, ve které pokud (a, b) je v relaci a a≠b, pak (b, a) není v relaci.

Musíme omezit možné kombinace dvojic symetrie. Pro každou dvojici (a, b) a (b, a) máme 3 možnosti - buď je v relaci (a, b), nebo (b, a), nebo ani jedna. Máme tedy $3^\frac{n(n-1)}{2}$ možností pro tyto dvojice.

Celkový počet antisymetrických relací je tedy $2^n * 3^\frac{n(n-1)}{2}$.