Množiny a relace: stavebnice, ze které se skládají definice v AI

Množina je výchozí pojem, který se dál nerozkládá (podobně jako bod v geometrii): je to soubor navzájem různých objektů, kterým říkáme její prvky. Pro množinu A a libovolný objekt x píšeme

x ∈ A — „x je prvkem A“,   x ∉ A :⇔ ¬(x ∈ A) — „x není prvkem A“.

Od množiny požadujeme dvě věci:

1. pro každý objekt x platí právě jedno z tvrzení x ∈ A, x ∉ A — o členství je vždy jednoznačně rozhodnuto;
2. množina je plně určena svými prvky — nic dalšího (pořadí, počet opakování) k ní nepatří; přesně to říká definice rovnosti níže.

Nechť A a B jsou množiny. A a B jsou si rovny, píšeme A = B, právě když

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

Množiny jsou tedy stejné, právě když mají přesně tytéž prvky.

Prázdná množina ∅ je množina, pro kterou platí

∀x : x ∉ ∅,

tj. nemá žádný prvek. Podle definice rovnosti je jen jedna.

Nechť A je množina. A je konečná, právě když A = ∅, nebo existují n ∈ ℕ a navzájem různé objekty a₁, …, a_n (a_i ≠ a_j pro i ≠ j) takové, že A = {a₁, …, a_n}. Mohutnost konečné množiny je číslo

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

tedy počet jejích prvků.

Nechť A a B jsou množiny. A je podmnožinou B, píšeme A ⊆ B, právě když

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

Každý prvek A je tedy i prvkem B. Zápor píšeme A ⊄ B; podle negace kvantifikátorů to znamená ∃x : x ∈ A ∧ x ∉ B.

Nechť A a B jsou množiny. A je vlastní podmnožinou B, píšeme A ⊂ B, právě když

A ⊆ B ∧ A ≠ B.

V B tedy existuje aspoň jeden prvek, který v A není. (Některé učebnice píší ⊂ i pro obyčejnou podmnožinu; v této 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ími prvky jsou tedy právě všechny podmnožiny A (vždy i ∅ a A sama).

Věta. Nechť A je konečná množina. Pak |𝒫(A)| = 2^|A| (důkaz níže).

Věta. Nechť n ∈ ℕ a A = {a₁, …, a_n}, kde prvky a₁, …, a_n jsou navzájem různé (tj. |A| = n). Pak |𝒫(A)| = 2ⁿ. (Pro A = ∅ je 𝒫(∅) = {∅} a |𝒫(∅)| = 1 = 2⁰.)

Důkaz. Každé podmnožině S ⊆ A přiřadíme charakteristický vektor (b₁, …, b_n) ∈ {0, 1}ⁿ, kde b_i = 1, právě když a_i ∈ S. Různé podmnožiny mají různé vektory a každý vektor nějaké podmnožině patří — přiřazení je vzájemně jednoznačné. Podmnožin je tedy stejně jako vektorů z nul a jedniček délky n, a těch je 2 · 2 · … · 2 = 2ⁿ. ∎

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

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

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

Nechť A a B jsou množiny. Definujeme množiny

1. sjednocení   A ∪ B := {x : x ∈ A ∨ x ∈ B},
2. průnik   A ∩ B := {x : x ∈ A ∧ x ∈ B},
3. rozdíl   A ∖ B := {x : x ∈ A ∧ x ∉ B}.

Prvek tedy leží v A ∪ B, právě když leží aspoň v jedné z množin, v A ∩ B, právě když leží v obou, a v A ∖ B, právě když leží v A, ale ne v B. Množiny s A ∩ B = ∅ se nazývají disjunktní.

Nechť navíc U je množina (základní množina, „vesmír“) a A ⊆ U. Doplněk množiny A vzhledem k U je množina

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

Věta (De Morganovy zákony). Nechť U je množina a A, B ⊆ U. Pak (A ∪ B)^c = A^c ∩ B^c a (A ∩ B)^c = A^c ∪ B^c (doplňky vzhledem k U).

Věta. Nechť A a B jsou konečné množiny. Pak |A ∪ B| = |A| + |B| − |A ∩ B|.

Důkaz. A ∪ B se skládá ze tří disjunktních částí: A ∖ B, A ∩ B a B ∖ A. Přitom |A| = |A ∖ B| + |A ∩ B| a |B| = |B ∖ A| + |A ∩ B|. Součet |A| + |B| tedy obsahuje všechny tři části, ale průnik dvakrát; jedno odečtení |A ∩ B| to napraví. ∎

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

Barvy podle vzorce přesnosti a úplnosti:

přesnost = 36/50 = 0,72 — 14 označených e-mailů byl falešný poplach,

úplnost = 36/40 = 0,90 — 4 spamy model propustil.

Podle inkluze a exkluze (barvy podle jejího vzorce) |P ∪ S| = 50 + 40 − 36 = 54. Poměr průniku a sjednocení je Jaccardův index (v počítačovém vidění IoU, „intersection over union“, kterým se hodnotí, jak dobře rámeček detektoru sedí na objekt): pro konečné množiny P, S, z nichž aspoň jedna je neprázdná,

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

Nechť a, b jsou libovolné objekty. Uspořádaná dvojice (a, b) je objekt s první složkou a a druhou složkou b, pro který platí: pro všechny objekty a, b, c, d

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

Na rozdíl od množiny {a, b} = {b, a} tedy na pořadí záleží. (Čistě množinově se dvojice zavádí jako (a, b) := {{a}, {a, b}} — Kuratowského definice, která právě tuhle vlastnost má.)

Nechť A a B jsou množiny. Kartézský součin A a B je množina

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

Jsou-li A, B konečné, platí |A × B| = |A| · |B|.

Obecně: nechť n ∈ ℕ a A₁, …, A_n jsou množiny. n-tice (a₁, …, a_n) má vlastnost (a₁, …, a_n) = (b₁, …, b_n) ⇔ ∀i ∈ {1, …, n} : a_i = b_i a

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

Robot na mřížce 3 × 3 má |S| = 9 stavů (políček) a |A| = 4 akce {↑, →, ↓, ←}.

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

Tabulka, která má pro každou dvojici (stav, akce) jedno číslo — třeba odhad, jak dobrá je ta akce v tom stavu — má tedy 36 políček. Proč se počty násobí: ke každému z 9 stavů lze přidat kteroukoli ze 4 akcí, takže dvojice tvoří 9 řádků po 4.

Nechť A a B jsou množiny. Binární relace mezi A a B je libovolná množina R, pro kterou

R ⊆ A × B.

Pro a ∈ A a b ∈ B píšeme a R b :⇔ (a, b) ∈ R a čteme „a je v relaci R s b“.

Relace mezi A a A, tj. R ⊆ A × A, se nazývá relace na množině A.

Nechť n ∈ ℕ, A = {a₁, …, a_n} je množina s navzájem různými prvky a₁, …, a_n a R ⊆ A × A relace na A. Matice relace R (vzhledem k tomuto očíslování prvků) je tabulka M ∈ {0, 1}^n×n o n řádcích a n sloupcích s prvky

M_ij := 1, je-li a_i R a_j,   M_ij := 0 jinak,   pro i, j = 1, …, n.

Počet dvojic v relaci je počet jedniček v matici: ∑_i=1ⁿ ∑_j=1ⁿ M_ij = |R|.

Věta. Nechť A a B jsou konečné množiny. Pak mezi A a B existuje přesně 2^{|A| · |B|} relací.

Důkaz. Relace je libovolná podmnožina A × B, relací je tedy |𝒫(A × B)| = 2^{|A × B|} = 2^{|A| · |B|}. ∎

Na {1, …, 6} je 6 · 6 = 36 možných dvojic a 2³⁶ = 68 719 476 736 relací. „Dělí“ je jedna z nich — ta se 14 jedničkami v matici.

Nechť A je množina a R ⊆ A × A relace na A. Relace R je

1. reflexivní, právě když ∀a ∈ A : a R a;
2. symetrická, právě když ∀a, b ∈ A : (a R b ⇒ b R a);
3. antisymetrická, právě když ∀a, b ∈ A : ((a R b ∧ b R a) ⇒ a = b);
4. tranzitivní, právě když ∀a, b, c ∈ A : ((a R b ∧ b R c) ⇒ a R c).

Antisymetrie není opak symetrie: relace „=“ je symetrická i antisymetrická zároveň.

Na matici relace se vlastnosti čtou přímo: reflexivní ⇔ na diagonále jsou samé jedničky (M_ii = 1), symetrická ⇔ matice je souměrná podle diagonály (M_ij = M_ji), antisymetrická ⇔ mimo diagonálu nikdy nejsou jedničky na obou místech M_ij a M_ji.

Abychom vlastnost vyvrátili, stačí jediný protipříklad. „Sousedé“ nejsou tranzitivní: 1 R 2 (|1 − 2| = 1) a 2 R 1, ale 1 R 1 neplatí (|1 − 1| = 0). Nejsou ani reflexivní (1 R 1 neplatí) ani antisymetrické (1 R 2 a 2 R 1, přitom 1 ≠ 2).

Abychom ji dokázali, musíme projít všechny případy. „Dělí“ je tranzitivní: když b = ka a c = lb, pak c = (kl)a, takže a dělí c.

Nechť A je množina a R, Q ⊆ A × A jsou relace na A. Složení relací R a Q je relace

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

— „z a se dá jedním krokem R a pak jedním krokem Q dojít do c“. (Pozor, pořadí v zápisu se v literatuře liší; u funkcí znamená g ∘ f „nejdřív f“, tady R ∘ Q „nejdřív R“.)

Mocniny relace R definujeme pro k ∈ ℕ rekurzí R¹ := R, R^k+1 := R^k ∘ R. Tranzitivní uzávěr relace R je relace

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

Tedy a R⁺ c, právě když existují k ∈ ℕ a prvky b₀, …, b_k ∈ A s b₀ = a, b_k = c a b_i−1 R b_i pro i = 1, …, k — z a vede do c cesta po šipkách R délky aspoň 1.

Věta. Nechť R je relace na množině A. Pak R⁺ je nejmenší tranzitivní relace na A, která obsahuje R: platí R ⊆ R⁺, R⁺ je tranzitivní a pro každou tranzitivní relaci T na A s R ⊆ T je R⁺ ⊆ T.

Nechť A je množina a R ⊆ A × A relace na A. R je ekvivalence, právě když je reflexivní, symetrická a tranzitivní. Je-li R ekvivalence a a ∈ A, je třída ekvivalence prvku a množina

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

Nechť A je množina. Rozklad množiny A je množina 𝒮 ⊆ 𝒫(A) podmnožin A (jejím prvkům říkáme části nebo třídy), která splňuje

1. ∀S ∈ 𝒮 : S ≠ ∅ — žádná část není prázdná;
2. ∀S, T ∈ 𝒮 : (S ≠ T ⇒ S ∩ T = ∅) — různé části jsou disjunktní;
3. ⋃_{S ∈ 𝒮} S = A, tj. ∀x ∈ A ∃S ∈ 𝒮 : x ∈ S — části pokryjí celé A.

Každý prvek A tedy leží v právě jedné části.

Věta. Nechť A je množina.

1. Je-li R ekvivalence na A, pak množina tříd {[a] : a ∈ A} je rozklad A.
2. Je-li 𝒮 rozklad A, pak relace x ∼ y :⇔ ∃S ∈ 𝒮 : x ∈ S ∧ y ∈ S („patří do stejné části“) je ekvivalence na A a její třídy jsou právě části 𝒮.

Věta. Nechť A je množina, R ekvivalence na A a a, b ∈ A. Pak platí buď [a] = [b], nebo [a] ∩ [b] = ∅. Navíc a ∈ [a] pro každé a ∈ A.

Důkaz. Předpokládejme, že [a] ∩ [b] ≠ ∅, a ukážeme [a] = [b]. Pak existuje z ∈ [a] ∩ [b], tedy z R a a z R b. Ze symetrie a R z a z tranzitivity a R b. Pro každé x ∈ [a] je x R a a a R b, tedy x R b a x ∈ [b]; stejně naopak. Takže [a] = [b]. Reflexivita navíc dává a ∈ [a] — žádná třída není prázdná a každý prvek v nějaké je. ∎

Na A = {0, …, 8} je x R a :⇔ x mod 3 = a mod 3, kde x mod 3 je zbytek po celočíselném dělení x třemi.

[4] = {x ∈ {0, …, 8} : x mod 3 = 4 mod 3 = 1} = {1, 4, 7} (barvy podle vzorce výše).

[1] = [7] = {1, 4, 7} — tatáž třída pod jiným jménem. Dohromady vzniknou 3 třídy po 3 prvcích: {0, 3, 6}, {1, 4, 7}, {2, 5, 8}; 3 + 3 + 3 = 9 = |A|.

Nechť A je množina a R ⊆ A × A relace na A. R je částečné uspořádání, právě když je reflexivní, antisymetrická a tranzitivní. Dvojici (A, R) pak říkáme částečně uspořádaná množina.

Prvky a, b ∈ A jsou srovnatelné, právě když a R b ∨ b R a. Částečné uspořádání R je lineární (úplné), právě když jsou srovnatelné všechny dvojice:

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

Nechť A je množina a ≤ částečné uspořádání na A. Ostré uspořádání příslušné k ≤ je relace < na A daná pro a, b ∈ A předpisem

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

Prvek b ∈ A pokrývá prvek a ∈ A, píšeme a ⋖ b, právě když

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

tj. a je ostře pod b a mezi nimi neleží žádný další prvek. Hasseův diagram konečné částečně uspořádané množiny kreslí čáru (zdola nahoru) právě mezi dvojicemi a ⋖ b.

Nechť A a B jsou množiny. Funkce (zobrazení) z A do B, psáno f : A → B, je relace f ⊆ A × B, pro kterou platí

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

kde ∃! čteme „existuje právě jedno“. Každý prvek a ∈ A je tedy v relaci s právě jedním prvkem b ∈ B; ten se značí f(a). Podrobněji o funkcích v dílu Funkce a zobrazení.

Na A = {1, 2, 3} je 2^{3 · 3} = 2⁹ = 512 relací. Funkce musí každému ze 3 prvků vybrat právě jeden ze 3 obrazů, nezávisle na ostatních: 3 · 3 · 3 = 3³ = 27 funkcí.

V matici relace to znamená: v každém řádku je právě jedna jednička. Matice „dělí“ funkcí není — v řádku 1 má šest jedniček.