Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI

Množina je východiskový pojem, ktorý sa ďalej nerozkladá (podobne ako bod v geometrii): je to súbor navzájom rôznych objektov, ktorým hovoríme jej prvky. Pre množinu A a ľubovoľný objekt x píšeme

x ∈ A — „x je prvkom A“,   x ∉ A :⇔ ¬(x ∈ A) — „x nie je prvkom A“.

Od množiny požadujeme dve veci:

1. pre každý objekt x platí práve jedno z tvrdení x ∈ A, x ∉ A — o členstve je vždy jednoznačne rozhodnuté;
2. množina je úplne určená svojimi prvkami — nič ďalšie (poradie, počet opakovaní) k nej nepatrí; presne to hovorí definícia rovnosti nižšie.

Nech A a B sú množiny. A a B sa rovnajú, píšeme A = B, práve vtedy, keď

∀x : (x ∈ A ⇔ x ∈ B).

Množiny sú teda rovnaké práve vtedy, keď majú presne tie isté prvky.

Prázdna množina ∅ je množina, pre ktorú platí

∀x : x ∉ ∅,

t. j. nemá žiadny prvok. Podľa definície rovnosti je len jedna.

Nech A je množina. A je konečná práve vtedy, keď A = ∅, alebo existujú n ∈ ℕ a navzájom rôzne objekty a₁, …, a_n (a_i ≠ a_j pre i ≠ j) také, že A = {a₁, …, a_n}. Mohutnosť konečnej množiny je číslo

|A| := n,   |∅| := 0,

teda počet jej prvkov.

Nech A a B sú množiny. A je podmnožinou B, píšeme A ⊆ B, práve vtedy, keď

∀x : (x ∈ A ⇒ x ∈ B).

Každý prvok A je teda aj prvkom B. Zápor píšeme A ⊄ B; podľa negácie kvantifikátorov to znamená ∃x : x ∈ A ∧ x ∉ B.

Nech A a B sú množiny. A je vlastnou podmnožinou B, píšeme A ⊂ B, práve vtedy, keď

A ⊆ B ∧ A ≠ B.

V B teda existuje aspoň jeden prvok, ktorý v A nie je. (Niektoré učebnice píšu ⊂ aj pre obyčajnú podmnožinu; v tejto sérii znamená ⊂ vždy vlastnú podmnožinu.)

Nech A je množina. Potenčná množina množiny A je množina

𝒫(A) := {S : S je množina ∧ S ⊆ A}.

Jej prvkami sú teda práve všetky podmnožiny A (vždy aj ∅ a A samotná).

Veta. Nech A je konečná množina. Potom |𝒫(A)| = 2^|A| (dôkaz nižšie).

Veta. Nech n ∈ ℕ a A = {a₁, …, a_n}, kde prvky a₁, …, a_n sú navzájom rôzne (t. j. |A| = n). Potom |𝒫(A)| = 2ⁿ. (Pre A = ∅ je 𝒫(∅) = {∅} a |𝒫(∅)| = 1 = 2⁰.)

Dôkaz. Každej podmnožine S ⊆ A priradíme charakteristický vektor (b₁, …, b_n) ∈ {0, 1}ⁿ, kde b_i = 1 práve vtedy, keď a_i ∈ S. Rôzne podmnožiny majú rôzne vektory a každý vektor patrí nejakej podmnožine — priradenie je vzájomne jednoznačné. Podmnožín je teda rovnako ako vektorov z núl a jednotiek dĺžky n, a tých je 2 · 2 · … · 2 = 2ⁿ. ∎

5 = 1 · 2⁰ + 0 · 2¹ + 1 · 2², teda bity (b₁, b₂, b₃) = (1, 0, 1).

Bit 1 pri a a pri c, bit 0 pri b ⇒ podmnožina {a, c}.

Číslo 0 dá ∅, číslo 7 = 111₂ dá celé {a, b, c} — a medzi tým je dohromady 8 čísel, teda 8 podmnožín.

Nech A a B sú množiny. Definujeme množiny

1. zjednotenie   A ∪ B := {x : x ∈ A ∨ x ∈ B},
2. prienik   A ∩ B := {x : x ∈ A ∧ x ∈ B},
3. rozdiel   A ∖ B := {x : x ∈ A ∧ x ∉ B}.

Prvok teda leží v A ∪ B práve vtedy, keď leží aspoň v jednej z množín, v A ∩ B práve vtedy, keď leží v oboch, a v A ∖ B práve vtedy, keď leží v A, ale nie v B. Množiny s A ∩ B = ∅ sa nazývajú disjunktné.

Nech navyše U je množina (základná množina, „vesmír“) a A ⊆ U. Doplnok množiny A vzhľadom na U je množina

A^c := U ∖ A = {x ∈ U : x ∉ A}.

Veta (De Morganove zákony). Nech U je množina a A, B ⊆ U. Potom (A ∪ B)^c = A^c ∩ B^c a (A ∩ B)^c = A^c ∪ B^c (doplnky vzhľadom na U).

Veta. Nech A a B sú konečné množiny. Potom |A ∪ B| = |A| + |B| − |A ∩ B|.

Dôkaz. A ∪ B sa skladá z troch disjunktných častí: A ∖ B, A ∩ B a B ∖ A. Pritom |A| = |A ∖ B| + |A ∩ B| a |B| = |B ∖ A| + |A ∩ B|. Súčet |A| + |B| teda obsahuje všetky tri časti, ale prienik dvakrát; jedno odčítanie |A ∩ B| to napraví. ∎

Model označil |P| = 50 e-mailov, skutočného spamu je |S| = 40 a v oboch množinách je |P ∩ S| = 36 e-mailov.

Farby podľa vzorca presnosti a úplnosti:

presnosť = 36/50 = 0,72 — 14 označených e-mailov bol falošný poplach,

úplnosť = 36/40 = 0,90 — 4 spamy model prepustil.

Podľa inklúzie a exklúzie (farby podľa jej vzorca) |P ∪ S| = 50 + 40 − 36 = 54. Pomer prieniku a zjednotenia je Jaccardov index (v počítačovom videní IoU, „intersection over union“, ktorým sa hodnotí, ako dobre rámček detektora sedí na objekt): pre konečné množiny P, S, z ktorých aspoň jedna je neprázdna,

J(P, S) := |P ∩ S|/|P ∪ S| = 36/54 = 2/3 ≈ 0,667.

Nech a, b sú ľubovoľné objekty. Usporiadaná dvojica (a, b) je objekt s prvou zložkou a a druhou zložkou b, pre ktorý platí: pre všetky objekty a, b, c, d

(a, b) = (c, d) ⇔ a = c ∧ b = d.

Na rozdiel od množiny {a, b} = {b, a} teda na poradí záleží. (Čisto množinovo sa dvojica zavádza ako (a, b) := {{a}, {a, b}} — Kuratowského definícia, ktorá práve túto vlastnosť má.)

Nech A a B sú množiny. Karteziánsky súčin A a B je množina

A × B := {(a, b) : a ∈ A ∧ b ∈ B}.

Ak sú A, B konečné, platí |A × B| = |A| · |B|.

Všeobecne: nech n ∈ ℕ a A₁, …, A_n sú množiny. n-tica (a₁, …, a_n) má vlastnosť (a₁, …, a_n) = (b₁, …, b_n) ⇔ ∀i ∈ {1, …, n} : a_i = b_i a

A₁ × … × A_n := {(a₁, …, a_n) : a_i ∈ A_i pre i = 1, …, n},   Aⁿ := A × … × A (n-krát).

Robot na mriežke 3 × 3 má |S| = 9 stavov (políčok) a |A| = 4 akcie {↑, →, ↓, ←}.

|S × A| = |S| · |A| = 9 · 4 = 36.

Tabuľka, ktorá má pre každú dvojicu (stav, akcia) jedno číslo — napríklad odhad, aká dobrá je tá akcia v tom stave — má teda 36 políčok. Prečo sa počty násobia: ku každému z 9 stavov možno pridať ktorúkoľvek zo 4 akcií, takže dvojice tvoria 9 riadkov po 4.

Nech A a B sú množiny. Binárna relácia medzi A a B je ľubovoľná množina R, pre ktorú

R ⊆ A × B.

Pre a ∈ A a b ∈ B píšeme a R b :⇔ (a, b) ∈ R a čítame „a je v relácii R s b“.

Relácia medzi A a A, t. j. R ⊆ A × A, sa nazýva relácia na množine A.

Nech n ∈ ℕ, A = {a₁, …, a_n} je množina s navzájom rôznymi prvkami a₁, …, a_n a R ⊆ A × A relácia na A. Matica relácie R (vzhľadom na toto očíslovanie prvkov) je tabuľka M ∈ {0, 1}^n×n s n riadkami a n stĺpcami s prvkami

M_ij := 1, ak a_i R a_j,   M_ij := 0 inak,   pre i, j = 1, …, n.

Počet dvojíc v relácii je počet jednotiek v matici: ∑_i=1ⁿ ∑_j=1ⁿ M_ij = |R|.

Veta. Nech A a B sú konečné množiny. Potom medzi A a B existuje presne 2^{|A| · |B|} relácií.

Dôkaz. Relácia je ľubovoľná podmnožina A × B, relácií je teda |𝒫(A × B)| = 2^{|A × B|} = 2^{|A| · |B|}. ∎

Na {1, …, 6} je 6 · 6 = 36 možných dvojíc a 2³⁶ = 68 719 476 736 relácií. „Delí“ je jedna z nich — tá so 14 jednotkami v matici.

Nech A je množina a R ⊆ A × A relácia na A. Relácia R je

1. reflexívna práve vtedy, keď ∀a ∈ A : a R a;
2. symetrická práve vtedy, keď ∀a, b ∈ A : (a R b ⇒ b R a);
3. antisymetrická práve vtedy, keď ∀a, b ∈ A : ((a R b ∧ b R a) ⇒ a = b);
4. tranzitívna práve vtedy, keď ∀a, b, c ∈ A : ((a R b ∧ b R c) ⇒ a R c).

Antisymetria nie je opak symetrie: relácia „=“ je symetrická aj antisymetrická zároveň.

Na matici relácie sa vlastnosti čítajú priamo: reflexívna ⇔ na diagonále sú samé jednotky (M_ii = 1), symetrická ⇔ matica je súmerná podľa diagonály (M_ij = M_ji), antisymetrická ⇔ mimo diagonály nikdy nie sú jednotky na oboch miestach M_ij a M_ji.

Aby sme vlastnosť vyvrátili, stačí jediný protipríklad. „Susedia“ nie sú tranzitívni: 1 R 2 (|1 − 2| = 1) a 2 R 1, ale 1 R 1 neplatí (|1 − 1| = 0). Nie sú ani reflexívni (1 R 1 neplatí), ani antisymetrickí (1 R 2 a 2 R 1, pritom 1 ≠ 2).

Aby sme ju dokázali, musíme prejsť všetky prípady. „Delí“ je tranzitívna: keď b = ka a c = lb, potom c = (kl)a, takže a delí c.

Nech A je množina a R, Q ⊆ A × A sú relácie na A. Zloženie relácií R a Q je relácia

R ∘ Q := {(a, c) ∈ A × A : ∃b ∈ A : a R b ∧ b Q c}

— „z a sa dá jedným krokom R a potom jedným krokom Q dôjsť do c“. (Pozor, poradie v zápise sa v literatúre líši; pri funkciách znamená g ∘ f „najprv f“, tu R ∘ Q „najprv R“.)

Mocniny relácie R definujeme pre k ∈ ℕ rekurziou R¹ := R, R^k+1 := R^k ∘ R. Tranzitívny uzáver relácie R je relácia

R⁺ := ⋃_k=1^∞ R^k = R ∪ (R ∘ R) ∪ (R ∘ R ∘ R) ∪ …

Teda a R⁺ c práve vtedy, keď existujú k ∈ ℕ a prvky b₀, …, b_k ∈ A s b₀ = a, b_k = c a b_i−1 R b_i pre i = 1, …, k — z a vedie do c cesta po šípkach R dĺžky aspoň 1.

Veta. Nech R je relácia na množine A. Potom R⁺ je najmenšia tranzitívna relácia na A, ktorá obsahuje R: platí R ⊆ R⁺, R⁺ je tranzitívna a pre každú tranzitívnu reláciu T na A s R ⊆ T je R⁺ ⊆ T.

Nech A je množina a R ⊆ A × A relácia na A. R je ekvivalencia práve vtedy, keď je reflexívna, symetrická a tranzitívna. Ak je R ekvivalencia a a ∈ A, je trieda ekvivalencie prvku a množina

[a] := {x ∈ A : x R a}.

Nech A je množina. Rozklad množiny A je množina 𝒮 ⊆ 𝒫(A) podmnožín A (jej prvkom hovoríme časti alebo triedy), ktorá spĺňa

1. ∀S ∈ 𝒮 : S ≠ ∅ — žiadna časť nie je prázdna;
2. ∀S, T ∈ 𝒮 : (S ≠ T ⇒ S ∩ T = ∅) — rôzne časti sú disjunktné;
3. ⋃_{S ∈ 𝒮} S = A, t. j. ∀x ∈ A ∃S ∈ 𝒮 : x ∈ S — časti pokryjú celé A.

Každý prvok A teda leží v práve jednej časti.

Veta. Nech A je množina.

1. Ak je R ekvivalencia na A, potom množina tried {[a] : a ∈ A} je rozklad A.
2. Ak je 𝒮 rozklad A, potom relácia x ∼ y :⇔ ∃S ∈ 𝒮 : x ∈ S ∧ y ∈ S („patria do rovnakej časti“) je ekvivalencia na A a jej triedy sú práve časti 𝒮.

Veta. Nech A je množina, R ekvivalencia na A a a, b ∈ A. Potom platí buď [a] = [b], alebo [a] ∩ [b] = ∅. Navyše a ∈ [a] pre každé a ∈ A.

Dôkaz. Predpokladajme, že [a] ∩ [b] ≠ ∅, a ukážeme [a] = [b]. Potom existuje z ∈ [a] ∩ [b], teda z R a a z R b. Zo symetrie a R z a z tranzitivity a R b. Pre každé x ∈ [a] je x R a a a R b, teda x R b a x ∈ [b]; rovnako naopak. Takže [a] = [b]. Reflexivita navyše dáva a ∈ [a] — žiadna trieda nie je prázdna a každý prvok je v nejakej. ∎

Na A = {0, …, 8} je x R a :⇔ x mod 3 = a mod 3, kde x mod 3 je zvyšok po celočíselnom delení x tromi.

[4] = {x ∈ {0, …, 8} : x mod 3 = 4 mod 3 = 1} = {1, 4, 7} (farby podľa vzorca vyššie).

[1] = [7] = {1, 4, 7} — tá istá trieda pod iným menom. Dohromady vzniknú 3 triedy po 3 prvkoch: {0, 3, 6}, {1, 4, 7}, {2, 5, 8}; 3 + 3 + 3 = 9 = |A|.

Nech A je množina a R ⊆ A × A relácia na A. R je čiastočné usporiadanie práve vtedy, keď je reflexívna, antisymetrická a tranzitívna. Dvojici (A, R) potom hovoríme čiastočne usporiadaná množina.

Prvky a, b ∈ A sú porovnateľné práve vtedy, keď a R b ∨ b R a. Čiastočné usporiadanie R je lineárne (úplné) práve vtedy, keď sú porovnateľné všetky dvojice:

∀a, b ∈ A : a R b ∨ b R a.

Nech A je množina a ≤ čiastočné usporiadanie na A. Ostré usporiadanie prislúchajúce k ≤ je relácia < na A daná pre a, b ∈ A predpisom

a < b :⇔ a ≤ b ∧ a ≠ b.

Prvok b ∈ A pokrýva prvok a ∈ A, píšeme a ⋖ b, práve vtedy, keď

a < b ∧ ¬∃c ∈ A : (a < c ∧ c < b),

t. j. a je ostro pod b a medzi nimi neleží žiadny ďalší prvok. Hasseov diagram konečnej čiastočne usporiadanej množiny kreslí čiaru (zdola nahor) práve medzi dvojicami a ⋖ b.

Nech A a B sú množiny. Funkcia (zobrazenie) z A do B, písané f : A → B, je relácia f ⊆ A × B, pre ktorú platí

∀a ∈ A ∃! b ∈ B : (a, b) ∈ f,

kde ∃! čítame „existuje práve jedno“. Každý prvok a ∈ A je teda v relácii s práve jedným prvkom b ∈ B; ten sa označuje f(a). Podrobnejšie o funkciách v diele Funkcie a zobrazenia.

Na A = {1, 2, 3} je 2^{3 · 3} = 2⁹ = 512 relácií. Funkcia musí každému z 3 prvkov vybrať práve jeden z 3 obrazov, nezávisle od ostatných: 3 · 3 · 3 = 3³ = 27 funkcií.

V matici relácie to znamená: v každom riadku je práve jedna jednotka. Matica „delí“ funkciou nie je — v riadku 1 má šesť jednotiek.