|
|
(Není zobrazeno 6 mezilehlých verzí od jednoho dalšího uživatele.) |
Řádka 14: |
Řádka 14: |
| V~naivní teorii množin se brzy došlo k tzv. \defined[paradox]{paradoxům}. | | 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í}, | | 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 | + | ale zde jde skutečně o spory v pravém slova smyslu. |
| | | |
| \example(Cantorův paradox) | | \example(Cantorův paradox) |
| Nechť $\UU $ je množina všech množin | | 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. | + | 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). | + | Potom neboť $\PP\UU\sse\UU$, je $\abs{\PP\UU}\leq\abs\UU$ (exaktní definice velikosti 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. | + | Současně však $\forall M(\abs{\PP M}>\abs{M})$, tedy i $\abs{\PP\UU}\leq\abs\UU$, což je spor. |
| | | |
| \example(Russelův paradox) | | \example(Russelův paradox) |
Řádka 42: |
Řádka 42: |
| | | |
| \begin{enumerate} | | \begin{enumerate} |
− | \item Zermelova-Fraenkelova axiomatika (označovaná \defined[ZF]{ZF}) | + | \item Zermelova-Fraenkelova axiomatika (označovaná \defined[ZF]{ZF}); |
− | \item G\H odelova-Bernaysova axiomatika; | + | \item G\H odelova-Bernaysova axiomatika. |
| \end{enumerate} | | \end{enumerate} |
| | | |
Řádka 71: |
Řádka 71: |
| | | |
| \axiom(A4)Axiom sjednocení (sumy). | | \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)$. | + | $\AA x \EE z \AA u \big(u\in z \Lequiv \EE y (u\in y \Land y\in x)\big)$. |
| | | |
| \define | | \define |
| Sumu systému $x$ značíme $z=\bigcup x$. | | Sumu systému $x$ značíme $z=\bigcup x$. |
| | | |
− | \axiom(A5)Schema axiomů vydělení. | + | \axiom(A5)Schéma axiomů vydělení. |
− | Nechť $F[u]$ je formule s volnou proměnnou $u$, jež neobsahuje $z$. | + | Nechť $F[u]$ je formule s volnou proměnnou $u$, jež neobsahuje volnou proměnnou $z$. |
| Potom axiomem je $\AA x \EE z \AA u \big(u\in z \Lequiv (u \in x \Land F[u])\big)$. | | Potom axiomem je $\AA x \EE z \AA u \big(u\in z \Lequiv (u \in x \Land F[u])\big)$. |
| | | |
Řádka 114: |
Řádka 114: |
| \define(třídy v Z-F axiomatice) | | \define(třídy v Z-F axiomatice) |
| \begin{enumerate}%XX | | \begin{enumerate}%XX |
− | \item Každá formule $F[u]$ definuje \defined{třídu} $Z=\set u{F[u]}$. | + | \item Každá formule $F[u]$ definuje \defined{třídu} $Z=\set u{F[u]}$, u je množina. |
| \item Třídy značíme velkými písmeny. | | \item Třídy značíme velkými písmeny. |
− | \item Každá monžina je třída $x=\set u{u\in x}$. | + | \item Každá množ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 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. | | \item $\UU:=\set u{u=u}$ nazýváme \defined{universum} a je to vlastní třída. |
Řádka 152: |
Řádka 152: |
| \implies | | \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)} | | 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. | + | $, tedy podle schématu axiomu vydělení je $x\times y$ množina. |
| \QED | | \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}
| |