Čo je relácia
Binárna relácia R z množiny A do množiny B je ľubovoľná podmnožina kartézskeho súčinu: R ⊆ A × B. Ak je (a, b) ∈ R, hovoríme, že a je v relácii s b, a píšeme a R b.
Pripomeňme si: kartézsky súčin A × B je množina všetkých usporiadaných dvojíc (a, b), kde a ∈ A a b ∈ B. Relácia je teda len výber niektorých z týchto dvojíc. Ak A = B, hovoríme o relácii na množine A, čiže R ⊆ A × A.
Definícia
Relácia R ⊆ A × B. Žiadna ďalšia podmienka — stačí byť podmnožinou súčinu.
Zápis
(a, b) ∈ R a a R b znamenajú to isté. Napr. 3 ≤ 5 je dvojica (3, 5) v relácii „≤“.
Koľko ich je
Na n-prvkovej množine je |A × A| = n² dvojíc, a teda 2n² rôznych relácií.
Nech A = {1, 2, 3} a relácia „delí“ a | b. Potom R = {(1,1), (1,2), (1,3), (2,2), (3,3)} — napríklad (2, 3) ∉ R, lebo 2 nedelí 3.
Vyber správnu odpoveď.
Vlastnosti relácií na množine
Reláciu R na množine A opisujeme štyrmi kľúčovými vlastnosťami. Z nich poskladáme ekvivalenciu aj usporiadanie.
Reflexívnosť
Každý prvok je v relácii sám so sebou: ∀a ∈ A : a R a. Napr. ≤ (lebo a ≤ a).
Symetria
Ak a R b, tak aj b R a: ∀a,b : a R b ⇒ b R a. Napr. = alebo „má rovnaký vek“.
Antisymetria
Ak a R b a zároveň b R a, tak a = b. Napr. ≤ na ℕ.
Tranzitívnosť
Ak a R b a b R c, tak a R c. Napr. ≤, = aj | (delí).
Nie sú to protiklady! Relácia = je aj symetrická, aj antisymetrická naraz. Antisymetria nezakazuje slučky a R a — zakazuje len dve rôzne protismerné dvojice.
Klikni a over si odpoveď.
Vyber správnu odpoveď.
Ekvivalencia a rozklad množiny
Relácia ∼ na A je ekvivalencia, ak je súčasne reflexívna, symetrická a tranzitívna. Zovšeobecňuje pojem „rovnosti“.
Pre prvok a nazveme množinu [a] = {x ∈ A : x ∼ a} jeho triedou ekvivalencie. Kľúčová veta: triedy ekvivalencie tvoria rozklad množiny A — sú neprázdne, navzájom disjunktné a ich zjednotenie je celé A. Dva prvky sú v relácii práve vtedy, keď padnú do tej istej triedy.
Tri podmienky
R + S + T: reflexívna, symetrická, tranzitívna. Vynechanie ktorejkoľvek ekvivalenciu pokazí.
Rozklad na triedy
Buď [a] = [b], alebo [a] ∩ [b] = ∅. Tretia možnosť neexistuje — triedy sa neprekrývajú.
Relácia a ≡ b (mod 3) na ℤ (čiže 3 | (a − b)) je ekvivalencia s presne 3 triedami podľa zvyšku po delení 3: [0] = {…,−3,0,3,…}, [1], [2]. Najmenšia ekvivalencia na každej množine je rovnosť = (každá trieda je jednoprvková).
Overíme všetky tri vlastnosti. Klikaj.
Vyber správnu odpoveď.
Čiastočné a lineárne usporiadanie
Relácia ≤ je čiastočné usporiadanie, ak je reflexívna, antisymetrická a tranzitívna. Oproti ekvivalencii sa symetria mení na antisymetriu.
Usporiadanie znázorňujeme Hasseovým diagramom: prvky sú body, väčší prvok kreslíme vyššie a spájame ho hranou s bezprostredne menším (reflexívne slučky a tranzitívne skratky vynechávame). Minimálny prvok nemá pod sebou žiadny menší, maximálny nad sebou žiadny väčší. Ak sú každé dva prvky porovnateľné (a ≤ b alebo b ≤ a), ide o lineárne (úplné) usporiadanie.
Hasseov diagram — deliteľnosť na {1,2,3,6}
1 je minimum, 6 je maximum. Prvky 2 a 3 sú neporovnateľné — preto nejde o lineárne usporiadanie.
Lineárne usporiadanie
Reťazec, v ktorom sú všetky prvky porovnateľné, napr. ≤ na ℕ: 0 ≤ 1 ≤ 2 ≤ … Hasseov diagram je jediná zvislá čiara.
≤ na ℕ je lineárne usporiadanie (každé dva prvky porovnateľné). Deliteľnosť | na ℕ je len čiastočné (2 a 3 sa nedelia navzájom). Relácia < nie je usporiadanie v tomto zmysle — nie je reflexívna (a < a neplatí).
Vyber správnu odpoveď.
Zobrazenia ako špeciálne relácie
Zobrazenie (funkcia) f : A → B je špeciálna relácia f ⊆ A × B, v ktorej má každý prvok a ∈ A priradený práve jeden obraz f(a) ∈ B.
Injektívne (prosté)
Rôzne vzory majú rôzne obrazy: f(x) = f(y) ⇒ x = y.
Surjektívne (na)
Každé b ∈ B je obrazom: ∀b ∃a : f(a) = b.
Bijektívne
Injektívne aj surjektívne naraz — vzájomne jednoznačné priradenie.
Zložené zobrazenie (g ∘ f)(x) = g(f(x)) najprv aplikuje f, potom g. Inverzné zobrazenie f⁻¹ existuje práve vtedy, keď je f bijekcia, a platí f⁻¹(f(x)) = x.
f(x) = 2x je bijekcia (prostá aj na, inverzná je x/2). Naopak f(x) = x² na ℝ nie je ani injekcia ((−1)² = 1²) ani surjekcia (záporné čísla nie sú druhou mocninou).
Klikni a over si.
Vyber správnu odpoveď.
Záverečný kvíz
Desať otázok cez celú tému — od definície relácie cez vlastnosti, ekvivalenciu a usporiadanie až po zobrazenia.
Otestuj sa cez celú tému.