Relace
Relace na množinách A1, A2, . . ., An je libovolná podmnožina kartézského součinu A1 x A2 x ... x An
Kartézský součin množin A a B, označovaný A × B, je množina všech uspořádaných dvojic, kde první prvek z dvojice patří do množiny A a druhý do množiny B. Příklad: {a, b} × {a, b, c} = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c)}
Je-li kartézský součin ze dvou množin (n=2), jde o binární relaci, v případě tří množin jde o relaci ternální, atd. Pokud jsou množiny kartézského součinu shodné jde o relaci homogení v opačném případě, jde o heterogenní relaci.
Na obrázku vidíme příklady binárních homogenních relací, protože kartezská součin AxA je dán dvěma shodnými množinami.
Vlastnosti relací
Binární relace R ⊆ A × A je:
- reflexivní, jestliže pro všechna a ∈ A platí (a, a) ∈ R.
Relací musí obahovat celou osu kartézského součinu (obr. šedá relace R6). - ireflexivní, jestliže pro všechna a ∈ A platí (a, a) ∉R.
Relací nesmí obsahovat ani kousek osy kartézského součinu (obr. R4, R5). - symetrická, jestliže pro všechna a, b ∈ A platí, že pokud (a, b) ∈ R, pak
(b, a) ∈ R.
Relace je symetrická podle osy kartézského součinu (obr. R1, R5). - asymetrická, jestliže pro všechna a, b ∈ A platí, že pokud (a, b) ∈ R, pak (b, a) ∉ R.
Relace se nachází pouze v jedné polovině kart. součinu rozděleného osou, přičemž se nesmí dotýkat osy (obr. R4). - antisymetrická, jestliže pro všechna a, b ∈ A platí, že pokud (a, b) ∈ R a (b, a) ∈ R, pak a = b.
Relace se nachází pouze v jedné polovině kart. součinu rozděleného osou a může obsahovat osu. - tranzitivní, jestliže pro všechna a, b, c ∈ A platí, že pokud (a, b) ∈ R a (b, c) ∈ R, pak (a, c) ∈ R.