16. Množiny, relace a zobrazení

30 minut

Co si odnesete

Jak se s množinami počítá: operace, De Morganova pravidla, kartézský součin, potenční množina a princip inkluze a exkluze.
Co je relace, jak se skládá a obrací a jak u ní ověřit sedm vlastností — hlavně ekvivalenci a uspořádání.
Kdy je relace zobrazením, co je injekce, surjekce a bijekce a proč je ℚ spočetná, ale ℝ ne.

Množina je nejzákladnější pojem matematiky — tak základní, že se ani nedefinuje. Z množin se ale dá postavit všechno ostatní: relace je množina dvojic, zobrazení (funkce) je relace, která každému prvku přiřadí nejvýš jednu hodnotu, a uspořádání nebo ekvivalence jsou relace se zvláštními vlastnostmi. Okruh jde v tomhle pořadí: nejdřív množiny a operace s nimi (a logika, kterou se popisují), pak relace a jejich vlastnosti, rozklady a uspořádání a nakonec zobrazení a otázka, kdy mají dvě nekonečné množiny „stejně prvků“.

1. Množina, podmnožina a rovnost

Definice — množina

Množina je primitivní pojem — pojem, který se nedefinuje, protože by ho bylo nutné vysvětlit pomocí jiných pojmů a ty zase pomocí dalších; někde se začít musí. Popisně: souhrn (skupina, soubor) nějakých navzájem různých objektů, které podle nějakého kritéria tvoří jeden celek. Množina je určená, jestliže o každém objektu lze rozhodnout, zda je, nebo není jejím prvkem (x ∈ A, x ∉ A).

Množinu lze zadat

výčtem prvků, např. {1, 2, 3},
jako obor pravdivosti výrokové formy, např. {x ∈ ℕ; x < 4}. Výroková forma je tvrzení s proměnnou, o jehož pravdivosti rozhodne až dosazení (x < 4 platí pro x = 2, neplatí pro x = 7). Obor pravdivosti jsou všechny hodnoty, pro které po dosazení platí — tady {1, 2, 3}.

Prázdná množina ∅ = {} nemá žádný prvek. Pozor: {∅} není prázdná množina — má jeden prvek, a to ∅.

Laicky řečeno

Množina je pytel, u kterého jde o jediné: co v něm je a co ne. Nezáleží na pořadí a nic se nepočítá dvakrát — {1, 2, 2, 3} je tatáž množina jako {3, 1, 2}. A prázdný pytel ∅ je něco jiného než pytel, ve kterém leží prázdný pytel {∅}.

Nejčastěji se pracuje s číselnými množinami; každá další obsahuje tu předchozí:

ℕ — přirozená čísla 1, 2, 3, … (čísla, kterými se počítají předměty);
ℤ — celá čísla: přirozená, nula a záporná čísla …, −2, −1, 0, 1, 2, …;
ℚ — racionální čísla: všechny zlomky p/q s celým p a nenulovým celým q, např. 1/2 nebo −3/4;
ℝ — reálná čísla: všechny body číselné osy, tedy i čísla, která zlomkem zapsat nejdou (√2, π);
ℂ — komplexní čísla a + bi, kde a, b jsou reálná a i je číslo s vlastností i² = −1.

Mohutnost množiny je zobecnění „počtu prvků“. Množina je konečná, má-li nějaký konkrétní počet prvků (|{1, 2, 3}| = 3), jinak nekonečná. Nekonečné se dál dělí na spočetné a nespočetné — co to znamená, vysvětluje poslední oddíl.

Podmnožiny ℝ se často zapisují jako intervaly — všechna reálná čísla mezi dvěma mezemi a < b. Lomená závorka ⟨ ⟩ znamená, že mez do intervalu patří, kulatá ( ), že nepatří:

uzavřený ⟨a, b⟩ = {x; a ≤ x ≤ b} (obě meze patří), otevřený (a, b) = {x; a < x < b} (žádná),
zleva otevřený (a, b⟩ = {x; a < x ≤ b}, zprava otevřený ⟨a, b) = {x; a ≤ x < b},
nevlastní body −∞ a ∞ nejsou čísla, jen značka „interval nemá v tomto směru konec“: (0, ∞) jsou všechna kladná čísla. Protože ∞ není číslo, nemůže do intervalu patřit a závorka u něj je vždy kulatá.

Definice — podmnožina a rovnost množin

Množina A je podmnožinou množiny B, píšeme A ⊆ B, jestliže každý prvek A je prvkem B. Platí-li navíc A ≠ B, píšeme A ⊂ B a A je vlastní podmnožina B.

Pro každou množinu A platí ∅ ⊆ A a A ⊆ A.

Množiny A, B se rovnají, jestliže A ⊆ B a zároveň B ⊆ A.

Laicky řečeno

Rovnost se dokazuje „oběma směry“: ukážu, že každý prvek vlevo je i vpravo, a pak naopak. Přesně tak se dokazují všechny množinové zákony v dalších oddílech. Prázdná množina je podmnožinou čehokoli, protože v ní není žádný prvek, který by mohl pravidlo porušit.

2. Výroky a predikáty jako jazyk množin

Množiny se popisují logikou: x ∈ A ∪ B znamená „x ∈ A nebo x ∈ B“. Než přijdou operace, je proto potřeba mít jasno v logice.

Výrok je tvrzení, o kterém má smysl říct, že je pravdivé, nebo nepravdivé („7 je prvočíslo“). Jeho pravdivostní hodnota (ph) je 1 (pravda), nebo 0 (nepravda). Výrokový počet zkoumá, jak se pravdivost složeného výroku odvodí z jeho částí, spojených logickými spojkami:

¬p — negace, „není pravda, že p“;
p ∧ q — konjunkce, „p a q“, pravdivá, jen když platí obě;
p ∨ q — disjunkce, „p nebo q“, pravdivá, když platí aspoň jedna (i obě);
p ⇒ q — implikace, „jestliže p, pak q“, nepravdivá jen pro pravdivé p a nepravdivé q;
p ⇔ q — ekvivalence, „p právě tehdy, když q“, pravdivá, když mají obě stejnou hodnotu.

Celé chování spojek shrnuje pravdivostní tabulka — pro každou kombinaci hodnot p, q jeden řádek:

`p`	`q`	¬`p`	`p` ∧ `q`	`p` ∨ `q`	`p` ⇒ `q`	`p` ⇔ `q`
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

Definice — výroková formule a základní zákony

Výroková proměnná (p, q, A, …) zastupuje libovolný výrok. Výroková formule je správně utvořený zápis z proměnných, spojek a závorek: každá výroková proměnná je výroková formule, a jsou-li φ, ψ výrokové formule, jsou jimi i ¬(φ), (φ) ∧ (ψ), (φ) ∨ (ψ), (φ) ⇒ (ψ) a (φ) ⇔ (ψ). Třeba (p ∧ q) ⇒ p je formule, p ∧ ⇒ q ne.

Dvě formule jsou ekvivalentní, mají-li pro každé dosazení pravdivostních hodnot stejnou hodnotu — dá se pak jedna nahradit druhou. Platí tyto ekvivalence:

A ⇔ ¬(¬A) — dvojí negace se vyruší,
A ∧ B ⇔ B ∧ A, A ∨ B ⇔ B ∨ A — komutativita: nezáleží na pořadí,
(A ∧ B) ∧ C ⇔ A ∧ (B ∧ C), totéž pro ∨ — asociativita: nezáleží na uzávorkování, proto se závorky vynechávají,
A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C) — distributivita: „roznásobení závorky“ jako u a(b + c) = ab + ac, tady funguje oběma směry,
¬(A ∧ B) ⇔ ¬A ∨ ¬B, ¬(A ∨ B) ⇔ ¬A ∧ ¬B — De Morganova pravidla: negace „prohodí“ ∧ a ∨,
(A ⇔ B) ⇔ (A ⇒ B) ∧ (B ⇒ A) — ekvivalence je implikace oběma směry,
¬(A ⇒ B) ⇔ A ∧ ¬B — negace implikace,
A ⇒ B ⇔ ¬B ⇒ ¬A — obměna (kontrapozice): „když prší, je mokro“ znamená totéž co „když není mokro, neprší“.

Laicky řečeno

Implikace je nepravdivá jen v jediném případě: z pravdy vyjde nepravda. „Když prší, je mokro“ nevyvrátí suchý slunečný den — vyvrátí ho jen déšť bez mokra. Proto negace implikace zní „A a zároveň ne B“, ne „když A, tak ne B“.

Definice — term a formule predikátového počtu

Výrokový počet nevidí dovnitř výroků. Predikátový počet přidává proměnné za prvky nějaké množiny, vztahy mezi nimi a kvantifikátory: ∀x („pro každé x“, obecný kvantifikátor) a ∃x („existuje x“, existenční kvantifikátor).

Term nad množinou A je výraz, který označuje nějaký prvek A — třeba x + 1 nad ℕ. Termem je každá proměnná s oborem A, symbol každého prvku z A a dále f(t₁, …, t_n), je-li f n-ární operace na A (pravidlo, které z n prvků A udělá jeden prvek A, jako sčítání ze dvou čísel; formálně D(f) ⊆ Aⁿ, H(f) ⊆ A) a t₁, …, t_n jsou termy nad A.

Formule je naopak tvrzení. Jsou-li t₁, t₂ termy a R relace na A (vztah jako < nebo =), je t₁ R t₂ atomická formule — nejjednodušší, dál nedělitelné tvrzení, např. x + 1 < 5. Z formulí se spojkami tvoří další formule a je-li φ(x) formule s proměnnou x, která neobsahuje ∀x ani ∃x, jsou formulemi i ∀x φ(x) a ∃x φ(x).

Podformule je souvislý kus formule, který je sám formulí (vznikne umazáním symbolů na začátku a na konci). Je-li ∀x: V (resp. ∃x: V) podformule, je V dosah kvantifikátoru — část, na kterou kvantifikátor působí. Výskyt proměnné je vázaný, následuje-li hned po ∀ nebo ∃ nebo leží-li v dosahu kvantifikátoru této proměnné; jinak je volný. Proměnná je volná ve formuli, má-li v ní aspoň jeden volný výskyt, a vázaná, jsou-li všechny její výskyty vázané.

Formule je uzavřená, jsou-li všechny její proměnné vázané; je výrokovou formou, je-li aspoň jedna proměnná volná.

Laicky řečeno

„x > 3“ není ani pravda, ani nepravda — záleží na x. Je to výroková forma a množina {x ∈ ℕ; x > 3} je přesně její obor pravdivosti. Ve formuli ∃y (x < y) je y vázané (kvantifikátor za něj „dosadí“ sám) a x volné (čeká na dosazení), takže to pořád je výroková forma. Až ∀x ∃y (x < y) je uzavřená formule — výrok s pravdivostní hodnotou (nad ℕ pravdivý: ke každému číslu existuje větší).

3. Sjednocení, průnik, rozdíl a doplněk

Definice — sjednocení, průnik, rozdíl

A ∪ B = {x; x ∈ A ∨ x ∈ B}, A ∩ B = {x; x ∈ A ∧ x ∈ B}, A ∖ B = {x; x ∈ A ∧ x ∉ B}.

Sjednocení obsahuje prvky, které jsou aspoň v jedné z množin, průnik prvky, které jsou v obou, a rozdíl prvky první množiny, které ve druhé nejsou. Vlastnosti:

A ∪ ∅ = A, A ∪ A = A, A ∪ B = B ∪ A, A ∪ (B ∪ C) = (A ∪ B) ∪ C;
A ∩ ∅ = ∅, A ∩ A = A, A ∩ B = B ∩ A, A ∩ (B ∩ C) = (A ∩ B) ∩ C;
A ∖ ∅ = A, A ∖ A = ∅, ale A ∖ B ≠ B ∖ A a A ∖ (B ∖ C) ≠ (A ∖ B) ∖ C — rozdíl není komutativní ani asociativní.

Definice — doplněk a De Morganova pravidla

Doplněk dává smysl jen vůči nějaké základní množině (univerzu) M — množině všeho, o čem se v dané úloze mluví (třeba všichni studenti fakulty). Je-li A ⊆ M, je doplněk A v M

A′_M = M ∖ A, tj. x ∈ A′_M ⇔ x ∈ M ∧ x ∉ A.

(A′_M)′_M = A,
(A ∪ B)′_M = A′_M ∩ B′_M, protože x ∉ A ∪ B ⇔ x ∉ A ∧ x ∉ B,
(A ∩ B)′_M = A′_M ∪ B′_M, protože x ∉ A ∩ B ⇔ x ∉ A ∨ x ∉ B,
(A ∖ B)′_M = A′_M ∪ B, protože x ∉ A ∖ B ⇔ x ∉ A ∨ x ∈ B.

A ∪ B — sjednocení

A ∩ B — průnik

A ∖ B — rozdíl

A′_M — doplněk

Laicky řečeno

Každá množinová operace je jen logická spojka nad tvrzením „x je v množině“: sjednocení je „nebo“, průnik „a“, rozdíl „a ne“, doplněk „ne“. Proto De Morganova pravidla pro množiny jsou doslova De Morganova pravidla z výrokové logiky — „není v (A nebo B)“ je totéž co „není v A a není v B“.

Příklad — operace na konkrétních množinách

Univerzum M = {1, 2, 3, 4, 5, 6}, A = {1, 2, 3, 4}, B = {3, 4, 5}.

A ∪ B = {1, 2, 3, 4, 5}, A ∩ B = {3, 4}, A ∖ B = {1, 2}, B ∖ A = {5};
A′_M = {5, 6}, B′_M = {1, 2, 6};
(A ∪ B)′_M = {6} a A′_M ∩ B′_M = {5, 6} ∩ {1, 2, 6} = {6} — souhlasí;
(A ∩ B)′_M = {1, 2, 5, 6} a A′_M ∪ B′_M = {5, 6} ∪ {1, 2, 6} = {1, 2, 5, 6} — souhlasí;
(A ∖ B)′_M = {3, 4, 5, 6} a A′_M ∪ B = {5, 6} ∪ {3, 4, 5} = {3, 4, 5, 6} — souhlasí.

A proč rozdíl není asociativní: pro C = {4, 5, 6} je B ∖ C = {3}, takže A ∖ (B ∖ C) = {1, 2, 4}, kdežto (A ∖ B) ∖ C = {1, 2}.

4. Symetrický rozdíl, kartézský součin, distributivita

Definice — symetrický rozdíl

A Δ B = (A ∖ B) ∪ (B ∖ A).

Je komutativní (A Δ B = B Δ A), asociativní (A Δ (B Δ C) = (A Δ B) Δ C) a průnik je vůči němu distributivní: A ∩ (B Δ C) = (A ∩ B) Δ (A ∩ C).

Laicky řečeno

Symetrický rozdíl jsou prvky, které jsou „v právě jedné z množin“ — množinová obdoba spojky XOR (vylučovací „buď, anebo“: pravdivá, když platí jedna strana, ale ne obě). S A a B z předchozího příkladu je A Δ B = {1, 2} ∪ {5} = {1, 2, 5}: všechno kromě společného {3, 4}.

Definice — kartézský součin

A × B = {[x, y]; x ∈ A ∧ y ∈ B},

tedy [x, y] ∈ A × B ⇔ x ∈ A ∧ y ∈ B a [x, y] ∉ A × B ⇔ x ∉ A ∨ y ∉ B.

Prvky jsou uspořádané dvojice: na rozdíl od dvouprvkové množiny záleží na pořadí a je jasné, co je první a co druhá složka — [1, 2] ≠ [2, 1], kdežto {1, 2} = {2, 1}. Uspořádaná dvojice také smí mít obě složky stejné: [3, 3].

Vlastnosti: (A ∪ B) × C = (A × C) ∪ (B × C), (A ∩ B) × C = (A × C) ∩ (B × C) a stejně zprava: A × (B ∪ C) = (A × B) ∪ (A × C), A × (B ∩ C) = (A × B) ∩ (A × C).

Laicky řečeno

Kartézský součin je tabulka „každý s každým“: řádky jsou prvky A, sloupce prvky B a každé políčko je jedna dvojice. Pro A = {1, 2, 3, 4} a B = {3, 4, 5} má tabulka 4 · 3 = 12 políček. Z kartézského součinu se v dalším oddíle stane relace — ta je prostě vybraná část téhle tabulky.

Věta — distributivita a rozdíl

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Pro rozdíl distributivita vzhledem ke sjednocení ani k průniku neplatí! Místo ní platí obdoba De Morganových pravidel:

A ∖ (B ∪ C) = (A ∖ B) ∩ (A ∖ C), A ∖ (B ∩ C) = (A ∖ B) ∪ (A ∖ C).

Množinové zákony (a všechno ostatní) se dokazují čtyřmi základními způsoby. Pro tvrzení tvaru A ⇒ B:

přímý důkaz — z předpokladu A postupnými platnými kroky odvodím B;
nepřímý důkaz — místo toho dokážu obměnu ¬B ⇒ ¬A, která je s původní implikací ekvivalentní (někdy se z „neplatí B“ vychází snáz);
důkaz sporem — předpokládám, že tvrzení neplatí, a odvodím z toho spor, tedy něco, co platit nemůže (např. C ∧ ¬C); předpoklad tedy byl chybný;
důkaz matematickou indukcí — pro tvrzení o všech přirozených n: dokážu ho pro n = 1 (základ) a ukážu, že z platnosti pro n plyne platnost pro n + 1 (indukční krok). Jako u řady domina: padne první kostka a každá shodí další, takže padnou všechny.

Rovnost množin se typicky dokazuje přímo přes obě inkluze (vztahy ⊆): vezmu libovolné x z levé strany, podmínku členství rozepíšu spojkami a ukážu, že x leží i vpravo — a pak naopak.

5. Potenční množina, inkluze a exkluze, Dirichlet

Definice — potenční množina

Množina všech podmnožin množiny X je její potenční množina:

𝒫(X) = {B; B ⊆ X}, značí se také 2^X.

Je to „množina množin“: jejími prvky nejsou prvky X, ale podmnožiny X — včetně ∅ a celé X.

Laicky řečeno

Podmnožinu vyrobím tak, že u každého prvku řeknu „beru / neberu“. Pro {a, b, c} jsou to tři nezávislá rozhodnutí, tedy 2 · 2 · 2 = 8 podmnožin: ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c} a {a, b, c}. Odtud zápis 2^X: má-li X n prvků, má potenční množina 2ⁿ prvků.

Věta — princip inkluze a exkluze

Svislé čáry |A| značí počet prvků konečné množiny A. Princip říká, jak spočítat prvky sjednocení, když se množiny překrývají:

|A ∪ B| = |A| + |B| − |A ∩ B|,

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|,

a obecně pro n množin: sečtu velikosti jednotlivých množin, odečtu průniky dvojic, přičtu průniky trojic, … až po (−1)ⁿ⁺¹ |A₁ ∩ A₂ ∩ ⋯ ∩ A_n|.

|A ∪ B ∪ C| = Σ |X| − Σ |X ∩ Y| + |A ∩ B ∩ C|

Σ |X|: hrubý součet |A| + |B| + |C|; prvek ve dvou množinách je započítaný dvakrát, prvek ve všech třech třikrát
− Σ |X ∩ Y|: průniky všech tří dvojic; opraví prvky ve dvou množinách na jedničku — ale prvek ve všech třech odečte třikrát, takže klesne na nulu
+ průnik trojice: vrátí prvkům ve všech třech množinách jejich jedničku

Střídání znamének zajistí, že každý prvek sjednocení se započítá právě jednou.

Příklad — čísla dělitelná 2, 3 nebo 5

Kolik čísel z {1, …, 100} je dělitelných 2, 3 nebo 5? Označím A, B, C čísla dělitelná 2, 3 a 5.

|A| = 50, |B| = 33, |C| = 20;
|A ∩ B| = 16 (dělitelná 6), |A ∩ C| = 10 (dělitelná 10), |B ∩ C| = 6 (dělitelná 15);
|A ∩ B ∩ C| = 3 (dělitelná 30).

|A ∪ B ∪ C| = 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74. Zbylých 26 čísel není dělitelných ani jedním z nich.

Věta — Dirichletův (holubníkový) princip

Máme-li roztřídit kn + 1 objektů (k ≥ 1) do n tříd, existuje aspoň jedna třída, ve které je aspoň k + 1 objektů.

Název „holubníkový“ je z obrázku holubů a holubníku: vletí-li 11 holubů do 10 otvorů, v některém otvoru jsou aspoň dva.

Laicky řečeno

Kdyby v každé třídě bylo nejvýš k objektů, vešlo by se jich dohromady jen kn — o jeden méně, než kolik jich máme. Ve skupině 25 studentů (25 = 2 · 12 + 1) se tedy aspoň tři narodili ve stejném měsíci, i když nevíme ve kterém.

6. Relace, její obory, inverze a skládání

Definice — binární relace

Binární relace je každá množina uspořádaných dvojic („binární“ = mezi dvěma prvky). Je-li R relace, píšeme aRb nebo [a, b] ∈ R a čteme „prvek a je v relaci R s prvkem b“.

Definiční obor (první obor): a ∈ D(R) ⇔ ∃b; aRb.
Obor hodnot (druhý obor): b ∈ H(R) ⇔ ∃a; aRb.
Je-li D(R) ⊆ A a H(R) ⊆ B, je R relace z množiny A do množiny B (tj. R ⊆ A × B); pro A = B mluvíme o relaci na A.
n-ární relace (n ∈ ℕ) je každá množina uspořádaných n-tic [a₁, …, a_n] — obdoba dvojice s n složkami v pevném pořadí. Pro n = 3 se jí říká ternární.

Laicky řečeno

Relace je seznam dvojic „kdo s kým“ — třeba tabulka v databázi se sloupci student a předmět. Definiční obor jsou všichni, kdo se v levém sloupci aspoň jednou objeví, obor hodnot všechno, co se objeví v pravém. Tabulka se třemi sloupci by byla ternární relace.

Definice — doplňková, identická a inverzní relace

Je-li R relace na A, je i R = A² ∖ R relace na A — doplňková (komplementární) relace. A² = A × A jsou všechny možné dvojice, doplňková relace tedy obsahuje přesně ty dvojice, které v R nejsou (k „dělí“ je to „nedělí“).

Identická (diagonální) relace na A je Δ_A = {[a, a]; a ∈ A} — každý prvek je v relaci jen sám se sebou; je to relace rovnosti. „Diagonální“ proto, že v tabulce A × A zabírá právě úhlopříčku. (Δ tu neznamená symetrický rozdíl, jen stejný symbol.)

Inverzní relace k R je R⁻¹ = {[a, b]; [b, a] ∈ R} — vznikne prohozením složek v každé dvojici (inverze k „je rodičem“ je „je dítětem“); zřejmě (R⁻¹)⁻¹ = R.

Relace jsou množiny, takže jsou-li R, S relace na A × B, jsou jimi i R ∪ S, R ∩ S a R ∖ S.

Definice — skládání relací

R ∘ S = {[a, c]; ∃b: [a, b] ∈ S ∧ [b, c] ∈ R}.

Pozor na pořadí: nejdřív se jde podle S (pravé), pak podle R. Skládání je asociativní (nezáleží na uzávorkování) a inverze složení je složení inverzí v opačném pořadí:

(R ∘ S) ∘ T = R ∘ (S ∘ T), (R ∘ S)⁻¹ = S⁻¹ ∘ R⁻¹.

Laicky řečeno

Skládání je „přestup“: z a se dostanu přes S do nějakého b a z b přes R do c. Zápis je jako u funkcí — g(f(x)) se píše g ∘ f a provede se nejdřív f. Inverze otočí všechny šipky, a proto musí otočit i pořadí: kdo jde zpátky, projde nejdřív poslední úsek.

Příklad — složení a inverze

S = {[1, a], [2, b], [3, a]} z {1, 2, 3} do {a, b}, R = {[a, x], [b, y], [b, z]} z {a, b} do {x, y, z}.

Z 1 vede S do a a odtud R do x; z 2 do b a odtud do y i z; z 3 do a a do x:

R ∘ S = {[1, x], [2, y], [2, z], [3, x]}.

Inverze: (R ∘ S)⁻¹ = S⁻¹ ∘ R⁻¹ = {[x, 1], [x, 3], [y, 2], [z, 2]}. Složení S ∘ R je tu prázdné — H(R) a D(S) nemají nic společného, takže skládání obecně není komutativní.

7. Vlastnosti relací

Definice — speciální vlastnosti relace R na množině A

reflexivní: ∀a ∈ A: aRa — každý prvek je v relaci sám se sebou (≤, „dělí“, „je stejně starý jako“);
symetrická: ∀a, b ∈ A: aRb ⇒ bRa — vztah platí vždy oběma směry („je sourozencem“, „sedí vedle“);
tranzitivní: ∀a, b, c ∈ A: aRb ∧ bRc ⇒ aRc — vztah se „přenáší“ přes prostředníka (je-li a starší než b a b starší než c, je a starší než c);
antisymetrická: ∀a, b ∈ A: aRb ∧ bRa ⇒ a = b — dva různé prvky nikdy nejsou v relaci oběma směry (≤: z a ≤ b a b ≤ a plyne a = b). Není to opak symetrie — relace může být obojí (rovnost) i ani jedno;
ireflexivní: ∀a ∈ A: ¬ aRa — žádný prvek není v relaci sám se sebou (<, „je rodičem“);
souvislá: ∀a, b ∈ A: a ≠ b ⇒ aRb ∨ bRa — každé dva různé prvky jdou porovnat aspoň jedním směrem;
trichotomická: pro každé a, b ∈ A platí právě jeden ze vztahů a = b, aRb, bRa („trichotomie“ = rozdělení na tři možnosti; typicky < na číslech).

Laicky řečeno

V matici relace (řádek a, sloupec b, tečka = dvojice v relaci) se vlastnosti dají „vidět“: reflexivní má tečky na celé diagonále, ireflexivní žádnou; symetrická je souměrná podle diagonály; antisymetrická nemá žádnou dvojici teček souměrnou mimo diagonálu; souvislá má mimo diagonálu u každé dvojice políček aspoň jednu tečku. Jen tranzitivitu z obrázku nepoznáte — tu je potřeba projít cesty a → b → c a zkontrolovat, že vede i zkratka a → c.

matice: řádek a, sloupec b

graf: šipka a → b (bez smyček a → a)

Relace „a dělí b“ na množině {1, …, 6} dvojic v relaci: 14

Příklad — dělitelnost a „menší než“

Dělitelnost na {1, …, 6} má 14 dvojic (obrázek výše). Je

reflexivní — každé číslo dělí samo sebe;
antisymetrická — dělí-li a číslo b i b číslo a, je a = b;
tranzitivní — a | b a b | c dává a | c;
není symetrická (1 | 2, ale 2 ∤ 1) a není souvislá (2 ani 3 nedělí druhé z nich).

Doplňková relace „a nedělí b“ má 36 − 14 = 22 dvojic.

„Menší než“ na {1, 2, 3} je ireflexivní, antisymetrická (předpoklad a < b ∧ b < a nikdy nenastane), tranzitivní, souvislá a trichotomická — pro každá dvě čísla platí právě jedno z a = b, a < b, b < a.

8. Uzávěry relací

Definice — reflexivní, symetrický a tranzitivní uzávěr

Nechť R je binární relace na M.

Reflexivní uzávěr je R ∪ {(x, x) | x ∈ M}.
Symetrický uzávěr je {(x, y) | (x, y) ∈ R nebo (y, x) ∈ R}.
Tranzitivní uzávěr je R⁺ = ⋃_i=1^∞ Tⁱ(R), kde T(S) = S ∪ {(x, z) | existuje y: (x, y), (y, z) ∈ S} — jeden krok přidá zkratky přes jednoho prostředníka — a Tⁱ je i-krát iterované (opakovaně za sebou provedené) použití T: T²(R) = T(T(R)). Velké ⋃ je sjednocení všech těchto relací.

Laicky řečeno

Uzávěr je „doplň nejméně, co musíš, aby vlastnost platila“. Reflexivní přidá smyčky, symetrický ke každé šipce šipku zpátky. Tranzitivní přidává zkratky — a protože nové zkratky vytvoří nové cesty, opakuje se to, dokud se nic nezmění. Výsledek odpovídá na otázku „dá se z x nějak dojít do z?“.

Příklad — uzávěry „řetízku“

M = {1, 2, 3, 4}, R = {(1, 2), (2, 3), (3, 4)} — tři dvojice.

reflexivní uzávěr: přidá (1, 1), …, (4, 4) — celkem 7 dvojic;
symetrický uzávěr: přidá (2, 1), (3, 2), (4, 3) — celkem 6 dvojic;
tranzitivní uzávěr: T(R) přidá (1, 3) a (2, 4), T²(R) ještě (1, 4) a T³ už nic nového nepřinese. R⁺ = {(a, b); a < b} má 6 dvojic.

9. Ekvivalence a rozklad množiny

Definice — rozklad množiny

Nechť A je neprázdná množina. Systém S podmnožin A (množina, jejímiž prvky jsou podmnožiny A) je rozklad množiny A, jestliže

∅ ∉ S — žádná třída není prázdná,
∀B, C ∈ S: B ≠ C ⇒ B ∩ C = ∅ — různé třídy jsou disjunktní (nemají žádný společný prvek),
⋃S = A — sjednocení všech tříd je celé A, žádný prvek nezůstane mimo.

Definice — ekvivalence, třída a faktorová množina

Relace R na A je ekvivalence, je-li reflexivní, symetrická a tranzitivní.

Věta. Je-li R ekvivalence na A a pro a ∈ A je [a] = {x ∈ A; xRa}, pak S = {[a]; a ∈ A} je rozklad množiny A.

Množina [a] je třída rozkladu podle R daná prvkem a; systém všech tříd se značí A/R a nazývá faktorová množina množiny A podle R.

Laicky řečeno

Ekvivalence je „považuj za stejné“ — mít stejný zbytek, stejnou barvu, stejný ročník. Takové „stejné“ nutně roztřídí prvky do přihrádek, které se nepřekrývají a nic nezůstane mimo: to je rozklad. A naopak, každý rozklad dává ekvivalenci „být ve stejné přihrádce“. Faktorová množina je množina přihrádek — každá přihrádka se v ní stane jedním prvkem.

třída [0] {0, 3, 6}

třída [1] {1, 4, 7}

třída [2] {2, 5, 8}

Rozklad {0, …, 8} podle zbytku po dělení 3

Ekvivalence „a a b mají stejný zbytek po dělení 3“ na {0, …, 8} je reflexivní, symetrická i tranzitivní. Třídy jsou [0] = {0, 3, 6}, [1] = {1, 4, 7} a [2] = {2, 5, 8}; faktorová množina má 3 prvky. Třídu lze pojmenovat kterýmkoli jejím prvkem — [3] je táž třída jako [0].

10. Uspořádání a Hasseův diagram

Definice — částečné a lineární uspořádání

Relace R ⊆ M × M je (částečné) uspořádání, právě když je reflexivní, antisymetrická a tranzitivní. K důkazu, že relace je uspořádáním, je potřeba ověřit všechny tři vlastnosti.

Uspořádaná množina je dvojice (M, ⪯), kde ⪯ je uspořádání na M (symbol ⪯ se čte „je menší nebo rovno“ v obecném smyslu, „je pod“). Prvky x, y jsou porovnatelné, platí-li x ⪯ y nebo y ⪯ x. Uspořádání je lineární (úplné), jsou-li každé dva prvky M porovnatelné — prvky pak jdou seřadit do jedné řady (lineární = „v přímce“).

Další typy: kvaziuspořádání je reflexivní a tranzitivní relace bez požadavku antisymetrie — dva různé prvky smějí být „na stejné úrovni“ (např. lidé porovnaní podle věku: dva stejně staří jsou v relaci oběma směry, a přitom to nejsou tíž lidé). Dobré uspořádání je takové, ve kterém každá (neprázdná) podmnožina má nejmenší prvek.

Laicky řečeno

Uspořádání je „je pod / je před“, které se nezacyklí. „Částečné“ znamená, že některé dvojice srovnat nejde — 2 a 3 se dělitelností neporovnají, žádné z nich nedělí druhé. ≤ na číslech je lineární, srovná cokoli. A ≤ na ℕ je dokonce dobré uspořádání (každá množina přirozených čísel má nejmenší), kdežto na ℤ ne — celá záporná čísla nejmenší prvek nemají.

Definice — význačné prvky a meze

Nechť (M, ⪯) je uspořádaná množina. Prvek x ∈ M je

minimální, právě když pro každé y ∈ M: y ⪯ x ⇒ x ⪯ y (pod ním nic jiného neleží);
maximální, právě když pro každé y ∈ M: x ⪯ y ⇒ y ⪯ x;
nejmenší, právě když x ⪯ y pro každé y ∈ M; největší, právě když y ⪯ x pro každé y;
x pokrývá y, právě když x ≠ y, y ⪯ x a neexistuje z ∉ {x, y} s y ⪯ z ⪯ x — x je „hned nad“ y, bez mezikroku;
dolní mez (závora, ohraničení) množiny A ⊆ M, je-li x ⪯ y pro každé y ∈ A — leží pod všemi prvky A; horní mez, je-li y ⪯ x pro každé y ∈ A — leží nad všemi. Mez nemusí být prvkem A;
infimum množiny A je její největší dolní mez, supremum její nejmenší horní mez.

Laicky řečeno

Minimální = „pod ním nikdo není“, nejmenší = „je pod všemi“. Rozdíl je vidět, když je minimálních prvků víc: pak žádný z nich nejmenší není. Nejmenší prvek je vždy jediný a je zároveň minimální. Infimum je „nejlepší možné dno“ — ze všech prvků, které jsou pod celou množinou, ten nejvyšší.

Definice — Hasseův diagram

Hasseův diagram konečné uspořádané množiny (M, ⪯) je jednoznačné grafické znázornění: do první vodorovné vrstvy se zakreslí minimální prvky. Máme-li vrstvu i, zakreslí se do vrstvy i + 1 (nad ní) všechny dosud nezakreslené prvky, které pokrývají jen prvky vrstev ≤ i. Pokrývá-li prvek x vrstvy i + 1 prvek y nižší vrstvy, spojí se x a y neorientovanou čarou — čarou bez šipky.

Proč: graf relace (každý prvek jako bod, každá dvojice [a, b] jako šipka a → b) je u uspořádání nepřehledný. Hasseův diagram vynechá smyčky a → a (z reflexivity jsou jasné) i zkratky (z tranzitivity se domyslí — x ⪯ y platí, právě když se z x dá dojít po čarách stále nahoru do y) a šipky nahradí směr „zdola nahoru“.

Dělitelé čísla 12 uspořádaní dělitelností

Příklad — dělitelé 12

(M, |) s M = {1, 2, 3, 4, 6, 12}. Relace „dělí“ tu má 18 dvojic, Hasseův diagram jen 7 čar — kreslí se jen pokrytí: 1–2, 1–3, 2–4, 2–6, 3–6, 4–12, 6–12. Prvek 4 pokrývá 2, ale nepokrývá 1, protože mezi nimi leží 2.

1 je nejmenší (a jediný minimální), 12 největší (a jediný maximální) prvek;
uspořádání není lineární: 4 a 6, stejně jako 2 a 3, jsou neporovnatelné;
pro A = {4, 6}: horní meze jsou {12}, takže supremum je 12; dolní meze jsou {1, 2} a infimum (největší z nich) je 2.

Supremum dvou čísel je tu jejich nejmenší společný násobek (nejmenší číslo, které obě dělí) a infimum největší společný dělitel (největší číslo, které dělí obě).

11. Zobrazení: injekce, surjekce, bijekce

Definice — zobrazení, obraz a úplný vzor

Binární relace f je zobrazení, jestliže

[a, b] ∈ f ∧ [a, c] ∈ f ⇒ b = c.

Má definiční obor D(f) a obor hodnot H(f) jako každá relace.

Obraz množiny: f(M) = {b; ∃a ∈ M: f(a) = b}.
Úplný vzor množiny: f⁻¹(P) = {a; ∃b ∈ P: f(a) = b}.

Laicky řečeno

Zobrazení je relace, ve které z každého prvku vede nejvýš jedna šipka — proto má smysl psát f(a) jako „ta jediná hodnota“. Do jednoho prvku ale klidně může šipek vést víc. Obraz je „kam se dostanu z M“, úplný vzor „odkud se dostanu do P“.

Definice — injekce, surjekce, bijekce

Zobrazení je prosté (injekce), jestliže ∀a, b ∈ D(f): a ≠ b ⇒ f(a) ≠ f(b).
Zápis f: A → B říká, že f bere prvky z A a hodnoty dává v B. Je-li D(f) = A (každý prvek A má hodnotu), je f zobrazení množiny A do množiny B. Je-li H(f) = B (každý prvek B je hodnotou něčeho), je to zobrazení na B neboli surjekce; s D(f) = A i H(f) = B jde o zobrazení množiny A na množinu B.
Prosté zobrazení A na B je vzájemně jednoznačné zobrazení neboli bijekce — každému prvku A odpovídá právě jeden prvek B a naopak.
Každé prosté zobrazení je bijekcí svého definičního oboru na svůj obor hodnot.

Laicky řečeno

Injekce: žádné dva prvky nesdílí cíl. Surjekce: žádný cíl nezůstane bez šipky. Bijekce: obojí — prvky obou množin jdou spárovat jedna k jedné, jako lidé a jejich místa v plně obsazeném sále s místenkami.

Zobrazení f(x) = x mod 3 z {1, …, 6} na {0, 1, 2}

Definice — ekvivalentní množiny a jádro zobrazení

Existuje-li bijekce A na B, je množina A ekvivalentní s B, píšeme A ∼ B. Pro libovolné A, B, C platí A ∼ A, A ∼ B ⇒ B ∼ A a A ∼ B ∧ B ∼ C ⇒ A ∼ C.

Ekvivalentní množiny mají „stejně prvků“ — u konečných množin to znamená stejný počet.

Pro zobrazení f: A → B definujeme na A relaci a ∼ b ⇔ f(a) = f(b) — dva prvky jsou „stejné“, když se zobrazí na stejnou hodnotu. Říká se jí jádro zobrazení. Je to ekvivalence na A a faktorová množina A/∼ je ekvivalentní s oborem hodnot H(f): každá třída odpovídá právě jedné hodnotě.

Příklad — zbytek po dělení 3

f(x) = x mod 3 na A = {1, …, 6} (obrázek výše).

Je to zobrazení: z každého čísla vede jediná šipka. D(f) = A, H(f) = {0, 1, 2}, takže jde o surjekci A na {0, 1, 2}.
Není prosté: f(1) = f(4) = 1. Šest prvků se do tří prostě zobrazit nedá — to je Dirichletův princip.
Obraz f({1, 2}) = {1, 2}, úplný vzor f⁻¹({0}) = {3, 6}.
Ekvivalence f(a) = f(b) rozloží A na třídy {1, 4}, {2, 5}, {3, 6}. Faktorová množina má 3 prvky — stejně jako H(f), přesně podle věty.

12. Mohutnost: spočetné a nespočetné množiny

Definice — spočetná a nespočetná množina

Množiny jsou konečné a nekonečné. Nekonečná množina je

spočetná, existuje-li bijekce s množinou přirozených čísel (A ∼ ℕ),
nespočetná, neexistuje-li bijekce s množinou přirozených čísel.

Laicky řečeno

Dvě množiny mají „stejně prvků“, když jdou spárovat jedna k jedné — u nekonečných množin jiné měřítko nemáme. Spočetná množina je taková, jejíž prvky jde seřadit do (nekonečné) fronty a očíslovat 1, 2, 3, … tak, aby se na každý jednou dostalo. Překvapivě i „menší“ část může mít stejně prvků jako celek: sudá čísla ∼ ℕ přes bijekci n ↦ 2n.

Dva klasické příklady ukazují, že nekonečna nejsou stejně velká. Racionální čísla jsou spočetná: zlomky p/q se zapíšou do nekonečné tabulky (řádek p, sloupec q) a projdou se po šikmých úhlopříčkách — 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, … — přičemž se přeskočí zlomky, které už se objevily v jiném tvaru (2/2 = 1/1). Každá úhlopříčka je konečná, takže na každý zlomek se jednou dojde a dostane své pořadové číslo.

Reálná čísla spočetná nejsou (Cantorova diagonální metoda): kdyby šla všechna čísla z (0, 1) očíslovat jako r₁, r₂, … a zapsat pod sebe v desetinném rozvoji, sestrojím číslo, které má na n-tém místě za čárkou jinou číslici než r_n. Od každého r_n se liší aspoň na jednom místě, takže v seznamu chybí — spor s předpokladem, že seznam obsahuje všechna. ℝ je tedy „větší“ nekonečno než ℕ a ℚ.

13. Shrnutí ke zkoušce

Množina je primitivní pojem, zadává se výčtem nebo výrokovou formou; A = B ⇔ A ⊆ B ∧ B ⊆ A. ∅ ≠ {∅}.
Operace ∪, ∩, ∖, doplněk a Δ odpovídají spojkám ∨, ∧, „a ne“, ¬ a XOR. De Morgan: (A ∪ B)′ = A′ ∩ B′, (A ∩ B)′ = A′ ∪ B′. Rozdíl není komutativní, asociativní ani distributivní.
Kartézský součin = množina uspořádaných dvojic; 𝒫(X) má 2^|X| prvků; inkluze a exkluze střídá znaménka; Dirichlet: kn + 1 objektů v n třídách ⇒ někde aspoň k + 1.
Relace = množina dvojic, D(R), H(R), R⁻¹; R ∘ S provede nejdřív S; (R ∘ S)⁻¹ = S⁻¹ ∘ R⁻¹.
Vlastnosti: reflexivní, symetrická, tranzitivní, antisymetrická, ireflexivní, souvislá, trichotomická. Uzávěr doplní nejméně dvojic, aby vlastnost platila; tranzitivní uzávěr iteruje přidávání zkratek.
Ekvivalence (R + S + T) ⇔ rozklad (neprázdné, disjunktní třídy pokrývající A); A/R je faktorová množina.
Uspořádání (R + A + T), lineární, kvazi-, dobré; minimální vs. nejmenší, pokrytí, meze, infimum a supremum; Hasseův diagram kreslí jen pokrytí po vrstvách.
Zobrazení = relace s nejvýš jednou hodnotou; injekce, surjekce, bijekce; A ∼ B přes bijekci; jádro f(a) = f(b) je ekvivalence s A/∼ ∼ H(f).
Mohutnost: spočetná = bijekce s ℕ. ℚ je spočetná (úhlopříčky), ℝ nespočetná (diagonální metoda).

Zdroje

IDM — Množiny (prezentace, P. Hliněná, 2025/26)
IDM — Relace a zobrazení (prezentace, P. Hliněná, 2025/26)

Zpátky na přehled okruhů