Množiny, relace a zobrazení

Note	Základní množinové operace. Relace a jejich vlastnosti – ekvivalence a rozklady, uspořádání a uspořádané množiny. Skládání relací, zobrazení (injekce, surjekce, bijekce). IB000, MB101/MB201

Teorie množin je v informatice všude. Dokládá to fakt, že většina informatických definic je tvaru "množina, na níž jsou kladeny specifické požadavky". V MZI se rozlišují dvě: naivní a Zermelova-Fraenkelova teorie množin.

Naivní teorie množin

Množina je skupina objektů. Tato skupina může obsahovat třeba nic, čtyři brambory, nebo třeba nekonečné množství kopečků vanilkové zmrzliny. Množina může dokonce obsahovat další množiny.

Problém nastává, když si představíte množinu, která obsahuje sama sebe. Taková množina přece není normální, takže si dále představíte množinu, dejme tomu $R$ , všech množin, které normální jsou, tedy neobsahují samy sebe. Je ale $R$ normální?

Pokud ano, pak $R$ musí obsahovat sama sebe, protože má obsahovat všechny normální množiny, a tím pádem $R$ normální není.

Jenže pokud $R$ normální není, pak by měla obsahovat sama sebe, ale to nemůže, protože $R$ smí obsahovat pouze normální množiny, takže $R$ normální je.

Tenhle drobný zádrhel se nazývá Russelův paradox.

Zermelova-Fraenkelova teorie množin

Zermelova-Fraenkelova (ZF) teorie množin řeší Russelův paradox svou specifičtější, axiomatickou definicí.

Axiom	Popis	Formulka
Axiom extenzionality	Množiny, které mají stejné prvky, se rovnají.	$(\forall a \forall b) (a = b ⟺ (\forall x) (x \in a ⟺ x \in b)))$
Schéma axiomů (omezeného) vyčlenění/vydělení	Lze tvořit podmnožiny takových $x$ , které splňují predikát $P (x)$ .	$(\forall a \exists b \forall x) (x \in b ⟺ (x \in a \land P (x)))$ nebo taky $b = {x \in a : P (x)}$
Axiom prázdné množiny	Existuje "nic". (Tenhle axiom je trochu zbytečný, protože plyne z Vyčlenění a neprázdnosti univerza.)	$(\exists a \forall x) (x \in / a)$
Axiom dvojice	Když dáš dohromady $rybu$ a $hranolky$ , máš množinu ${ryba, hranolky}$ .	$(\forall x \forall y \exists a \forall z) (z \in c ⟺ (z = x \lor z = y))$
Axiom sjednocení (sumy)	Množiny se dají "slít do jednoho hrníčku".	$(\forall a \exists b \forall x) (x \in b ⟺ (\exists y) (x \in y \land y \in a))$ , nebo taky $b = ⋃ a$ .
Axiom potenční množiny	Z každé množiny dokážeš vyrobit množinu všech jejích podmnožin	$(\forall a \exists b \forall x) (x \in b ⟺ (\forall z) (z \in x ⟹ z \in a))$
Schéma axiomu nahrazení	Pokud $F (x, y)$ je na dané množině zobrazením, tak můžu danou množinu zobrazit.	$(\forall a) ((\forall x \exists! y) (x \in a ⟹ F (x, y)) ⟹ (\exists b \forall z) (z \in b ⟺ (\exists v) (v \in a \land F (v, z))))$
Axiom nekonečna	Existuje $N$ resp. nekonečná množina obsahující $\emptyset, {\emptyset}, {\emptyset, {\emptyset}}$ , atd.	$(\exists a) (\emptyset \in a \land (\forall x) (x \in a ⟹ x \cup {x} \in a))$
Axiom regularity (fundovanosti)	Když už množina $a$ něco obsahuje, tak má alespoň jeden prvek $b$ , který má s $a$ prázdný průnik. Tohle zabraňuje konstrukci množin, které obsahují samy sebe.	$(\forall a) (a \neq = \emptyset ⟹ (\exists b \in a) (b \cap a = \emptyset))$

Axiom

Popis

Formulka

Axiom extenzionality

Množiny, které mají stejné prvky, se rovnají.

$(\forall a \forall b) (a = b ⟺ (\forall x) (x \in a ⟺ x \in b)))$

Schéma axiomů (omezeného) vyčlenění/vydělení

Lze tvořit podmnožiny takových $x$ , které splňují predikát $P (x)$ .

$(\forall a \exists b \forall x) (x \in b ⟺ (x \in a \land P (x)))$ nebo taky $b = {x \in a : P (x)}$

Axiom prázdné množiny

Existuje "nic". (Tenhle axiom je trochu zbytečný, protože plyne z Vyčlenění a neprázdnosti univerza.)

$(\exists a \forall x) (x \in / a)$

Axiom dvojice

Když dáš dohromady $rybu$ a $hranolky$ , máš množinu ${ryba, hranolky}$ .

$(\forall x \forall y \exists a \forall z) (z \in c ⟺ (z = x \lor z = y))$

Axiom sjednocení (sumy)

Množiny se dají "slít do jednoho hrníčku".

$(\forall a \exists b \forall x) (x \in b ⟺ (\exists y) (x \in y \land y \in a))$ , nebo taky $b = ⋃ a$ .

Axiom potenční množiny

Z každé množiny dokážeš vyrobit množinu všech jejích podmnožin

$(\forall a \exists b \forall x) (x \in b ⟺ (\forall z) (z \in x ⟹ z \in a))$

Schéma axiomu nahrazení

Pokud $F (x, y)$ je na dané množině zobrazením, tak můžu danou množinu zobrazit.

$(\forall a) ((\forall x \exists! y) (x \in a ⟹ F (x, y)) ⟹ (\exists b \forall z) (z \in b ⟺ (\exists v) (v \in a \land F (v, z))))$

Axiom nekonečna

Existuje $N$ resp. nekonečná množina obsahující $\emptyset, {\emptyset}, {\emptyset, {\emptyset}}$ , atd.

$(\exists a) (\emptyset \in a \land (\forall x) (x \in a ⟹ x \cup {x} \in a))$

Axiom regularity (fundovanosti)

Když už množina $a$ něco obsahuje, tak má alespoň jeden prvek $b$ , který má s $a$ prázdný průnik. Tohle zabraňuje konstrukci množin, které obsahují samy sebe.

$(\forall a) (a \neq = \emptyset ⟹ (\exists b \in a) (b \cap a = \emptyset))$

Note	Když se do ZF přidá axiom výběru, vyleze z toho ZFC.

Základní množinové operace

Operace	Formulka
sjednocení	$A \cup B = {x ∣ x \in A \lor x \in B}$
průnik	$A \cap B = {x ∣ x \in A \land x \in B}$
rozdíl	$A ∖ B = {x ∣ x \in A \land x \in / B}$
symetrický rozdíl	$A Δ B = (A \cup B) ∖ (A \cap B)$
potenční množina	$2^{A} = {B ∣ B \subseteq A}$
kartézský součin	$A \times B = {(a, b) ∣ a \in A \land b \in B}$

Operace

Formulka

sjednocení

$A \cup B = {x ∣ x \in A \lor x \in B}$

průnik

$A \cap B = {x ∣ x \in A \land x \in B}$

rozdíl

$A ∖ B = {x ∣ x \in A \land x \in / B}$

symetrický rozdíl

$A Δ B = (A \cup B) ∖ (A \cap B)$

potenční množina

$2^{A} = {B ∣ B \subseteq A}$

kartézský součin

$A \times B = {(a, b) ∣ a \in A \land b \in B}$

Vlastnosti množinových operací

Vlastnost	Formulka
Komutativita	$A \cap B = B \cap A$ $A \cup B = B \cup A$
Asociativita	$A \cap (B \cap C) = (A \cap B) \cap C$ $A \cup (B \cup C) = (A \cup B) \cup C$
Distributivita	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Vlastnost

Formulka

Komutativita

$A \cap B = B \cap A$
$A \cup B = B \cup A$

Asociativita

$A \cap (B \cap C) = (A \cap B) \cap C$
$A \cup (B \cup C) = (A \cup B) \cup C$

Distributivita

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Relace

Binární relace $R$ je podmnožinou kartézské součinu dvou množin: $R \subseteq A \times B$ .

Vlastnosti binarních relací $R \subseteq A \times A$

Vlastnost relace	Formulka
Reflexivní	$(\forall a \in A) ((a, a) \in R)$
Ireflexivní	$(\forall a \in A) ((a, a) \in / R)$
Symetrická	$(\forall a, b \in A) ((a, b) \in R ⟹ (b, a) \in R)$
Antisymetrická	$(\forall a, b \in A) (((a, b) \in R \land (b, a) \in R) ⟹ a = b)$
Tranzitivní	$(\forall a, b, c \in A) (((a, b) \in R \land (b, c) \in R) ⟹ (a, c) \in R)$

Vlastnost relace

Formulka

Reflexivní

$(\forall a \in A) ((a, a) \in R)$

Ireflexivní

$(\forall a \in A) ((a, a) \in / R)$

Symetrická

$(\forall a, b \in A) ((a, b) \in R ⟹ (b, a) \in R)$

Antisymetrická

$(\forall a, b \in A) (((a, b) \in R \land (b, a) \in R) ⟹ a = b)$

Tranzitivní

$(\forall a, b, c \in A) (((a, b) \in R \land (b, c) \in R) ⟹ (a, c) \in R)$

Relační pojmy

[Reflexivní | symetrický | tranzitivní] uzávěr

Nejmenší nadmnožina $R$ taková, že splňuje vlastnost z názvu.

Předuspořádání (kvaziuspořádání)

Reflexivní a tranzitivní binární relace.

Částečné uspořádání na $A$

Reflexivní, antisymetrická a tranzitivní binární relace na $A$ .

Lineární (úplné) uspořádání

Uspořádání, kde jsou každé dva prvky srovnatelné.

Ekvivalence

Reflexivní, symetrická a tranzitivní binární relace.

Rozklad (quotient set)

Každá ekvivalence $\sim$ "rozkládá" množinu $A$ , na které je definována, na vzájemně disjunktní podmnožiny — třídy rozkladu. Píšeme $A / \sim$ . Rozklad $R$ je pak množina tříd rozkladu. Ke třídě rozkladu se dostaneme skrze reprezentanta $a$ : $[a]_{R} = {x ∣ x \sim a}$ . Pár faktů:

$\emptyset \in / R$
$⋃_{C \in R} = A$
Každá ekvivalence jednoznačně určuje rozklad. A obráceně.

Skládání relací

Dejme tomu, že $(a, b) \in P$ , když $a$ sedí napravo od $b$ , a $(c, d) \in D$ , když $c$ sedí pod $d$ . Pak $(e, f) \in (D \circ P)$ (D po P), když $e$ sedí vpravo dole pod $f$ (a někdo sedí i ve vzniknuvším rohu).

(e, f) \in (D \circ P) ⟺ (\exists x) (P (e, x) \land D (x, f))

Pojmy uspořádaných množin

Uspořádaná množina

Dvojice $(A, \leq)$ , kde $A$ je množina a $\leq$ je částečné uspořádání na $A$ .

Minimální prvek

Není prvek uspořádané množiny, který by byl menší. Může jich být více. Anglicky minimal element.

Maximální prvek

Není prvek uspořádané množiny, který by byl větší. Může jich být více. Anglicky maximal element.

Nejmenší prvek

Prvek uspořádané množiny menší než všechny ostatní. Je nejvýše jeden. Anglicky least element nebo taky minimum.

Největší prvek

Prvek uspořádané množiny větší než všechny ostatní. Je nejvýše jeden. Anglicky greatest element nebo taky maximum.

Horní a dolní závora

Mějme uspořádanou množinu $A$ a její podmnožinu $B \subseteq A$ .

Horní závora (upper bound) je prvek $u \in A$ takový, že $(\forall x \in B) (x \leq u)$ .
Dolní závora (lower bound) je prvek $l \in A$ takový, že $(\forall x \in B) (l \leq x)$ .

Infimum a supremum

Infimum je nejmenší horní závora.
Supremum je největší dolní závora.

Představ si množinu $A$ jako dálnici. Dálnice (přinejmenším D1) je vlastně taková množina volně spojených, diskrétních panelů. Panely blíže tvému auto u a za tvým autem jsou "menší" než panely, co tě teprve čekají. Množina $B$ je pak jako placený úsek dálnice. Infimum by byla doslova závora na začátku tohohle úseku a supremum by pak byla závora na jeho konci.

Řetězec

$B \subseteq A$ je řetězec v uspořádání $\leq$ , právě když $(B, \leq)$ je lineárně uspořádaná množina.

Pokrývá

$x \in A$ pokrývá $y \in A$ , právě když $x \neq = y$ , $x \leq y$ a neexistuje $z \in A$ takové, že $z \neq = x$ , $z \neq = y$ a $x \leq z \leq y$ .

Pojmy zobrazení

Částečné zobrazení (partial map): Je binární relace $F \subseteq A \times B$ taková, že

$(\forall a \in A) (\forall x \in B) (\forall y \in B) (((a, x) \in F \land (a, y) \in F) ⟹ x = y)$

Tedy každý vzor má nejvýše jeden obraz. Píšeme $F : A \to B$ — zobrazení z $A$ do $B$ . Taky píšeme $f (a) = b$ , když $(a, b) \in F$ .
Definiční obor (domain): $A$
Obor hodnot (codomain): $B$
Vzory: Prvky $A$ .
Obrazy: Prvky $B$ .
Totální zobrazení (total map): Je parciální zobrazení, ale navíc platí $(\forall a \in A) (\exists b \in B) ((a, b) \in F)$ . (To, že takové $b$ bude právě jedno, už zajišťuje definice výše.) Tedy každý vzor má právě jeden obraz.
Injekce: Injektivní (prostá) funkce (zobrazení) je funkce taková, že

$(\forall x \in A) (\forall y \in A) (x \neq = y ⟹ f (x) \neq = f (y))$

Tedy každý vzor má svůj vlastní obraz.
Surjekce: Surjektivní funkce (zobrazení) je taková, že

$(\forall b \in B) (\exists a \in A) (b = f (a))$

Tedy každý obraz má svůj vzor.
Bijekce: Je funkce, která je zároveň injektivní i surjektivní (vzájemně jednoznačná).

Naivní teorie množin

Zermelova-Fraenkelova teorie množin

Základní množinové operace

Vlastnosti množinových operací

Relace

Vlastnosti binarních relací R⊆A×A

Relační pojmy

Pojmy uspořádaných množin

Pojmy zobrazení

Vlastnosti binarních relací $R \subseteq A \times A$