Domů » Matematika » Relace

Relace

Množina R je relace na množinách A1 až An právě když jsou všechny její prvky uspořádané n-tice prvků po řadě z množin A1 až An. Relaci lze definovat i pomocí kartézského součinu. Relace na množinách A1 až An je libovolná podmnožina kartézského součinu množin A1 až An, tedy platí € R \subseteq A_1 \times \ldots \times A_n €. Protože je relace množina, lze na ní aplikovat všechny operace i vlastnosti, které platí pro množinu.

Binární relace

Množina R je binární relace na množinách A a B právě tehdy když jsou všechny její prvky uspořádané dvojice prvků z množiny A a B, tedy platí € R \subseteq A \times B €. Z toho vyplývá, že z výsledku lze vypátrat i původní dvojici hodnot. Jinak zapsáno platí, že € \forall z \in R \;\exists\; x,y : z = (x, y) €.

Množina všech prvků x se nazývá definiční obor (domain) relace R, množina všech prvků y je obor hodnot (range) relace R.

€€ D_R = \{x \;|\; (x, y) \in R\} €€ €€ R_R = \{y \;|\; (x, y) \in R\} €€

Skutečnost, že nějaká dvojice prvků leží v relaci, lze zapisovat různými způsoby.

€€ (a,b) \in R \sim a R b \sim R(a,b) €€
Podrelace

Jako podrelace relace R se označuje každá relace S, pro kterou platí, že € S \subseteq R €.

Inverzní relace

Jako inverzní relace k relaci R se označuje každá relace S, pro kterou platí, že € x S y \leftrightarrow y R x €.

Vlastnosti

Reflexivita

Reflexivní relace vyjadřuje, že je každý prvek ve vztahu sám se sebou.

€€ \forall x \; R(x,x) €€

příklad reflexivní relace

Antireflexivita

Antireflexivní (ireflexivní) relace vyjadřuje, že prvek není nikdy ve vztahu sám se sebou.

€€ \forall x \; \lnot R(x,x) €€
Symetrie

Symetrická relace vyjadřuje vzájemný vztah dvou prvků.

€€ \forall x,y \; (R(x,y) \rightarrow R(y,x)) €€

příklad symetrické relace

Antisymetrie

Antisymetrická relace vyjadřuje vztah, který není opětován.

€€ \forall x,y \; ((R(x,y) \land R(y,x)) \rightarrow (x=y)) €€
Asymetrie

Asymetrická relace se někdy označuje jako silně antisymetrická.

€€ \forall x,y \; (R(x,y) \rightarrow \lnot R(y,x)) €€
Tranzitivita

Tranzitivní relace vyjadřuje přenos vztahu mezi prvky.

€€ \forall x,y,z \; ((R(x,y) \land R(y,z)) \rightarrow R(x,z)) €€

příklad tranzitivní relace

Intranzitivita

Intranzitivní relace vyjadřuje, že se vztah mezi prvky nikdy nepřenáší.

€€ \forall x,y,z \; ((R(x,y) \land R(y,z)) \rightarrow \lnot R(x,z)) €€
Konexnost

Konexní relace vyjadřuje, že jsou všechny prvky propojeny sítí vztahů.

€€ \forall x,y \; ((x \neq y) \rightarrow (R(x,y) \lor R(y,x))) €€
Inkonexnost

Inkonexní relace vyjadřuje, že existují takové dva různé prvky, které mezi sebou nemají žádný vztah.

€€ \exists x,y \; ((x \neq y) \land \lnot R(x,y) \land \lnot R(y,x)) €€

Uzávěry

Reflexivní uzávěr

Reflexivní uzávěr relace R je nejmenší reflexivní relace S (ve smyslu počtu prvků) taková, že R je podrelace (podmnožina) S.

Symetrický uzávěr

Symetrický uzávěr relace R je nejmenší symetrická relace S (ve smyslu počtu prvků) taková, že R je podrelace S.

Tranzitivní uzávěr

Tranzitivní uzávěr relace R je nejmenší tranzitivní relace S (ve smyslu počtu prvků) taková, že R je podrelace S.

příklad tranzitivního uzávěru

Speciální relace

Relace ekvivalence

Relace R je relace ekvivalence právě když je reflexivní, symetrická a tranzitivní.

Relace uspořádání

Relace R je relace uspořádání právě když je reflexivní, antisymetrická a tranzitivní.

Relace ostrého uspořádání

Relace R je relace ostrého uspořádání právě když je ireflexivní, antisymetrická a tranzitivní.

Reference