01ALG:Kapitola3: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
Řádka 97: | Řádka 97: | ||
\proof | \proof | ||
− | Víme, že existují injekce $\map fMN$ a $\map | + | Víme, že existují injekce $\map fMN$ a $\map gNM$. |
Označme $N_1:=f(M)$, $M_1:=g(N)$, $N_1':=N\sm N_1$, $M_1':=M\sm M_1$. | 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}$. | Pak $\maptype fM{bij}{N_1}$ a $\maptype gN{bij}{M_1}$. |
Aktuální verze z 24. 1. 2012, 13:18
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01ALG
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01ALG | Karel.brinda | 24. 8. 2010 | 14:49 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 13:48 | ||
Header | editovat | Hlavičkový soubor | Karel.brinda | 24. 10. 2010 | 19:54 | header.tex | |
Kapitola0 | editovat | Úvodní poznámky | Karel.brinda | 26. 8. 2010 | 15:03 | alg_note.tex | |
Kapitola1 | editovat | Teorie množín | Snilard | 6. 1. 2011 | 00:37 | alg_set.tex | |
Kapitola2 | editovat | Relace | Karel.brinda | 25. 1. 2011 | 22:52 | alg_rel.tex | |
Kapitola3 | editovat | Uspořádané množiny | Sedlam18 | 24. 1. 2012 | 13:18 | alg_set2.tex | |
Kapitola4 | editovat | Algebra | Snilard | 6. 1. 2011 | 00:59 | alg_alg.tex | |
Kapitola5 | editovat | Teorie grup | Pitrazby | 17. 2. 2012 | 02:51 | alg_group.tex | |
Kapitola6 | editovat | Okruhy | Pitrazby | 17. 2. 2012 | 03:00 | alg_ring.tex | |
Kapitola7 | editovat | Moduly a lineární algebry | Kosarvac | 11. 11. 2011 | 15:50 | alg_module.tex | |
Kapitola8 | editovat | Teorie svazů | Pitrazby | 17. 2. 2012 | 14:19 | alg_lattice.tex | |
Kapitola9 | editovat | Polynomy nad komutativními tělesy | Pitrazby | 17. 2. 2012 | 14:21 | alg_polynoms.tex | |
Kapitola10 | editovat | Konečná tělesa | Pitrazby | 17. 2. 2012 | 14:24 | alg_finite.tex |
Zdrojový kód
%\wikiskriptum{01ALG} \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]{řetě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$ ($\pce$ je reflexivní, tranzitivní, ale není slabě antisymetrická). 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 gNM$. 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 $\maptype {f_{/M_M}}{M_M}{bij}{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. 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 \lemma Libovolné 2 úplně uspořádané konečné množiny o stejném počtu prvku jsou podobné. \proof Ukážeme indukcí podle počtu prvků: \begin{enumerate} \item $n = 1, n = 2$: zřejmé \item $n \geq 2: |A| = |B| = n$.\\ Definujeme $p,q$ jako nejmenší prvky v $A$ resp. $B$, $A' = A - \{p\}, B' = B - \{q\}$. Pro $A'$ a $B'$ máme z indukčního předokladu podobnost $f': A' \cong_{f'} B'$\\ Pro $A, B$ definujeme podobnost:\\ $f(x) = \left\{ \begin{array}{l l} f'(x) & \quad \text{pro } x \in A'\\ q & \quad \text{pro } x=p\\ \end{array} \right.$ \end{enumerate} \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 (Cantor) 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 $A$ úplně uspořádaná: \begin{enumerate} \item Je-li $a$ první v~$A \iff 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$ ($\ord \N = \ord \N_0 = \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 posloupnost $(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ězec, což je spor. \end{description} \QED \example $\emptyset$ je dobře uspořádaná, $\N$ je dobře uspořádaná, $\ord \N = \omega = \ord \N_0$.\\ $\Z$ není při přirozeném uspořádání dobře uspořádaná, $\Q$ také není. \lemma Buďte $A, B$ podobné dobře uspořádané množiny. Pak existuje pouze jedna podobnost $A$ na $B$. \proof Nechť $\map fAB,\ \map gAB,\ f \neq g,\ M:=\set{x\in A}{f(x) \neq g(x)} \neq \emptyset,\ M \subseteq A,\ p$~první prvek v $M$. $b_1 = f(p),\ b_2 = g(p)$, nechť $b_1 < b2$. Nechť $a \in A$ takové, že $g(a) = b_1,\ g(a) < b_2 = g(p)$. Z izotonie máme $f(a) < f(p) = b_1 = g(a)$. Z toho dostáváme $a \in M$, což je spor. \QED \theorem Uspořá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. \consequence Dobře uspořádaná množina není podobná žádné podmnožině svého úseku ani žádnému úseku své podmnožiny, tedy ani žádnému své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 Relace 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$. \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$. \QED \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 A_j$. Pak $$a\leq b \Lequiv (i<_Ij \Lor (i=j \Land a\leq_ib)).$$ \lemma Uspořá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}