01ALG:Kapitola1

Z WikiSkripta FJFI ČVUT v Praze
Verze z 24. 8. 2010, 13:52, kterou vytvořil Karel.brinda (diskuse | příspěvky) (Založena nová stránka: \nothing{ \begin{document} } \xx{Úvod do teorie množin} \xxx{Teorie množin} \xxxx{Naivní teorie množin} \begin{enumerate}%XX \item Cantor, 19. století \item Vych...)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání

\nothing{ \begin{document} }

\xx{Úvod do teorie množin}

\xxx{Teorie množin}

\xxxx{Naivní teorie množin}

\begin{enumerate}%XX \item Cantor, 19. století \item Vychází z~představy, že každý objekt je množina. \end{enumerate}%XX

V~naivní teorii množin se brzy došlo k tzv. \defined[paradox]{paradoxům}. Ve skutečnosti to nejsou paradoxy, neboť paradox je \uv{neuvěřitelné, leč pravdivé tvrzení},

ale zde jde skutečně o spory v pravém slova smyslu

\example(Cantorův paradox) Nechť $\UU $ je množina všech množin

a $\PP\UU=\set x{x\subset\UU}$ její potenční množina (množina všech jejích podmnožin.

Potom neboť $\PP\UU\sse\UU$, je $\abs\UU\leq\abs{\PP\UU}$ (exaktní definice velkosti množiny je dále). Současně však $\forall M(\abs{\PP M}>\abs{M})$, tedy i $\abs\UU\leq\abs{\PP\UU}$, což je spor.

\example(Russelův paradox) 2 předpoklady:

\begin{enumerate} \item každý výrok $V(x)$ definuje množinu; \item o každém prvku lze rozhodnout, zda do množiny patří, či nikoli. \end{enumerate}

Potom definujme $x:=\set y{y\notin y}$. Dále $x\in x \Limpl x\notin x$ a zároveň $x\notin x \Limpl x\in x$, což je spor.

\example(sémantické paradoxy) Např. paradox Kréťana: \uv{Všichni Kréťani jsou lháři.} V~této podobě však nefunguje a je třeba jej poupravit: \uv{Teď lžu.}

\xxxx{Axiomatická teorie množin}

Teorie množin má 2 axiomatiky, které jsou však ekvivalentní:

\begin{enumerate} \item Zermelova-Fraenkelova axiomatika (označovaná \defined[ZF]{ZF}) \item G\H odelova-Bernaysova axiomatika; \end{enumerate}

My budeme pracovat s~Zermelovou-Fraenkelovou axiomatikou, jež vznikla v~roce 1908.

\axiom(A0)Axiomy rovnosti. \begin{enumerate}%XX \item $\AA x (x=x)$; \item $\AA x \AA y (x=y \Limpl y=x)$; \item $\AA x \AA y \AA z ((x=y \Land y=z) \Limpl x=z)$; \item $\AA x \AA y \Bigl(x=y \Limpl \bigl( (\AA u (u \in x \Lequiv u \in y) ) \Land \AA u (x \in u \Lequiv y \in u )\bigr)\Bigr)$. \end{enumerate}%XX

\axiom(A1)Axiom existence. $\EE x (x=x)$.

\axiom(A2)Axiom extenzionality. $\AA x \AA y \big(x=y \Lequiv \AA u (u \in x \Lequiv u \in y)\big)$.

\axiom(A3)Axiom dvojice. $\AA x \AA y \EE z \AA u \big(u \in z \Lequiv (u=x \Lor u=y)\big)$.

\define \defined{Uspořádaná dvojice} $\anglevector{x,y} :=\{\{x\},\{x,y\}\}$.\\ \defined{Uspořádaná $n$-tice} $\anglevector{x_1\cldc x_n}:=

\anglevector{x_1, \anglevector{x_2\cldc x_n}}$.

\axiom(A4)Axiom sjednocení (sumy). $\AA x \EE z \AA u \big(u\in z \Lequiv \EE y (u\in y \Land u\in x)\big)$.

\define Sumu systému $x$ značíme $z=\bigcup x$.

\axiom(A5)Schema axiomů vydělení. Nechť $F[u]$ je formule s volnou proměnnou $u$, jež neobsahuje $z$. Potom axiomem je $\AA x \EE z \AA u \big(u\in z \Lequiv (u \in x \Land F[u])\big)$.

\example \begin{enumerate} \item $F=\ulcorner u\in y\urcorner$ $\rightarrow$ \defined{průnik} $z=:x\cap y$. \item $F=\ulcorner u\notin y\urcorner$ $\rightarrow$ \defined{rozdíl} $z=:x\setminus y$. \item $F=\ulcorner u\neq u\urcorner$ $\rightarrow$ existence \defined{prázdné množiny} $z=:\emptyset$. \end{enumerate}

\axiom(A6)Axiom potence. $\AA x \EE z \AA u (u \in z \Lequiv u \sse x)$.

\define Potenční množinu množiny $x$ značíme $z=\PP x$.

\axiom(A7)Axiom nekonečna. $\EE z \big(\emptyset\in z \Land \AA x (x\in z \Limpl x\cup\{x\}\in z)\big)$.

\example $\PP{\emptyset}=\{\emptyset\}$. $\PP{\{\emptyset\}}=\{\emptyset, \{\emptyset\}\}$. $\PP{\{\emptyset, \{\emptyset\}\}}=\{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\emptyset, \{\emptyset\}\}\}$. Tato posloupnost množin umožňuje definovat přirozená čísla (s nulou) jako množiny.

\axiom(A8)Axiom fundovanosti. $\AA x \big(x\neq\emptyset \Limpl \EE z (z\in x \Land z\cap x=\emptyset)\big)$.

\consequence $\AA y (y\notin y)$.

\axiom(A9)Axiom výběru. Nezařazuje se do ZF axiomatiky, pokud jej zahrneme, používáme označení \defined{ZFC}

(\uv C označuje \uv{axiom of Choice}).

\define(třídy v Z-F axiomatice) \begin{enumerate}%XX \item Každá formule $F[u]$ definuje \defined{třídu} $Z=\set u{F[u]}$. \item Třídy značíme velkými písmeny. \item Každá monžina je třída $x=\set u{u\in x}$. \item Třída, která není množinou, se nazývá \defined{vlastní třída}. \item $\UU:=\set u{u=u}$ nazýváme \defined{universum} a je to vlastní třída. \end{enumerate}%XX

\remark(G\H odelova-Bernaysova axiomatika)

\begin{enumerate}%XX \item Prvotním pojmem je třída. \item Množina je taková třída, která je prvkem jiné třídy. \item Třída, který není množinou, je vlastní třída. \item Obě teorie jsou ekvivalentní. \end{enumerate}%XX

\xxxx{Kartézský součin}

\define Mějme 2 třídy $X$, $Y$. Třídu $$X\times Y:=\set{\anglevector{u,v}}{u\in X \Land v\in y} =\set z{\EE u \EE v (z=\anglevector{u,v} \Land u\in X \Land v\in Y)}$$ nazveme \defined{kartézský součin $X$ a $Y$}.

\lemma Jsou-li $x$ a $y$ množiny, pak i kartézský součin $x\times y$ je množina.

\proof $ u\in x \Land v\in y \implies u,v\in X\cup Y \implies \{u\}, \{u,v\}\in\PP{x\cup y} \implies z\in\PP{\PP{x\cup y}} \implies x\times y=\set{z\in\PP{\PP{x\cup y}}}{\EE u \EE v (z=\anglevector{u,v} \Land u\in x \Land v\in y)} $, tedy podle schematu axiomu vydělení je $x\times y$ množina. \QED

\xxx{Relace}

\define Nechť $M_1\cldc M_n$ jsou libovolné množiny Potom libovolné $\rho\sse M_1\times\cdots\times M_n$ nazveme \defined[relace]{$n$-ární relací

na $M_1\times\cdots\times M_n$} a číslo $n$ \defined[arita]{aritou} relace $\rho$.

\define \begin{enumerate}%XX \item Každé $R\sse M^2$ nazýváme \defined[relace!binární]{binární relace} na $M^2$. \item $R^\1:=\set{\anglevector{a,b}}{\anglevector{b,a}\in R}$ je \defined[relace!inverzní]{inverzní relace} k~$R$. \item $R\circ S=RS:=\set{\anglevector{a,c}}{\EE b\in M (\anglevector{a,b}\in R \Land \anglevector{b,c}\in S)}$

je \defined[součin!relací]{součin relací}.

\item $D_M=\set{\anglevector{a,a}}{a\in M}$ je \defined[diagonála]{diagonála}. \end{enumerate}%XX

\define \def\rEl#1#2#3#4{\anglevector{#1,#2}#3#4} \def\rR#1#2{\rEl {#1}{#2}\in R} Definujeme obecné vlastnosti, předpokládáme platnost výroků pro všechna $a,b,c\in M$. Relace je: \begin{enumerate}%XX \item \defined[relace!reflexivní]{reflexivní} $\equivs \rR aa \equivs D_M\sse R$; \item \defined[relace!transitivní]{transitivní} $\equivs \rR ab \Land \rR bc \Limpl \rR ac \equivs RR\sse R$; \item \defined[relace!symetrická]{symetrická} $\equivs \rR ab \Lequiv \rR ba \equivs R^\1=R$; \item \defined[relace!antisymetrická]{slabě antisymetrická}

$\equivs \rR ab \Land \rR ba \Limpl a=b \equivs R^\1\cap R\sse D_M$;

\item \defined[relace!antisymetrická]{silně antisymetrická}

$\equivs \rR ab \Limpl \rEl bc\notin R \equivs R^\1\cap R=\emptyset$;

\item \defined[relace!trichotonická]{trichotonická}

$\equivs \rEl ab\notin R \Limpl (\rR ba \Lor a=b) \equivs R^\1\cup R\cup D_M=M^2$;

\end{enumerate}%XX

\define Rozlišujeme následující typy relací: \begin{enumerate}%XX \item

\defined[ekvivalence (teorie množin)]{ekvivalence} (zn. $\equiv$) je reflexivní, transitivní a symetrická.
Ekvivalence rozděluje množinu na \defined{třídy ekvivalence}.
Množina $M_{/{\equiv}}$ všech tříd ekvivalence se nazývá \defined{faktorová množina}
nebo též \defined{faktor-množina} $M$ podle $\equiv$.

\item

\defined[uspořádání]{uspořádání} (zn. $\leq$) je relace reflexivní, transitivní a slabě antisymetrická.

\item

\defined[uspořádání!ostré]{ostré uspořádání} (zn. $<$) je relace transitivní a silně antisymetrická.
Platí: $$a\leq b \Lequiv a=b \Lor a<b,$$ $$a<b \Lequiv a\neq b \Land a\leq b.$$

\item

\defined[uspořádání!úplné]{úplné uspořádání} (\defined[uspořádání!lineární]{lineární uspořádání})
je relace trichotonická (každé dva prvky jsou \defined[prvek (teorie množin)!srovnatelnost]{srovnatelné}),
slabě antisymetrická, transitivní a reflexivní.

\end{enumerate}%XX


\xxx{Uspořádané množiny}

\xxxx{Uspořádané množiny. Řetězce}

\define \begin{enumerate} \item Množina $M$ s uspořádáním $\leq$ se nazývá \defined[množina!usporádaná]{uspořádaná množina} $(M, \leq)$. \item Přirozeným způsobem jsou na $M$ definovány operace $\geq$, $<$, $>$. \item Nechť $R\subseteq M$ je úplně uspořádaná, pak ji nazveme \defined[rzetězec@řetězec]{rětězcem}. \end{enumerate}

\define Nechť $(M, \leq)$ je uspořádaná množina, $a\in M$. Pak $a$ je: \begin{enumerate} \item \defined[prvek (teorie množin)!největší]{největší prvek}

(\defined[prvek (teorie množin)!poslední]{poslední prvek}) $\iff$ $(\forall x\in M)(x\leq a)$;

\item \defined[prvek (teorie množin)!nejmenší]{nejmenší prvek}

(\defined[prvek (teorie množin)!první]{první prvek}) $\iff$ $(\forall x\in M)(x\geq a)$;

\item \defined[prvek (teorie množin)!maximální]{maximální prvek} $\iff$ $(\forall x\in M)(x\geq a \Rightarrow x=a)$; \item \defined[prvek (teorie množin)!minimální]{minimální prvek} $\iff$ $(\forall x\in M)(x\leq a \Rightarrow x=a)$. \end{enumerate}

\lemma \begin{enumerate} \item Je-li $a\in M$ poslední, je maximální. \item Je-li $a\in M$ první, je minimální. \end{enumerate}

\example \begin{enumerate} \item $(\N, \;\mid\;)$. Relace \uv{dělí}: $a\mid b \Leftrightarrow (\exists c\in\Z)(b=ac)$.

První prvek je $1$, poslední není.

\item $(\Nz, \;\mid\;)$.

Prvním prvkem zůstává $1$, ale posledním je $0$, neboť $n\mid 0$ pro všechna celá čísla.

\item $(\N\sm\{1\}, \;\mid\;)$.

Nemá nejmenší, ale má minimální -- jsou to všechna prvočísla.

\end{enumerate}

\define Nechť $(M, \leq)$ je uspořádaná množina, $N\sse M$. Pak: \begin{enumerate} \item $z\in M$ je \defined[závora!horní]{horní závora} podmnožiny $N$ $\iff$ $(\forall x\in N)(x\leq z)$. \item $z\in M$ je \defined[závora!dolní]{dolní závora} podmnožiny $N$ $\iff$ $(\forall x\in N)(x\geq z)$. \item $N$ je \defined[množina!shora omezená]{shora omezená} $\iff$ existuje horní závora $N$. \item $N$ je \defined[množina!zdola omezená]{zdola omezená} $\iff$ existuje dolní závora $N$. \end{enumerate}

\define Nechť $(A, \leq)$ a $(B, \leq)$ jsou 2 uspořádané množiny, $f:A\rightarrow B$. Pak řekneme, že $f$ je \defined[zobrazení!izotonní]{izotonní} (\defined[zobrazení!izotonie]{izotonie}) $\iff$

$(\forall x,y\in A)\big(x\leq y \Limpl f(x)\leq f(y)\big)$.

\define Nechť $(A, \leq)$ a $(B, \leq)$ jsou 2 uspořádané množiny. Pak: \begin{enumerate} \item $f:a\rightarrow b$ je \defined[izomorfismus (teorie množin)]{izomorfizmus},

pokud je bijektivní a $f$ i $f^\1$ jsou izotonní, tj.
$$(\forall x,y\in A)\big(x\leq y \Lequiv f(x)\leq f(y)\big).$$

\item $A$ a $B$ jsou \defined[množiny!izomorfní]{izomorfní} (značíme $A\cong B$),

pokud existuje izomorfismus $A\rightarrow B$.

\end{enumerate}


\xxxx{Ekvivalence, subvalence množin}

\define \begin{enumerate} \item Řekneme, že $M$ a $N$ jsou \defined[množiny!ekvivalentní]{ekvivalentní}

(\defined[množiny!ekvipotenční]{ekvipotenční}) $\iff$
existuje bijekce $M$ na $N$. 
Značíme $M\approx N$.

\item Řekneme, že $M$ je \defined[množiny!subvalentní]{subvalentní} $N$ $\iff$

existuje injekce (prosté zobrazení) $M$ do $N$.
Značíme $M\pce N$.

\item Řekneme, že $M$ je \defined[množiny!subvalentní!ostře]{ostře subvalentní} $N$

$\iff$ $M\pce N \Land M\not\approx N$.
Značíme $M\pna N$ nebo $M\prec N$.

\end{enumerate}

\remark \begin{enumerate} \item $\approx$ je ekvivalence. \item Třídám ekvivalence $\UU_{/\approx}$ přiřazujeme

\defined[czíslo@číslo!kardinální]{kardinální číslo}.

\item $\pce$ není uspořádání, neboť $A\pce B \Land B\pce A \Limpl A\approx B$, nikoli $A=B$.

Lze tedy uspořádat kardinální čísla.

\end{enumerate}

\theorem (Cantor, Bernstein) Nechť $M$ a $N$ jsou libovolné množiny. Pak $$M\pce N \;\;\Land\;\; N\pce M \quad\Limpl\quad M\approx N.$$

\proof Víme, že existují injekce $\map fMN$ a $\map gMN$. Označme $N_1:=f(M)$, $M_1:=g(N)$, $N_1':=N\sm N_1$, $M_1':=M\sm M_1$. Pak $\maptype fM{bij}{N_1}$ a $\maptype gN{bij}{M_1}$.

Definujme posloupnost $x_n$ následovně: \begin{enumerate} \item $x_1\in M$; \item pokud $x_1\in M_1$, definuji $x_2:=g^\1 x_1$, jinak je $x_1$ poslední v~posloupnosti; \item pokud $x_2\in N_1$, definuji $x_3:=f^\1 x_2$, jinak je $x_2$ poslední v~posloupnosti; \item ... \end{enumerate}

Posloupnost je jednoduše rekurentní (každý prvek závisí pouze na nejbližším předchozím), tedy se množina $M$ direktně rozkládá na 3 podmnožiny: \begin{enumerate} \item $x\in M_M\sse M$, pokud poslední člen posloupnosti obsahující $x$ je v~$M$; \item $x\in M_N\sse M$, pokud poslední člen posloupnosti obsahující $x$ je v~$N$; \item $x\in M_\infty\sse M$, pokud je posloupnost obsahující $x$ nekonečná. \end{enumerate} Obdobně definujeme $N_M$, $N_N$ a $N_\infty$.

Potom nutně $N_1'\sse N_N$ a tedy platí, že $\map {f_{/M_M}}{M_M}{N_M}$ je prosté, protože $f$ je prosté, a na, protože $N_M\sse f(M)$. Obdobně $\maptype {g_{/N_N}}{N_N}{bij}{M_N}$ a konečně $\maptype{f_{/M_\infty}}{M_\infty}{bij}{N_\infty}$. Tedy $M_M\approx N_M$; $M_N\approx N_N$ a $M_\infty\approx N_\infty$,

z~čehož díky disjunktnosti rozkladů plyne $M\approx N$.

\QED

\theorem (Cantor) $$M\pna \PP M.$$

\proof \begin{description} \item[($M\pce \PP M$)] Položme $f(x):=\{x\}$. \item[($M\not\approx \PP M$)] Důkaz sporem.

Předpokládejme, že $M\approx \PP M$.
\\
Pak $(\EE g:M\stackrel{\mathrm{bij.}}{\longrightarrow} \PP M)$.
Označme $D:=\{x\in M\mid x\notin g(x)\}$, $d=g^\1(D)$.
Pak
\begin{itemize}
 \item $d\in D \Limpl d\notin g(d)=D$;
 \item $d\notin D \Limpl d\in g(d)=D$,
\end{itemize}
což je spor. (Tento typ důkazu se nazývá \defined[argument!Cantorův diagonální]{Cantorův diagonální argument}.)

\end{description} \QED

\xxxx{Úplně uspořádané množiny}

\define Nechť $(A, \leq)$, $(B, \leq)$ jsou 2 úplně uspořádané množiny a nechť $A$ je izomorfní s~$B$. Potom řekneme, že $A$ \defined[množiny!podobné]{je podobná} $B$

(relace \defined[relace!podobnost]{podobnost}; značíme $A\cong B$),

pokud existuje zobrazení $\map fAB$ nazývané \defined[zobrazení!podobnost]{podobnost}, které je bijektivní a izotonní.

\lemma Podobnost je ekvivalence na třídě všech úplně uspořádaných množin.

\proof \begin{description} \item[(reflexivita)] Podobností je identita. \item[(symetrie)] Podobností $\map gBA$ je inverzní zobrazení k~podobnosti $\map fAB$. \item[(transitivita)] existence podobností $\map fAB$ a $\map gBC$ zajišťuje existenci podobnosti $\map hAC$,

$h=g\circ f$.

\end{description} \QED

\define \defined[typ!ordinální]{Ordinální typ} je charakteristická vlastnost tříd ekvivalence

na všech úplně uspořádaných množinách podle $\cong$. Značí se $\ord A$.

\example \begin{enumerate} \item $\ord \emptyset=:0$. \item Nechť $K$ je úplně uspořádaná a $\abs K=k\in\N$.

Pak $\ord K=:k$. (Jednoznačnost lze ukázat matematickou indukcí, každá má první prvek)

\item $\ord\,(\N, \leq)=:\omega$. \end{enumerate}

\theorem Nechť $A$ a $B$ jsou podobné množiny. Pak má-li $A$ první prvek, má jej i $B$.

\proof Nechť $p$ je první v~$A$ a $\map fAB$ je podobnost. Ukážeme, že $f(p)$ je první v~$B$, tj. $(\AA y\in B)(\EE x\in A)(y=f(x))$. Ale $p$ je první v~$A$, tedy $x\geq p$ $\Limpl$ $y=f(x)\geq f(p)$. \QED

\example \begin{enumerate} \item $S=\set{2n}{n\in\N}\cong \N$, $\map fS\N$, $f(x)=x/2$. \item $\Nz\cong\N$, $f(x)=x+1$. \item $(\Z, \leq) \ncong (\N, \leq)$, neboť $\N$ má první a $\Z$ nikoliv, ale $\Z\approx\N$. \end{enumerate}

\define Řekneme, že úplné uspořádání $(M, \leq)$ je husté, právě když: $$(\AA x,y\in M, x<y)(\EE z\in M)(x<z<y).$$

\example \begin{enumerate} \item $(\Z, \leq)$ není husté uspořádání. \item $(\Q, \leq)$ je husté uspořádání. \end{enumerate}

\theorem Libovolná spočetná hustě uspořádaná množina, která nemá ani první, ani poslední prvek, je podobná $(\Q, \leq)$.

\define Nechť $A$ je úplně uspořádaná množina, $a\in A$. Pak \defined[usek@úsek]{úsekem} množiny $A$ určeným prvkem $a$ rozumíme $A_a:=\set{x\in A}{x<a}$.

\theorem \begin{enumerate} \item Je-li $a$ první v~$A$, pak $A_a=\emptyset$. \item Je-li $a$ poslední v~$A$, pak $A_a=A\sm\{a\}$. \item Ze 2 různých úseků množiny $A$ je jeden úsekem druhého. \item $a\leq b \iff A_a\sse A_b$. \item $(\set{A_a}{a\in A}, \sse)$ je úplně uspořádaná množina. \item $(\set{A_a}{a\in A}, \sse)\cong(A, \leq)$. \end{enumerate}

\xxxx{Dobré uspořádání}

\define Řekneme, že množina $M$ je \defined[množina!uspořádaná!dobře]{dobře uspořádaná},

má-li libovolná neprázdná podmnožina $M$ první prvek.

\theorem Dobré uspořádání je úplné.

\proof Mějme libovolné $a,b\in M$, $a\neq b$. Pak množina $\{a,b\}\sse M$ má první prvek, a tedy $a<b$ nebo $b<a$. \QED

\theorem \begin{enumerate} \item Neprázdná dobře uspořádaná množina má první prvek. \item Libovolná podmnožina dobře uspořádané množiny je dobře uspořádaná. \item Množina podobná dobře uspořádané množině je dobře uspořádaná.

(Dobře uspořádané množiny mají tedy vlastní třídy ekvivalence podle $\cong$
a jejich ordinální typ nazýváme \defined[czíslo@číslo!ordinální]{ordinální číslo}.)

\item Libovolný prvek dobře uspořádané množiny $M$, který není poslední (poslední však nemusí existovat),

má následníka, tj.

$$(\AA x\in M, \text{$x$ není poslední})(\EE y\in M)(\AA z\in M)(z\leq x \Lor z\geq y).$$ \end{enumerate}

\example Mějme $(\Z, \pce)$ s uspořádáním definovaným následovně: \begin{enumerate} \item $x,y\geq0$ \quad $x\prec y \Lequiv x<y$; \item $x,y<0$ \quad $x\prec y \Lequiv -x<-y$; \item $x<0\leq y$ \quad $y\prec x$. \end{enumerate} Pak $\ord\,(\Z, \pce)=\omega+\omega\neq\omega$.

\axiom(A9)Axiom výběru. Na libovolném $M\neq\emptyset$ existuje \defined[selektor]{selektor} (\defined[funkce!výběrová]{výběrová funkce})

$\map\phi{\PP M\sm \{\emptyset\}}{M}$ a platí:

$(\AA A\sse M, A\neq\emptyset)(\phi(A)\in A)$.

\define Zermelova-Frankelova axiomatika s~axiomem výběru se označuje \defined[ZFC]{ZFC}.

\theorem (Zermelo, v~ZFC) Na libovolné množině existuje binární relace, která je jejím dobrým uspořádáním.

\theorem (v~ZFC) Nechť $M$ je úplně uspořádaná množina. Pak následující výroky jsou ekvivalentní: \begin{enumerate} \item $M$ je dobře uspořádaná; \item na $M$ platí \defined[podmínka!indukční]{indukční podmínka}: $$\big(\AA N\sse M\big)\Big(\AA x\in M\big(\AA y\in M(y<x \Limpl y\in N)\Limpl x\in N\big)\Limpl N=M\Big);$$ \item na $M$ platí \defined[podmínka!konečnosti klesajících řětežců]{podmínka konečnosti klesajících řetězců}

(každý ostře klesající řetězec má konečnou délku).

\end{enumerate}

\proof Pro $M=\emptyset$ je důkaz triviální. Tedy nechť $M\neq\emptyset$. \begin{description}

\item[($1\Limpl2$)] Důkaz sporem. Nechť $(\EE N\sse M)(\AA x\in M(\AA y\in M(y<x \Limpl y\in N)\Limpl x\in N) \Land N\varsubsetneq M)$. $M$ je dobře uspořádaná, tedy má první prvek $p$ a podle předpokladu (neexistuje $y<p$) je $p\in N$,

tedy $N\neq\emptyset$.

Dále $M\sm N\neq\emptyset$ ($N$ je vlastní podmnožina), tedy existuje první prvek $q\in M\sm N$. Potom $(\AA y<q)(y\in N)$ $\Limpl$ $q\in N$, což je spor s $q\in M\sm N$.

\item[($2\Limpl3$)] Nechť $N$ je množina všech $z\in M$, pro které neexistuje nekonečný ostře klesající řetězec začínající v~$z$.


\item[($3\Limpl1$)] Dokážeme sporem. Nechť $M$ není dobře uspořádaná, tedy nechť existuje neprázdná $N\sse M$, která nemá první prvek. Pak pro libovolné $a\in N$ je úsek $N_a$ neprázdný (jinak by $a$ byl první prvek) a podle axiomu výběru $(\EE \map\phi{\PP N\sm\{\emptyset\}}N)(\phi(x)\in x)$. Definujme poslounost $(a_k)_1^\infty$ následovně: $a_1:=\phi(N)$; $a_{k+1}:=\phi(N_{a_k})$. Protoře $N_a$ je neprázdná pro všechna $a$ a $a_{k+1}<a_k$ (vlastnost úseku), je $(a_k)$ nekonečný ostře klesající řetětec, což je spor.

\end{description} \QED

\theorem Upořádaná množina $(\N, \leq)$ je uspořádaná dobře.

\theorem Nechť $A$ je dobře uspořádaná množina, $B\sse A$, $B\cong A$, $\map fAB$ je podobnost. Pak $(\AA x\in A)(f(x)\geq x)$.

\proof Označme $M:=\set{x\in A}{f(x)<x}$. Ukážeme sporem, že $M$ je prázdná.

Nechť $M\neq\emptyset$. Pak $M\sse A$, tedy má první prvek $p$. Platí $f(p)<p$, tedy z~izotonie $f$ je $f(f(p))<f(p)$ a tedy $f(p)$ je prvek $M$ menší než $p$, což je spor. \QED

\theorem Ze 2 dobře uspořádaných množin je vždy jedna podobná druhé nebo jejímu úseku.

\theorem (princip maximality, Zornovo lemma, Kuratowského lemma) Nechť $(M, \leq)$ je uspořádaná množina. Pak má-li libovolný řetězec z~$M$ horní závoru v~$M$,

pak libovolný prvek $a\in M$ je srovnatelný s~nějakým maximálním prvkem v~$M$.

(A tedy existuje alespoň jeden maximální prvek v $M$.)

\theorem (speciální případ Zornova lemmatu) Nechť $(\calS, \sse)$ je systém množin uspořádaný inkluzí. Pokud pro každý řetězec $R$ z~$\calS$ je $\bigcup R\in\calS$, pak $(\AA A\in\calS)(\EE B\in\calS, \text{$B$ maximální})(A\sse B)$.

\theorem Subvalence je trichotonická na třídě všech množin

(tj. libovolné 2 prvky jsou srovnatelné).

\proof Mějme 2 neprázdné množiny $A, B\in\UU$. Označme $M$ množinu všech prostých zobrazení z~$A$ do $B$, tedy $M=\set f{f:(A)\stackrel{\mathrm{inj.}}{\longrightarrow}B}$. Každé $f$ je speciální podmnožina $A\times B$, tedy $(M, \sse)$ je uspořádání. Nechť $R\sse M$ je řetězec. Označme $g:=\bigcup R$ Ukážeme, že $g\in M$. \QED

\begin{description} \item[($g$ je zobrazení)] Nechť $\anglevector{a, b_1}\!, \anglevector{a, b_2}\in g$. Pak $(\EE f_1, f_2\in R)\bigl(\anglevector{a, b_1}\in f_1, \anglevector{a, b_2}\in f_2\bigr)$. Bez újmy na obecnosti je $f_1\sse f_2$ a tedy $\anglevector{a, b_1}, \anglevector{a, b_2}\in f_2$,

tedy (neboť $f_2$ je zobrazení) $b_1=b_2$.

\item[($g$ je injekce)] Vezmeme $\anglevector{a_1, b}\!, \anglevector{a_2, b}\in g$. Stejným postupem dostaneme $a_1=a_2$. \end{description}

Tedy v~$M$ existuje maximální prvek $f$. Ukážeme, že je buďto $\mathdef f=A$ nebo $f(A)=B$. Nechť $(\EE a\in A)(a\notin\mathdef f)$ a $(\EE b\in B)(f^\1(\{b\})=\emptyset)$. Pak $f':=f\cup\anglevector{a, b}$ je bijekce z~$A$ do $B$ a $f\pce f'$, což je spor s~maximalitou $f$.

\theorem Libovolný netriviální vektorový prostor $V$ má (konečnou nebo Hammelovu) bázi.

\proof Označme $\calS$ systém všech lineárně nezávislých podmnožin $V$ uspořádaný inkluzí. Ukážeme, že pro libovolný řetězec $R=\set{A_i}{i=1\cldc n,\infty}\sse\calS$ je $A:=\bigcup R\in\calS$. Mějmě konečnou lineární kombinaci $\sum_{j=1}^k\alpha_ja_j$ prvků z~$A$. Pro každé $a_j$ existuje $A_{i_j}$ takové, že $a_j\in A_{i_j}$. Označme $i_m=\max_{j\in \widehat k} i_j$. Pak $(\AA j\in\widehat k)(a_j\in A_{i_m}\in\calS)$, tedy $\sum_{j=1}^k\alpha_ja_j=0 \Lequiv (\AA j)(\alpha_j=0)$,

což znamená, že $A\in\calS$.

Tedy podle Zornova lemmatu existuje maximální prvek $B\in\calS$.

Ukážeme, že $B\sublin=V$. Zjevně $B\sublin\sse V$, tedy zbývá ukázat, že generuje: Vezměme $v\in V\sm B$. Pak $B\cup\{v\}\varsupsetneq B$ je lineárně závislá (jinak by $B$ nebyla maximální v~$\calS$). Tedy existuje konečná lineární kombinace z~$B\cup\{v\}$ a nutně je koeficient u $v$ nenulový

(jinak by kombinace byla nulová a z~$B$, ale $B$ je lineárně nezávislá).

Tedy $v\in B\sublin$. \QED

\theorem (Hausdorffův princip, v~ZFC) V~libovolné uspořádané množině je každý řetězec částí nějakého maximálního řetězce (ve smyslu inkluze).

\theorem V~ZF axiomatice jsou následující výroky ekvivalentní: \begin{enumerate} \item axiom výběru; \item princip dobrého uspořádání (Zermelova věta); \item princip maximality (Zornovo lemma); \item Hausdorffův princip. \end{enumerate}

\xxxx{Uspořádání kartézského součinu}

\define Nechť $(A, \leq)$, $(B, \leq)$, $A\times B=\set{\anglevector{a,b}}{a\in A, b\in B}$.\\ Pak definuji \defined[uspořádání!lexikografické]{lexikografické uspořádání}: $$\anglecouple ab\leq\anglecouple cd\iff(a<c \;\lor\; (a=c\land b\leq d)).$$

\lemma Jsou-li $A$, $B$ dobře uspořádané, pak i lexikografické uspořádání na $A\times B$ je dobré.

\proof Nechť $\emptyset\neq M\sse A\times B$. Položme $M_A:=\set{a\in A}{(\EE b\in B)(\anglecouple ab\in M)}$. $\emptyset\neq M_A\sse A$, tedy má první prvek $p$. Položme $M_B:=\set{b\in B}{\anglecouple pb\in M}$. $\emptyset\neq M_B\sse B$, tedy má první prvek $q$.

Ukážeme, že $(\AA\anglecouple ab\in M)(\anglecouple pq\leq\anglecouple ab)$. Z~definice $M_A$ je $p\leq a$ a pokud $p=a$, je z~definice $M_B$ $q\leq b$. \QED

\define Nechť $A$, $B$ jsou dobře uspořádané množiny, $\alpha=\ord A$, $\beta=\ord B$. Definujeme \defined[součin!ordinálních čísel]{součin ordinálních čísel}: $$\alpha\cdot\beta:=\ord(B\times A).$$

\example \begin{enumerate} \item $\ord\N=\omega$. \item $\omega\cdot\omega=\ord(\N\times\N)=:\omega^2$. \item $\omega\cdot2=\ord(\{a,b;a<b\}\times\N)=\omega+\omega\neq\omega$. \item $2\cdot\omega=\ord(\N\times\{a,b\})=\ord\N=\omega$. Tedy $\omega\cdot2\neq2\cdot\omega$. \end{enumerate}

\define Nechť $\calS=\set{A_i}{i\in I}$ je systém po dvou disjunktních množin

(disjunktnost lze zaručit položenín $A'_i:=\{i\}\times A_i$.

Nechť $(I, \leq_I)$ je uspořádání, stejně tak pro všechna $i\in I$ je $(A_i, \leq_i)$ uspořádání. Pak definujeme \defined[sjednocení!uspořadané uspořádaných množin]{uspořádané sjednocení uspořádaných množin}

na množině $A=\bigcup\calS$.

Nechť $a, b\in A$, $a\in A_i$, $b\in B_j$. Pak $$a\leq b \Lequiv (i<_Ij \Lor (i=j \Land a\leq_ib)).$$

\lemma Usporádání $\leq$ na $A$ je úplné/dobré, pokud $\leq_I$ i všechna $\leq_i$ jsou úplná/dobrá.

\proof Obdobně jako pro kartézský součin \QED

\define Nechť $A_1$, $A_2$ jsou dobře uspořádané množiny, $\alpha=\ord A_1$, $\beta=\ord A_2$. Definujeme \defined[součet!ordinálních čísel]{součet ordinálních čísel}: $$\alpha+\beta:=\ord\bigcup\{A_1, A_2\}.$$

\example \begin{enumerate} \item $1+\omega=\ord\bigcup\{A_1=\{a\}; A_2=\N\}=\omega.$ \item $\omega+1=\ord\bigcup\{A_1=\N; A_2=\{a\}\}\neq\omega.$ \end{enumerate}