Množiny a zobrazení

Množiny

Definice: Množina nechť je základním objektem teorie množin (uvažujme Zermleovu a Fraenkenovu teorii). Jazykem dané teorie množin rozumíme symboly:

1. proměnné pro množiny
2. binární predikátový symbol rovnosti $=$
3. binární predikátový symbol náležení $\in$
4. symboly logiky jako $\neg$ negace, $\wedge$ konjunkce, $\vee$ disjunkce, $\to$ implikace, $\leftrightarrow$ ekvivalence
5. kvantifikátory $\forall$ obecný a $\exists$ existenční
6. pomocné další symboly jako třeba závorky

Základní jazyk také rozšíříme o symboly $\subseteq ,\subset$. Říkáme, že množina $x$ je podmnožinou $y$ a píšeme $x\subseteq y$, platí-li $(\forall a)(a\in x\to a\in y)$. Říkáme o $x$, že je vlastní podmnožinou y a píšeme $x\subset y$, je-li $x\subseteq y$ a $x\ne y$. Symboly zveme inkluzemi.

Potenční množinu, jenž jest složena ze všech podmnožin dané množiny $a$, zavádíme jako

$$\mathcal{P}(a)=2^a=\{x:x\subseteq a\}.$$

Suma na množině $a$ je definovaná výrazem

$$\bigcup a=\{x:(\exists y)(x\in y\wedge y\in a)\}.$$

Třídy

Každá formule $\phi (x)$ určuje soubor všech množin $x$, pro které platí, značme ho výrazem

$$\{x:\phi (x)\}.$$

Takovému zápisu za předpokladu, že $\phi (x)$ je formule jazyka teorie množin, říkáme třídový term. Tento soubor zveme třídou, určenou formulí $\phi (x)$. Máme navíc dva typy tříd:

1. množina, tedy platí-li formule

$$(\forall x)(x\in z\leftrightarrow \phi (x))$$

pro nějakou formuli $z$

2. jinak ji říkáme vlastní třídou

Univerzální třídu značíme $V$.

Definice: Kartézský součin tříd $A,B$ je třída

$$A\times B=\{⟨a,b⟩:a\in A\wedge b\in B\}=\{x:(\exists a)(\exists b)(x=⟨a,b⟩\wedge a\in A\wedge b\in B)\}.$$

Lemma: Pro libovolné množiny $x,y$ je $x\times y$ také množina. Důkaz: Vzhledem k tomu, že se dá jednoduše ověřit platnost

$$(A\subseteq A_1\wedge B\subseteq B_1)\to (A\times B\subseteq A_1\times B_1),$$

tak berouc $z=x\cup y$ je pravdou $x\times y\subseteq z\times z$. Dle schématu vydělení stačí dokázat $z\times z$ je množinou. A tedy vezměme libovolný prvek $⟨u,v⟩z\times z$, tedy $u,v\in z$. Potom

$$\{u\}\subseteq z,\{u,v\}\subseteq z,$$

a proto máme $\{u\}\subseteq \mathcal{P}(z)$, $\{u,v\}\subseteq \mathcal{P}(z)$. Opakováním naší úvahy dostáváme $\{\{u\},\{u,v\}\}=⟨u,v⟩\subseteq \mathcal{P}(z)$, odkud nám z definice potenční množiny plyne $⟨u,v⟩\in \mathcal{P}(\mathcal{P}(z))$. A máme tedy, že

$$z\times z\subseteq \mathcal{P}(\mathcal{P}(z)),$$

a dle axiomu potence víme o pravé straně inkluze množina. Proto $z\times z$ a tedy i $x\times y$ je také množina.

Relace

Definice: Třída $R$ je relace, je-li $R\subseteq V\times V$. Píšeme $⟨x,y⟩\in R$ jako $xRy$. Navíc je-li $R\subseteq V^n$ pro $n\ge 2$, říkáme, že $R$ je $n$-ární relace.

Definice: binární relace mezi množinami $X,Y$ je množina $R\subseteq X\times Y$. Příklady relací:

• $\varnothing \dots$ prázdná
• $X\times Y\dots$ univerzální
• ${\Delta }_X=\{(x,x)|x\in X\}\dots$ diagonální
• $R^{-1}:\{(y,x)|(x,y)\in R\}\dots$ inverzní
• $x(R\circ S)z\equiv \exists y\in Y:xRy\wedge ySz$

Definice: Třída

$$\text{Dom}(X)=\{u:(\exists v)(⟨u,v⟩)\in X\}$$

se nazývá definiční obor třídy $X$. Třída

$$\text{Rng}(X)=\{v:(\exists u)(⟨u,v⟩)\in X\}$$

se nazývá obor hodnot třídy $X$.

Zjevně pro libovolnou relaci $X$ platí

$$X\subseteq \text{Dom}(X)\times \text{Rng}(X).$$

Elementární vlastnosti relací:

Říkáme, že relace $R$ je na třídě $A$

1. reflexivní, jestliže pro libovolný prvek $x\in A$ platí $⟨x,x⟩\in R$
2. anti-reflexivní, jestliže pro žádný prvek $x\in A$ neplatí $⟨x,x⟩\in R$
3. symetrická, jestliže pro libovolné $x,y\in A$ platí $⟨x,y⟩\in R\to ⟨y,x⟩\in R$
4. slabě antisymetrická, jestliže pro libovolné $x,y\in A$ platí $\left(⟨x,y⟩\in R\wedge ⟨y,x⟩\in R\right)\to x=y$
5. slabě antisymetrická, jestliže pro libovolné $x,y\in A$ platí $⟨x,y⟩\in R\to ⟨y,x⟩\notin R$
6. trichotomická, jestliže pro libovolné $x,y\in A$ platí $⟨x,y⟩\in R\vee ⟨y,x⟩\in R\vee x=y$
7. tranzitivní, jestliže pro libovolné $x,y,z\in A$ platí $\left(⟨x,y⟩\in R\wedge ⟨y,z⟩\in R\right)\to ⟨x,z⟩\in R$

Ekvivalence

Definice: Relace $R$ na $X$ je ekvivalence $\equiv R$ je tranzitivní, symetrická a reflexivní. Definice: Třída ekvivalence $R$ prvku $x$ je $\{y\in X|⟨x,y⟩\in R\}$, třídu značíme $R[x]$.

Rozkladové třídy jsou právě třídy ekvivalence na ekvivalenci $R$.

Částečná uspořádání

Definice: Uspořádání je relací $R$ na třídě $A$, je-li $R$ reflexivní, antisymetrické a tranzitivní. Máme několik poddruhů:

1. lineární $\le$: $\forall x,y\in A:x\le y\vee y\le x$
2. částečné uspořádání je uspořádání nelineární
3. ostré: mějme $\le$ uspořádání, platí-li $\forall x,y\in A:x<y\equiv x\le y\wedge x\ne y$

Definice: Mějme třídu $A$, uspořádání $\le$ na této třídě a mějme $X\subseteq A$. O prvku $a\in A$ říkáme, že je

1. majoranta nebo horní mez třídy $X$, jestliže $(\forall x\in X)(x\le a)$,
2. maximální prvek třídy $X$, je-li $a\in X$ a $(\forall x\in X)(\neg a<x)$,
3. největší prvek třídy $X$, je-li $a$ majoranta $X$ a $a\in X$.
4. supremum třídy $X$, je-li $a$ nejmenší prvek třídy všech majorant třídy $X$.
5. minoranta nebo dolní mez třídy $X$, jestliže $(\forall x\in X)(x\ge a)$,
6. minimální prvek třídy $X$, je-li $a\in X$ a $(\forall x\in X)(\neg a>x)$,
7. nejmenší prvek třídy $X$, je-li $a$ minoranta $X$ a $a\in X$.
8. infimum třídy $X$, je-li $a$ největší prvek třídy všech minorant třídy $X$.

Definice: Mějme částečně uspořádanou množinu $(X,\le )$, pro ni definujeme

• Řetězec $A\subseteq X$ platí-li $\forall a,b\in A:(a\le b)\vee (b\le a)$, tedy jsou porovnatelné
  • značíme $\omega (X,\le )$ jako délku nejdelšího řetězce
• Antiřetězec $A\subseteq X$ je množina, kde žádné dva prvky nejsou porovnatelné (nezávislá množina)
  • $\alpha (X,\le )$ je délka největšího antiřetězce

Věta: (O dlouhém a širokém) Pro každou (konečnou) částečně uspořádanou množinu $(X,\le )$ platí

$$|X|\le \alpha (X,\le )\cdot \omega (X,\le ).$$

Důkaz: Iterativně prozkoumáme celou množinu $X$ a sice tak, že v prvním kroku vezmeme minimální prvky do množiny $M_1=\{x\in X|x\text{ je minimaˊlnıˊ v}\le \}$. Zavedeme si $X_1=X\setminus M_1$.

Pokračujeme až máme posloupnost $M_1,M_2,\dots ,M_k$, kde $k\le \omega (X,\le )$, protože výběrem vždy minimálních prvků v $X_{i-1}$, existuje posloupnost výběrů, že $\forall a_i\in M_i,\exists a_{i+1}\in M_{i-1}:a_{i-1}\le a_i$. Kdyby takový prvek neměl existovat tak nalezneme spor s volbou minimálního prvku při konstrukci.

Zároveň platí $\forall i\in \{1,2,\dots ,k\}:|M_i|\le \alpha (X,\le )$, protože každá $M_i$ je nezávislá množina, tedy její prvky mezi sebou nejsou porovnatelné, jinak bychom našli spor s minimalitou volby.

Kombinací odhadů nám vychází

$$|X|=\sum _{i=1}^k|M_i|\le \alpha (X,\le )\cdot \omega (X,\le ).$$