Relace

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 Aⁿ. Pro relaci R značením R(x₁, … , x_n) rozumíme (x₁, … , x_n) ∈ R.

Binární relace

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$ je $2^{mn}$. Více o počtu relací v samostatném článku.

Inverzní relace

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, $M_R^{−1} = (M_R)^T$.

Složení relací

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í

Reflexivita (RE)

$∀x ∈ X: xRx ⇔ ∀x ∈ X: R(x, x) ⇔ Δ_x ⊆ R$

Počet všech (i)reflexivních relací na n prvkové množině je $2^{n^2−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).

Ireflexivita (IR)

$∀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: $(R^2 ⊆ R ∧ S^2 ⊆ 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: $(R^2 ⊆ R ∧ S^2 ⊆ 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⁻¹.

Může být relace symetrická i antisymetrická zároveň? Ano! Každá $R ⊆ Δ_x$ tohle splňuje.

VĚTA: Nechť R je relace na množině A, nechť S je restrikce R na nějakou B ⊆ A. Jestliže má R nějakou z vlastností RE, SY, TR, ANS, tak ji má S také.

Přechodem k podmnožině na které se relace provádí, se tyto vlastnosti nezkazí. Jestliže nějaká vlastnost neplatí pro restrikci R, pak nesmí platit ani pro původní relaci S. Toto tvrzení, ale nemá tvar ekvivalence, čili, se může stát, že R nějakou vlastnost nemá, ale přechodem k S ji získá.

VĚTA: Nechť R je binární relace na množině X. Potom

• $R ∪ Δ_x$ je nejmenší reflexivní relace obsahující relaci R
• $R ∪ R^{-1}$ je nejmenší symetrickou relací obsahující relaci R
• $R^+$ je nejmenší tranzitivní relace obsahující relaci R
• $R - Δ_x$ je největší ireflexivní relace obsažená v relaci R.

Mocnina a tranzitivní uzávěr relace

Díky asociativnosti a existenci inverze má pro relaci $R ⊆ X × X$ smysl zavést celočíselnou mocninu R^n.

DEFINICE: Tranzitivní úzávěr $R^+$, resp. reflexivně-tranzitivní uzávěr $R^*$ relace R jsou definovány vztahy: $R^+ = ∪_i=1^\infty R^i = R^1 ∪ R^2$ $R^* = Δ_x ∪ R^+$

K čemu je tranzitivní uzávěr?

xRy: x je na jeden "krok" xR^+y: x je na libovolný počet "kroků"

Odvodíme předpis pro relaci $R^2: a(R^2)b ⇔ a(R ◦ R)b ⇔ ∃x ∈ Z : aRx ∧ xRb$

tranzitivní uzávěr trochu jinak Video https://www.youtube.com/watch?v=BKi8Ss_E2Ok hodina 6 min

Ekvivalence

DEFINICE: Ekvivalence ⇔ R je reflexivní, symetrická a tranzitivní. Příklad: Relace rovnosti =, kongruence ≡ (mod p)