Verze z 8. 1. 2011, 19:18

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]{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$ ($\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 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 $\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 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
 
\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 = \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}