Relace

@andrea@andrea

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 A1,A2,,AnA_1, A_2, … , A_n, kde n ≥ 1 pak kartézským součinem rozumíme množinu i=1nAi=A1×A2××An\prod\limits_{i=1}^n A_i = A_1 \times A_2 \times … \times A_n ={(a1,a2,,an);aiAi,i=1,2,,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 AiA_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

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:vyˊrokoa,b}R = \{(a, b) ∈ X × X : „výrok o a, b“\} nebo RZ×Z;aRbR ⊆ Z × Z; aRb ⇔ „výrok o a, b“.

Počet relací

Celkový počet mezi dvěma množinama A a B, A=m|A| = m, B=n|B| = n je 2mn2^{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 R1,Y,X⟨R^{-1}, Y, X⟩, kde

R1={(b,a);(a,b)R}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, MR1=(MR)TM_R^{−1} = (M_R)^T.

Složení relací

Složení (součin) relací. Nechť (R,X,Y)(R, X, Y) a (R,Y,Z)(R, Y, Z) jsou binární relace. Potom binární relací RS,X,Z⟨R ⚬ S, X, Z⟩ definovanou předpisem

a(RS)c=yY(aRyySc)a(R ⚬ S)c = ∃y ∈ Y (aRy ∧ ySc)

nebo jinak řečeno a(RS)ca(R ⚬ S)c, jestliže existuje bYb ∈ Y takové, že aRbaRb a bScbSc.

RS=(a,c)A×C:bB:(a,b)R(b,c)SR ⚬ 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, X, Y⟩, ⟨S, Y, Z⟩, ⟨T, Z, V⟩ (RS)T=R(ST)(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,TR, S, T jsou libovolné relace na množině XX. Potom platí

(RS)1=R1S1(R ∪ S)^{-1} = R^{-1} ∪ S{-1}

(RS)1R1S1(R ∩ S)^{-1} ⇒ R^{-1} ∩ S^{-1}

(RS)1=S1R1(R ⚬ S)^{-1} = S^{-1} ○ R^{-1}

(RS)=(RT)(ST)(R ⊆ S) = (R ⚬ T) ⇒ (S ⚬ T)

Vlastnosti binárních relací

Reflexivita (RE)

xX:xRxxX:R(x,x)ΔxR∀x ∈ X: xRx ⇔ ∀x ∈ X: R(x, x) ⇔ Δ_x ⊆ R

Počet všech (i)reflexivních relací na n prvkové množině je 2n2n2^{n^2−n}

Sjednocení dvou RE relací je RE: (XRXS)X(RS)(∆_X ⊆ R ∧ ∆_X ⊆ S) ⇒ ∆_X ⊆ (R ∪ S).

Protože platí ∆X = ∆X ∪ ∆X ⊆ R ∪ S. Průnik dvou RE relací je RE: (XRXS)X(RS)(∆_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)

xX:¬(xRx)xX:¬R(x,x)RΔx=∀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)

xX:xRyyRx;R1=R∀x ∈ X: xRy ⇒ yRx; R^{−1} = R

Sjednocení dvou SY relací je SY: (R1=RS1=S)(RS)1=(RS)(R^{−1} = R ∧ S^{−1} = S) ⇒ (R ∪ S)^{−1} = (R ∪ S). Platí

Průnik dvou SY relací je SY: (R1=RS1=S)(RS)1=R1S1=RS(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)}R = \{(a, b),(b, a)\}, S = \{(b, b)\}. Složení RS=(a,b)R ◦ S = {(a, b)} symetrické není.

Antisymetrie (SY) (AN/ANS)

xX:xRyyRxx=y;(RR1)Δx∀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: (R1RX)(R1SX)(R^{−1} ∩ R ⊆ ∆_X) ∧ (R^{−1} ∩ S ⊆ ∆_X)

Protipříkladem je např. antisymetrické relace R=(a,b),S=(b,a)R = {(a, b)}, S = {(b, a)}. Jejich sjednocení RS=(a,b),(b,a)R ∪ S = {(a, b),(b, a)} zřejmě antisymetrické není.

Průnik dvou AN relací je AN: (R1=RS1=S)(RS)1=R1S1=RS(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,bX = {a, b} a symetrické relace R=(a,b),(b,a),S=(b,b)R = {(a, b),(b, a)}, S = {(b, b)}. Složení RS=(a,b)R ◦ S = {(a, b)} symetrické není.

Asymetrie (AS) (silně antisymetrická)

xX:xRy¬(yRx);RR1=∀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)

xX:xRyyRxxRz;(RR)Rx ∈ X: xRy ∧ yRx ⇒ xRz; (R ⚬ R) ⊆ R

Sjednocení dvou TR relací není TR: (R2RS2S)(RS)2(RS).(R^2 ⊆ R ∧ S^2 ⊆ S) ⇒ (R ∪ S)^2 ⊆ (R ∪ S).

Protipříkladem je tranzitivní relace R=(a,b),S=(b,c)R = {(a, b)}, S = {(b, c)}. Sjednocení RS=(a,b),(b,c)R ∪ S = {(a, b),(b, c)} zjevně tranzitivní není.

Průnik dvou TR relací je TR: (R2RS2S)(RS)2(RS)(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)R = {(a, d),(b, c)}, S = {(c, a),(d, b)}. Složení RS=(a,b),(b,a)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ΔxR ⊆ Δ_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


Mocnina a tranzitivní uzávěr relace

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

DEFINICE: Tranzitivní úzávěr R+R^+, resp. reflexivně-tranzitivní uzávěr RR^* relace R jsou definovány vztahy: R+=i=1Ri=R1R2R^+ = ∪_i=1^\infty R^i = R^1 ∪ R^2 R=ΔxR+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 R2:a(R2)ba(RR)bxZ:aRxxRbR^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)