Pojem relace je matematickým vyjádřením používaného pojmu vztah. Relace jsou množiny. Proto s nimi lze provádět množinové operace (∩,∪) a lze na ně aplikovat vztah rovnosti a inkluze (=,⊆).
Formální definice
Pro definici relace, potřebujeme nejprve definovat kartézský součin.
Mějme množiny $A_1, A_2, … , A_n$, kde n ≥ 1 pak kartézským součinem rozumíme množinu $$\prod\limits_{i=1}^n A_i = A_1 \times A_2 \times … \times A_n$$ $$= \{(a_1, a_2, … , a_n); a_i \in A_i, i = 1, 2, … , n\}.$$ tedy množinu všech uspořádaných n-tic, jejichž i-té složky jsou prvky z $A_i$.
Arita relace
Číslo udávající počet množin, které do relačního vztahu vstupují.
Pojmem n-ární relace (n≥1) rozumíme podmnožinu kartézského součinu An. Pro relaci R značením R(x1, … , xn) rozumíme (x1, … , xn) ∈ R.
Binární relace
DEFINICE: Nechť A, Y jsou množiny a R ⊆ A × Y. Trojice ⟨R, A, Y⟩ se nazývá binární relace z A do Y. Množinu A nazýváme, levým oborem a množinu Y pravým oborem.
Značení „aRb" a „(a,b) ∈ R", jsou zcela rovnocenné. „aRb" je zkratka pro logický výrok „platí (a,b) ∈ R". Relace zachycuje, že existuje nějaký vztah.
Definiční obor D(R) = {x ∈ X; (∃y ∈ Y) xRy}
Obor hodnot H(R) = {y ∈ Y; (∃x ∈ X) yRx}.
U relací nepoužíváme některé pojmy běžně definované pro zobrazení, a to „obraz“ a „vzor“. Ty u obecných relací nemají smysl a o dvou prvcích lze pouze říci, jestli jsou nebo nejsou v relaci R.
Jak zadat relaci?
Definice: je tvaru R = {(a, b) ∈ X × X : „výrok o a, b“} nebo R ⊆ Z × Z; aRb ⇔ „výrok o a, b“.
Počet relací
Celkový počet mezi dvěma množinama A a B, |A| = m, |B| = n. 2mn.
představa tabulky nxm a pro každou buňku rozhoduju zda relace existuje nebo ne.
Počet symetrických relací je 2{n+1}\choose 2
Inverzní relace
DEFINICE: Inverzní relace. Nechť ⟨R, X, Y⟩ je binární relace. Potom inverzní relací k této relaci rozumíme binární relaci ⟨R-1, Y, X⟩, kde R-1 = {(b,a); (a,b) ∈ R}
Například: Inverzní relace k ⟨≤, X, Y⟩ je ⟨≥, X, Y⟩.
V maticové reprezentaci má inverzní relace matici transponovanou k matici původní relace, MR−1 = (MR)T.
Složení relací
DEFINICE: Složení (součin) relací. Nechť (R, X, Y) a (R, Y, Z) jsou binární relace. Potom binární relací ⟨R ⚬ S, X, Z⟩ definovanou předpisem
a(R ⚬ S)c = ∃y ∈ Y (aRy ∧ ySc)
nebo jinak řečeno a(R ⚬ S)c, jestliže existuje b ∈ Y takové, že aRb a bSc.
R ⚬ S = {(a,c) ∈ A×C: ∃b ∈ B:(a,b)∈ R ∧ (b,c) ∈ S}
Aby dvojice (a, c) ∈ R ⚬ S, musí se musí platit, aRbSc
Složení relací není komutativní.
VĚTA: Složení relací je asociativní.
Mějme relace ⟨R, X, Y⟩, ⟨S, Y, Z⟩, ⟨T, Z, V⟩
(R ⚬ S) ⚬ T = R ⚬ (S ⚬ T)
- DŮKAZ: x((R ⚬ S) ⚬ T)z ⇔ ∃z ∈ Z: (xR⚬Sz) ∧ zTu ⇔ ∃z ∈ Z: (∃y ∈ Y: xRy ∧ ySz) ∧ zTu ⇔ ∃y ∈ Y: ∃z ∈ Z: xRy ∧ (ySz ∧ zTu) ⇔ ∃y ∈ Y: xRy ∧ (∃z ∈ Z: ySz ∧ zTu) ⇔ xR ⚬ (S ⚬ T)u
Omezíme se na relace v množině X
VĚTA: Nechť R, S, T jsou libovolné relace na množině X. Potom platí
- (R ∪ S) ⚬ T = (R ⚬ T) ∪ (S ⚬ T)
DŮKAZ: x((R ∪ S) ⚬ T)z ⇔ ∃y: (xR∪Sy) ∧ yTz ⇔ ∃y: ((xRy) ∨ (xSy)) ∧ yTz ⇔ ∃y: ((xRy) ∧ (yTz)) ∨ ((xSy)∧(yTz)) ⇔ ∃y: (xRy) ∧ (yTz) ∨ ∃y: (xSy) ∧ (yTz) ⇔ x(R ⚬ T)z ∨ x(S ⚬ T)z ⇔ x(R ⚬ T) ∪ (S ⚬ T)z
- (R ∪ S)-1 = R-1 ∪ S-1
- (R ∩ S)-1 => R-1 ∩ S-1
- (R ⚬ S)-1 = S-1 ○ R-1
- (R ⊆ S) = (R ⚬ T) => (S ⚬ T)
Vlastnosti binárních relací
∀x ∈ X: xRx ⇔ ∀x ∈ X: R(x, x) ⇔ Δx ⊆ R
Počet všech (i)reflexivních relací na n prvkové množině je 2n2−n
Sjednocení dvou RE relací je RE: (∆X ⊆ R ∧ ∆X ⊆ S) ⇒ ∆X ⊆ (R ∪ S).
Protože platí ∆X = ∆X ∪ ∆X ⊆ R ∪ S.
Průnik dvou RE relací je RE: (∆X ⊆ R ∧ ∆X ⊆ S) ⇒ ∆X ⊆ (R ∩ S).
Protože platí ∆X = ∆X ∩ ∆X ⊆ R ∩ S.
Složení dvou RE relací je RE: (∆X ⊆ R ∧ ∆X ⊆ S) ⇒ ∆X ⊆ (R ◦ S).
Platí (∆X ⊆ R ∧ ∆X ⊆ S) ⇒ ∆X ⊆ (R ◦ S).
∀x ∈ X: ¬(xRx) ⇔ ∀x ∈ X: ¬R(x, x) ⇔ R ∩ Δx = {}
Reflexivní relace má na všech vrcholech smyčky, ireflexivní nesmí mít žádnou smyčku.
Symetrie (SY)
∀x ∈ X: xRy ⇒ yRx; R−1 = R
Sjednocení dvou SY relací je SY:
(R−1 = R ∧ S−1 = S) ⇒ (R ∪ S)−1 = (R ∪ S). Platí.
Průnik dvou SY relací je SY:
(R−1 = R ∧ S−1 = S) ⇒ (R ∪ S)−1 = R−1 ∩ S−1 = R ∩ S, Platí.
Složení dvou SY relací není SY!
Protipříklad např. Symetrické relace R = {(a, b),(b, a)}, S = {(b, b)}. Složení R ◦ S = {(a, b)} symetrické není.
Antisymetrie (SY) (AN/ANS)
∀x ∈ X: xRy ∧ yRx ⇒ x = y; (R ∩ R−1) ⊆ Δx
Vlastnosti symetrie a antisymetrie nejsou opačné ani navzájem se vylučující.
Sjednocení dvou AN relací není AN:
(R−1 ∩ R ⊆ ∆X) ∧ (R−1 ∩ S ⊆ ∆X)
Protipříkladem je např. antisymetrické relace R = {(a, b)}, S = {(b, a)}. Jejich sjednocení R ∪ S = {(a, b),(b, a)} zřejmě antisymetrické není.
Průnik dvou AN relací je AN:
(R−1 = R ∧ S−1 = S) ⇒ (R ∪ S)−1 = R−1 ∩ S−1 = R ∩ S, Platí.
Složení dvou SY relací není SY!
Jako jednoduchý protipříklad lze zvolit např. X = {a, b} a symetrické relace R = {(a, b),(b, a)}, S = {(b, b)}. Složení R ◦ S = {(a, b)} symetrické není.
Asymetrie (AS) (silně antisymetrická)
∀x ∈ X: xRy ⇒ ¬(yRx); R ∩ R−1 = {}
Asymetrická relace je ireflexivní.
V grafu se nevyskytuje žádná obousměrná hrana, ale smyčky se objevit mohou.
Každou hrana v diagramu má ohranu k ní opačnou. "Obousměrné šipky", neorientovaný graf má matici symetrickou.
Tranzitivita (TR)
x ∈ X: xRy ∧ yRx ⇒ xRz; (R ⚬ R) ⊆ R
Sjednocení dvou TR relací není TR:
(R2 ⊆ R ∧ S2 ⊆ S) ⇒ (R ∪ S)2 ⊆ (R ∪ S).
Protipříkladem je tranzitivní relace R = {(a, b)}, S = {(b, c)}. Sjednocení R ∪ S = {(a, b),(b, c)} zjevně tranzitivní není.
Průnik dvou TR relací je TR:
(R2 ⊆ R ∧ S2 ⊆ S) ⇒ (R ∩ S)2 ⊆ (R ∩ S)
TODO Důkaz
Složení dvou TR relací není TR!
Jako protipříklad uveďme tranzitivní relace R = {(a, d),(b, c)}, S = {(c, a),(d, b)}.
Složení R ◦ S = {(a, b),(b, a)} zjevně tranzitivní není.
Za každou cestu délky 2 existuje i hrana spojující její krajní vrcholy.
Úpravy relací
Pro (RE), (SY) a (TR) musíme relaci vhodně doplnit, pro (AN), (AS) a (IR) z ní musíme naopak něco odebrat
VĚTA: Má-li relace R na množině X některé z vlastností (RE) až (TR), pak tytéž vlastnosti má také inverzní relace R−1.
Může být relace symetrická i antisymetrická zároveň? Ano! Každá R ⊆ Δx tohle splňuje .