Zde předložený text o Teorii množin je v procesu tvorby a bude během letního semestru průběžně inovován.
Obsah.Dvě množiny jsou si rovny, pokud obsahují stejné prvky. Tento axiom dává dvě možnosti, jak dokázat rovnost dvou množin \(A = B\):
Nechť \(\varphi(x)\) je formule. Potom pro každou množinu \(A\) existuje množina \(M\), která obsahuje ty elementy \(x\in A\), pro které platí \(\varphi(x).\) \[ M = \{x\in A: \varphi(x)\} \iff \forall z(z\in M\iff (z\in A\wedge \varphi(z))). \] Potom platí: \begin{equation} \forall A\forall B(A\cap B = \{x\in A:x\in B\}). \end{equation} Dále definujeme: \begin{equation} A\setminus B = \{x\in A: x\notin B\}. \end{equation}
Je-li \(\varphi(x)\) formule teorie množin, potom formuli \[ \{x:\varphi(x)\} \] nazveme třídou všech množin x pro něž platí \(\varphi(x)\). Je-li \(\varphi(x)\) formule teorie množin taková, že neexistuje množina \(A\) pro něž platí \[ \forall x(\varphi(x) \implies x\in A), \] potom říkáme, že třída \(\{x:\varphi(x)\}\) je vlastní třídou.
Věta.
Neexistuje množina, která obsahuje všechny množiny jako svoje prvky. Jinými slovy:
\[
\mathbb V := \{x: x=x\}
\]
je vlastní třídou.
Důkaz. Důkaz provedeme sporem. Předpokládejme, že existuje množina \(A\) obsahující jako svoje prvky
všechny množiny, tedy platí tvrzení: \(\forall x(x\in A\).
Axiom vydělení implikuje existenci množiny
\[
B = \{x\in A: x\notin x\}.
\]
Z definice množiny \(B\) snadno dokážeme ekvivalenci:
\[
B\in B \iff B\notin B,
\]
což je spor. \(\Box\)
Definice průniku systému množin. Nechť \(\mathcal F\) je neprázdná množina. Potom definujme třídu \(\bigcap\mathcal F\) formulí: \[ \bigcap\mathcal = \{x: \forall A(A\in\mathcal F\implies x\in A)\}. \] Vzledem k předpokladu \(\mathcal F\neq\emptyset\), existuje množina \(B\in\mathcal F\) a potom platí \(\forall x(x\in\mathcal F\implies x\in B.)\) Tedy třída \(\bigcap\mathcal F\) je množinou.
Pro každé dvě množiny \(u\) a \(v\) existuje množina obsahující právě
\(u\) a \(v\).
Nechť \(S\) označuje množinu obsahující právě dva prvky \(u\) a \(v\),
pak definujeme:
\[
\{u,v\} := S.
\]
Dále, pokud navíc platí \(u=v\), potom definujeme označení:
\[
\{u\} := \{u, u\}.
\]
Tedy platí tvrzení: \(\forall u(\textrm{sing}(\{u\})).\)
Věta
\(\{\emptyset\} \neq \{\{\emptyset\}\}.\)
Důkaz (Sporem.)
Předpokládejme, že \(\{\emptyset\} = \{\{\emptyset\}\}\).
Z axiomu extenzionality plyne, že
\(\emptyset = \{\emptyset\}.\) Dále zřejmě \(\emptyset\in\{\emptyset\}\)
a pak
\(\emptyset\in\emptyset\) což je spor. \(\Box\)
Opakovaným užitím axiomu neuspořádané dvojice lze tvořit
nové navzájem různé množiny:
\[
\{\emptyset\}, \{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\ldots
\]
Definice uspořádané dvojice.
Jsou-li \(a,b\) množiny, pak definujeme tzv. uspořádanou
dvojici množin \(a,b\) jako množinu:
\[
(a,b) := \{\{a\}, \{a,b\}\}.
\]
Věta. \(\forall a\forall b\forall c\forall d:\)
\[
(a,b) = (c,d) \iff a = c \wedge b = d.
\]
Důkaz. Domací cvičení. \(\Box\)
Pro každou množinu \(\mathcal F\) existuje množina \(U\), obsahující právě ty prvky, které náleží alespoň do jedné z množin náležících do množiny \(\mathcal F.\) Nyní definujeme označení: \[ \bigcup \mathcal F := U. \] Pak tedy \[ x\in\bigcup\mathcal F \iff \exists A(A\in F\wedge x\in A). \] Jinak lze tedy definovat \(\bigcup\mathcal F\) jako třídu \(\{x: x\in A\textrm{ pro nějaké } A\in\mathcal F\}\) Jsou-li \(A,B\) dvě množiny, pak definujeme sjednocení množin \(A,B\) jako množinu: \[ A\cup B := \bigcup\{A,B\}. \]
Pro každou množinu \(A\) existuje množina \(P\) obsahující jako
elementy všechny množiny, které jsou podmnožinami množiny \(A.\)
Definice potenční množiny. Je-li \(A\) množina, potom
množinu \(P\) jejíž existence plyne z Axiomu potenční množiny nazveme
potenční množinou množiny \(A\) a označíme ji symbolem \(P(A).\)
S využitím axiomu potenční množiny lze definovat další pojmy.
Součinem množiny \(X\) a \(Y\) se rozumí množina všech uspořádaných dvojic \(\left( x,y\right)\) takových, že \(x\in X\) a \(y\in Y\): \begin{eqnarray} X\times Y &=&\left\{ \left( x,y\right) :x\in X\wedge y\in Y\right\} \label{eq 1.6} \ &=&\left\{ u:\exists x~\exists y~\left( u=\left( x,y\right) \wedge x\in X\wedge y\in Y\right) \right\} \text{.} \notag \end{eqnarray} \(X\times Y\) je množinou neboť je \begin{equation*} X\times Y\subset P\left( P\left( X\cup Y\right) \right) \text{.} \end{equation*} Podobně součin tří množin $X,Y,Z$ je definován: \begin{equation*} X\times Y\times Z=\left( X\times Y\right) \times Z \end{equation*} a obecně je \begin{equation*} X_{1}\times \ldots \times X_{n+1}=\left( X_{1}\times \ldots \times X_{n}\right) \times X_{n+1}\text{.} \end{equation*} Tedy \begin{equation*} X_{1}\times \ldots \times X_{n}=\left\{ \left( x_{1},\ldots ,x_{n}\right) :x_{1}\in X_{1}\wedge \ldots \wedge x_{n}\in X_{n}\right\} \text{.} \end{equation*} Také definujeme \begin{equation*} X^{n}=\underset{\text{n krát}}{\underbrace{X\times \ldots \times X}}% \text{.} \end{equation*}
Definice. \(n\)-nární relací rozumíme jakoukoli množinu \(R\) jejímiž prvky jsou uspořádané \(n\)-tice. \(R\) je relací na množině \(X\), pokud \(R\subset X^{n}\). Dále formuli \(\left( x_{1},\ldots ,x_{n}\right) \in R\) zapisujeme spíše takto: \(R\left( x_{1},\ldots ,x_{n}\right)\). Je-li \(R\) binární relací, pak také píšeme \(xRy\) místo \(\left( x,y\right) \in R.\) Je-li \(R\) binární relací, pak definičním oborem relace míníme množinu \begin{equation*} dom\left( R\right) =\left\{ u:\exists v~\left( u,v\right) \in R\right\} \text{.} \end{equation*} Oborem hodnot relace \(R\) rozumíme množinu \begin{equation*} ran~\left( R\right) =\left\{ v:\exists u~\left( u,v\right) \in R\right\} \text{.} \end{equation*} Třídy \(dom~R\) i \(ran~R\) jsou množinami, neboť je \begin{equation*} dom\left( R\right) \subset \cup \cup R,\ ran\left( R\right) \subset \cup \cup R\text{.} \end{equation*} Pak polem relace \(R\) je množina \begin{equation*} field~\left( R\right) =dom\left( R\right) \cup ran\left( R\right) \text{.} \end{equation*} Obecně třída \(R\) je \(n\)-nární relací, jestliže všechny prvky jsou uspořádané \(n\)-tice, tj. \begin{equation*} R\subset V^{n}=\text{třída všech uspořádaných }n \text{-tic.} \end{equation*}
Binární relace \(f\) je pak funkcí, jestliže \begin{equation*} \forall x\forall y\forall z~\left( \left( x,y\right) \in f\wedge \left( x,z\right) \in f\implies y=z\right) \text{.} \end{equation*} To že \(\left( x,y\right) \in f\) píšeme obvykle takto: \begin{equation*} y=f\left( x\right) \text{.} \end{equation*} Řekneme, že funkce \(f\) je funkcí na \(X\), je-li \(X=dom~f\). Je-li \(dom~\left( f\right) =X^{n}\) říkáme, že \(f\) je funkcí \(n\)-proměných. \(f\) je funkcí množiny \(X\) do množiny \(Y\), \begin{equation*} f:X\rightarrow Y, \end{equation*} jestliže \(dom\left( f\right) =X\) a \(ran~\left( f\right) \subset Y\). Množina všech funkcí \(X\) do \(Y\) se bude značit symbolem \(Y^{X}\). \(Y^{X}\) je množina neboť \begin{equation*} Y^{X}\subset P\left( X\times Y\right) \text{.} \end{equation*} Jestliže \(ran\left( f\right) = Y\) říkáme, že \(f\) je funkcí na množinu \(Y\) (surjektivní). Funkce \(f\) se nazývá prostou funkcí (vzájemně jednoznačná funkce, 1-1 funkce), pokud \begin{equation*} \forall x\forall y~\left( f\left( x\right) = f\left( y\right) \implies x=y\right) \text{.} \end{equation*} \(n\)-nární operací na množině \(X\) se rozumí jakákoli funkce \(f:X^{n}\rightarrow X\). Restrikce funkce \(f\) na množinu \(X\) je definována jako funkce \begin{equation*} f\upharpoonright X=\left\{ \left( x,y\right) \in f:x\in X\right\} \text{.} \end{equation*} Obvykle \(X\subset dom~f.\) Funkce \(g\) se nazývá rozšířením funkce \(f\), jestliže \(g\supset f\), tj. \[ dom~\left( f\right) \subset dom~\left( g\right) \] a \[ g\left( x\right) =f\left( x\right) \text{ pro všechna }x\in dom~\left( f\right) \text{.} \] Jsou-li \(f\) a \(g\) funkce takové, že \(ran\left( f\right) \subset dom\left( g\right)\), pak kompozicí (složením) funkcí \(f\) a \(g\) rozumíme funkci \(g\circ f\) takovou, že \[ dom(g\circ f)=dom~\left( f\right) \] a \[ \forall x~\left( x\in dom~\left( f\right) \rightarrow \left( g\circ f\right) \left( x\right) =g\left( f\left( x\right) \right) \right) \text{.} \] Obrazem množiny \(X\) ve funkci \(f\) je množina \(f[X]\) nebo \(f\left( X\right) :\) \begin{equation*} f[X]=f\left( X\right) =\left\{ y:\left( \exists x\in X\right) ~y=f\left( x\right) \right\} \text{.} \end{equation*} Úplný vzor množiny ve funkci \(f\) nebo inverzní obraz množiny ve funkci \(f\) je množina: \begin{equation*} f_{-1}\left( X\right) =\{x:f\left( x\right) \in X\}. \end{equation*} Je-li funkce \(f\) prostá, pak funkce \begin{equation*} f^{-1}=\left\{ \left( y,x\right) :y=f\left( x\right) \right\} \end{equation*} se nazývá inverzní funkcí k funkci \(f\). obecně třída \(F\) je funkcí, je-li relací takovou, že z podmínek \(\left( x,y\right) \in F\), \(\left( x,z\right) \in F\) vyplývá \(y=z\). Podobně, je-li \(F\) funkce a \(C\) je třída, pak Obecně definujeme třídu \(F\left( C\right)\), která je obrazem třídy \(C\). Dále pojmy funkce, zobrazení, korespondence jsou považovány za synonyma. Podobně pojmy množina, soubor, kolekce jsou také považovány za synonyma.
Relace ekvivalence na množině \(X\) je binární relace (na množině \(X\)) \(\ \equiv \), která je reflexivní, symetrická a tranzitivní: pro všechna \(x,y,z\in X\) platí, \begin{eqnarray*} x &\equiv &x, \ x &\equiv &y\implies y\equiv x, \ \text{jestliže }x &\equiv &y\text{ a }y\equiv z\text{, pak}\ x\equiv z% \text{.} \end{eqnarray*}
Řekneme, že množina \(S\) je induktivní, jestliže
\begin{equation*}
\varnothing \in S\wedge \left( \forall x\in S\right) ~x\cup \left\{
x\right\} \in S\text{.}
\end{equation*}
Axiom nekonečna pak říká:
"Existuje induktivní množina."
Schéma axiomů nahrazení. Předpokládejme, že \(\psi(x,y)\) je formule,\(A\) je množina a pro každé \(x\in A\) existuje jediné \(y\) takové, že platí \(\psi(x,y)\). Potom existuje množina \(B\) obsahující právě ty elementy \(y\), pro které platí \(\psi(x,y)\) pro jisté \(x\in A.\)