Relacije predstavljaju veze (odnose) između izvesnih objekata. Najčešće se radi o vezi dva objekta, to su binarne relacije. U matematici se relacije definišu skupovnom terminologijom.
Definicija
Za ρ kažemo da je binarna relacija r na skupu A ako je ρ ⊆ A2.
Ako (a, b) ∈ ρ kažemo da je a u relaciji ρ sa b i pišemo a ρ b, ako (a, b) ∉ρ kažemo da a nije u relaciji ρ sa b i pišemo aρb.
Relacija ρ = ∅ je prazna relacija, a r = A2 je puna relacija.
Primer:
Na skupu A = {1, 2, 3} primeri binarnih relacija su
ρ1 = {(1, 1), (2, 2), (3, 3)}, tj. ρ _1 = ” = ” (jednakost u skupu A)
ρ2 = {(1, 2), (1, 3), (2, 3)}, tj. ρ _2 = ” < ”.
Svakoj binarnoj relaciji r skupa A odgovara funkcija fr: A2 → {1, 0}, data na sledeći načinkoja se zove karakteristična funkcija relacije ρ.
Dakle, binarnu relaciju možemo zadati i njenom karakterističnom funkcijom. U slučaju konačnog skupa A, funkciju fρ obično zadajemo tablicom.
Neka je A = {a, b, c, d, e}. Binarnu relaciju ρ možemo zadati navođenjem elemenata, npr.
- r = {(a, a), (a, c), (b, a), (c, a), (c, b), (d, d), (d, e)}
- tablicom karakteristične funkcije
Primer
(1) Relacija ρ = {2, 4, 6, . . . } ⊆ N je unarna relacija skupa N. Ona izražava osobinu „biti paran broj“.
(2) ρ = {(x, y, z)|x +y = z} ⊆ N3 je ternarna relacija skupa N.
(3) Ako je A skup tačaka na pravoj, onda se svojstvom „x je između y i z“ definiše jedna ternarna relacija na A.
Primer
Primenom skupovnih operacija na relacije ρ1 = {(1, 1), (2, 2), (3, 3)} i ρ2 = {(1, 2), (1, 3), (2, 3)} dobijamo
ρ1 ∪ ρ2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)} = ” ≤ ”,
ρ1∩ ρ2 = ∅,
A2 ρ1 = {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)} = ” ≠ ”,
A2ρ2= {(1, 1), (2, 1), (3, 1), (2, 2), (3, 2), (3, 3)} = ” ≥ ”.
= {2, 4, 6, . . . } ⊆ N je unarna relacija skupa N. Ona izražava
osobinu „biti paran broj“.
(2) ρ = {(x, y, z)|x +y = z} ⊆ N3 je terarna relacija skupa N.
(3) Ako je A skup tačaka na pravoj, onda se svojstvom „x je između y i z“
definiše jedna ternarna relacija na A.
Osnovne osobine koje binarna relacija može imati su: refleksivnost, simetričnost, antisimetričnost i tranzitivnost.
Definicija
Binarna relacija ρ skupa A je:
(R) refleksivna ako (∀ x ∈ A) x ρ x;
(S) simetrična ako (∀ x, y ∈ A) (x ρ y ⇒ y ρ x);
(A) antisimetrična ako (∀ x, y ∈ A) (x ρ y ∧ y ρ x ⇒ x = y);
(T) tranzitivna ako (∀ x, y, z ∈ A) (x ρ y ∧ y ρ z⇒x ρ z).
Jedina relacija skupa A koja ima sve četiri navedene osobine (RSAT) je relacija jednakosti.
Primer
(1) Na skupu A = {1, 2, 3}
- ρ1 = {(1, 1), (1, 2), (1, 3)} je (A) i (T), a nije (R), niti (S);
- ρ 2 = {(1, 2), (2, 1)} je (S), a nije (R), nije (A) i nije (T);
- ρ 3 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} je (R), (S) i (T).
(2) Neka je na skupu S definisana relacija r na sledeći način:
x ρ y akko x poznaje y.
Ova relacija je (R) i (S), a nije (A), niti (T).
Relacije ekvivalencije
Definicija
Binarna relacija ρ skupa A je relacija poretka ako je refleksivna, simetrična i tranzitivna (RAT).
Definicija
Binarna relacija ρ skupa A je relacija ekvivalencije ako je refleksivna, simetrična i tranzitivna (RST).
Relacija ekvivalencije se obično označava sa ∼ (čita se tilda). Primeri relacija ekvivalencije: jednakost (na bilo kom skupu), paralelnost pravih u ravni,. . .
Definicija
Neka je ∼ relacija ekvivalencije skupa A i a ∈ A. Skup zove se klasa ekvivalencije elementa u odnosu na relaciju ∼.
zove se klasa ekvivalencije elementa a u odnosu na relaciju ∼.
Osobine klasa ekvivalencije
Teorema
Neka je ∼ relacija ekvivalencije skupa A. Tada
(1) Ca , ∅, za sve a ∈ A (tj. svaka klasa ekvivalencije je neprazan skup);
(2) a ∼ b akko Ca = Cb (tj. dva elementa imaju istu klasu ekvivalencije akko su
u relaciji)
(3) a / b akko Ca ∩ Cb = ∅; (tj. dva elementa nisu u relaciji akko su im klase disjunktne)
(4) A = ∪a∈ACa (unija svih klasa ekvivalencije jednaka je celom skupu A.)
Primer
(1) Paralelnost pravih je relacija ekvivalencije na skupu svih pravih neke ravni α.
Klasu ekvivalencije prave p čine sve prave date ravni koje su paralelne sa p (to je, dakle, pravac prave p).
Količnički skup čine svi pravci pravih u ravni α.