Zdrojový kód
%\wikiskriptum{01ALG}
\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{\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{\PP\UU}\leq\abs\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 y\in x)\big)$.
\define
Sumu systému $x$ značíme $z=\bigcup x$.
\axiom(A5)Schéma axiomů vydělení.
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)$.
\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]}$, u je množina.
\item Třídy značíme velkými písmeny.
\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 $\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 schématu axiomu vydělení je $x\times y$ množina.
\QED
