{{Stub}}
{{predmet|Teorie množin|Petr Simon|AIL063}}
*[[AIL063 Termíny skúšok|Termíny skúšok]]
== Cantorova (nefunkční) teorie množin ==
Cantor: ''Množinou rozumíme každé shrnutí určitých a navzájem různých předmětů ''m'' našeho nazírání nebo myšlení (které nazýváme prvky) do jediného celku ''M''.''
=== Paradoxy ===
==== Russelův paradox ====
Buď <math>M</math> množina všech množin <math>K</math> takových, že <math>K \notin K</math>.
Ptáme se, jestli platí <math>M \in M</math>.
Z <math>M \in M</math> plyne <math>M \notin M</math>, naopak z <math>M \notin M</math> plyne <math>M\in M</math>.
Russelovu paradoxu se vždy vyhneme, pokud si na začátku vezmeme nějakou obrovskou množinu M, se kterou už pak dál nepracujeme, ale pracujeme s jejími prvky, částmi.
==== Richardův paradox ====
(1) ''Buď n nejmenší číslo (přirozené), které nejde definovat méně než třiceti slovy českého jazyka.''
Řekněme, že čeština má 10 000 slov. Některé ze všech možných kombinací nejvýše 30 slov jsou jistě definicemi čísel. Těchto definic je konečné množství, přirozených čísel je nekonečně, takže takové číslo určitě existuje. Číslo, o kterém věta (1) mluví ji ale nesplňuje.
Podezřelé z hlediska tohoto paradoxu jsou věty, které mluví samy o sobě.
== Teorie množin (Zermelo, Fraenkel) ==
=== Jazyk teorie množin ===
=== Axiomy ===
==== (0) Axiom existence množiny ====
<math>(\exists x)(x=x)</math>
==== (1) Axiom extenzionality====
<math>
((\forall x)(\forall y)((\forall u)((u \in x \leftrightarrow u \in y))
\rightarrow
(x=y))
</math>
==== (2) Schéma axiomů vydělení ====
Je-li
<math>\phi(x)</math>
formule jazyka teorie množin, která neobsahuje volně proměnnou
<math>z</math>,
pak následující formule:
<math>
(\forall a)(\exists z)(\forall x)((x\in z)
\leftrightarrow
((x \in a) \and \phi (x)))
</math>
je axiom teorie množin.
==== (3) Axiom dvojice ====
<math>
(\forall a)(\forall b)(\exists z)(\forall x)((x \in z)
\leftrightarrow
((x=a)\or(x=b)))
</math>
* Libovolné dvě množiny určují dvouprvkovou množinu
==== (4) Axiom sumy ====
<math>
(\forall a)(\exists z)(\forall x)((x \in z)
\leftrightarrow
(\exists t)((t \in a) \and (x \in t)))
</math>
* Ke každé množině existuje množina všech prvků jejich prvků
==== (5) Axiom potence ====
<math>
(\forall a)(\exists z)(\forall x)
((x \in z) \leftrightarrow (x \subseteq a))
</math>
* Pro každou množinu existuje množina všech jejich podmnožin.
==== (6) Schema axiomů nahrazení ====
Je-li <math>\psi(u,v)</math> fromule teorie množin, která neobsahuje volné proměnné <math>w,z</math>, pak formule:
<math>
(\forall u)(\forall v)(\forall w)
((\psi(u,v) \and \psi(u,w)) \rightarrow (v=w)) \rightarrow
(\forall a)(\exists z)(\forall v)
((v \in z) \leftrightarrow (\exists u)((u \in a) \and \psi(u,v)))
</math>
je axiom teorie množin.
* Obrazem množiny při definovaném zobrazení je množina.
==== (7) Axiom nekonečna ====
<math>
(\exists z)((0 \in z)\and(\forall x)((x \in z) \rightarrow (x \cup \{x\} \in z)))
</math>
* Existuje nekonečná množina
==== (8) Axiom fundovanosti ====
<math>
(\forall a)((a\neq0) \rightarrow (\exists x)((x \in a) \and (x \cap a=0)))
</math>
=== Dodatky k axiomům ===
==== (1) extenzionalita ====
Platí i opačná implikace, něž je v axiomu extenzionality, tj.:
<math>
(\forall x)(\forall y)(\forall t)(t \in x \leftrightarrow t \in y)
\leftrightarrow x = y
</math>
* Množina je kompletně určena svými prvky, nic jiného neuvažujeme. Množiny se stejnými prvky jsou si rovné. (V logice je rovnost tehdy, když "platí" (jsou splnitelné) u obou "členů" stejné formule)
===== Definice: podmnožiny, inkluze =====
Říkáme, že množina <math>x</math> je podmnožinou množiny <math>y</math>, zapisujeme
<math>x\subseteq y</math>, jestliže platí:
<math>
(\forall t)(t \in x \rightarrow t \in y)
</math>
Říkáme, že množina <math>x</math> je vlastní podmnožinou množiny <math>y</math>, zapisujeme
<math>x\subset y</math>, jestliže:
<math>
(x \subseteq y) \and (x \neq y)
</math>
====== Lemma ======
<math>
(\forall x)(x \subseteq x) \and \neg (x \subset y)
</math>
<math>
(\forall x,y,z)((x\subseteq y) \and (y \subseteq z) \rightarrow (x \subseteq z))
</math>
<math>
(\forall x,y,z)((x\subset y) \and (y \subseteq z) \rightarrow (x \subseteq z))
</math>
<math>
(\forall x,y,z)((x\subseteq y) \and (y \subset z) \rightarrow (x \subseteq z))
</math>
<math>
(\forall x,y)((x\subseteq y) \and (y \subseteq x) \rightarrow (x = y))
</math>
==== (2) Schéma axiomů vydělení ====
* Pro každé <math>\phi</math> je to jeden axiom
* Proč nemůže být <math>z</math> volná proměnná ve <math>\phi</math>?
Jinak bychom mohli položit <math>\phi(x): x \notin z</math>, z čehož:
<math>
(\forall a)(\exists z)(\forall x)
(x \in z \leftrightarrow ((x \in a)\and (x\notin z)))
</math>
což je spor.
* Máme-li množinu <math>a</math> a formuli <math>\phi(x)</math>
<math>
z=\{ x\in a : \phi(x) \} = \{x : (x \in a) \and (\phi(x))\}
</math>
Speciální volby <math>\phi(x)</math>
* <math>x \in b</math>
* <math>x \notin b </math>
* <math>x \neq x </math>
===== Definice: průnik, rozdíl =====
Jsou-li <math>a, b</math> množiny, pak:
* '''průnikem''' množin <math>a, b</math> nazýváme množinu:
<math>
a \cap b = \{ x : x \in a \and x \in b \}
</math>
* '''rozdílem''' nazýváme množinu:
<math>
a \setminus b = \{ x : x \in a \and x \notin b \}
</math>
===== Definice: prázdná množina =====
Buď <math>z</math> libovolná množina ((0) zaručuje její existenci). Pak existuje:
<math>
\{ x : x \in z \and x \neq x \}
</math>
(vydělení pro formuli <math>x \neq x</math>), která je jediná (extenzionalita).
Kdy je <math>t \in x</math>? Pokud <math>t \neq t</math>, což ale neplatí pro žádné <math>t</math>.
<math>0</math> je jediná množna <math>y</math> splňující
<math>(\forall x)(x \notin y) </math>.
Nazýváme ji '''prázdná''' množina.
===== Definice: disjunktní množiny =====
O množinách <math>a, b</math> říkáme, že jsou disjunktní, pokud platí:
<math>
a \cap b = 0
</math>
===== Lemma =====
<math>
\neg (\exists)(y\in0)
</math>
<math>
(\forall x)(0\subseteq x)
</math>
<math>
(\forall x)(x \subseteq 0 \leftrightarrow x=0)
</math>
<math>
(\forall a) a = \{ x \in a : x = x\}
</math> z extenzionality a vydělení.
===== Věta: Neexistuje množina všech množin =====
<math>
\neg(\exists z)(\forall x)x\in z
</math>
* Neexistence množiny všech množiny nás zbavuje Russelova paradoxu.
====== Důkaz ======
Sporem. Nechť existuje množina <math>z, (\forall x)x\in z</math>. Vezměme formuli
<math>\phi(x): x\notin x</math>.
Vydělení pro tuto <math>\phi(x)</math> dává množinu:
<math>u=\{x\in z : x \notin x\}</math>.
Musí platit <math>u\in z</math>.
Jestliže <math>u \in u</math>, pak podle vydělení pro <math>x\notin x</math> musí platit <math>u \notin u</math>.
Naopak pro <math>u \notin u</math> je splněna formule <math>\phi(x)</math>, tedy podle vydělení <math>u \in u</math>.
Obě možné cesty vedou ke sporu.
==== (3) axiom dvojice ====
<math>
(\forall a)(\forall b)(\exists z)(\forall x)((x \in z)
\leftrightarrow
((x=a)\or(x=b)))
</math>
===== Definice: neuspořádaná dvojice =====
Jsou-li <math>a,b</math> množiny, pak '''neuspořádanou dvojicí''' množin a,b nazýváme množinu, jejímiž jedinými prvky jsou množiny <math>a,b</math>. Značíme ji <math>\{a,b\}</math>, v případě, že <math>a=b: \{a\}</math>.
* <math>\{a,b\}</math>...dvouprvková
* <math>\{a\}</math>...jednoprvková
====== Lemma ======
<math>
(\forall x,y)\{x\}=\{y\} \leftrightarrow x=y
</math>
<math>
(\forall x,y)\{x\}=\{x,y\} \leftrightarrow x=y
</math>
<math>
(\forall x,y,u,v)\{x,y\}=\{u,v\}
\leftrightarrow
(x=u \and y=v) \or (x=v \and y=u)
</math>
===== Definice: uspořádaná dvojice =====
Jsou-li <math>a,b</math> množiny, pak '''uspořádanou dvojicí''' množin a,b nazýváme množinu <math>\{a,\{a,b\}\}</math>. Značíme ji
<math>\langle a,b \rangle </math>.
====== Lemma ======
<math>
(\forall x,y,u,v)
\langle x,y \rangle = \langle u,v \rangle
\leftrightarrow
(x=u \and y=v)
</math>
===== Definice: uspořádaná n-tice =====
Jsou-li dány <math>a_1,a_2,\dots,a_k, k>1</math>, pak uspořádanou k-ticí definujeme takto:
* <math>\langle a_1 \rangle = a_1</math>
a dále indukcí:
* <math>
\langle a_1,a_2,\dots,a_k \rangle = \langle \langle a_1,\dots,a_{k-1} \rangle ,a_k \rangle
</math>
====== Lemma ======
<math>
\langle a_1,a_2,\dots,a_k \rangle = \langle b_1,b_2,\dots,b_k \rangle
\leftrightarrow
(a_1=b_1 \and a_2=b_2 \and \dots \and a_k=b_k)
</math>
==== (4) axiom sumy ====
{{TODO: axiom sumy}}
===== Definice: kartézký součin =====
===== Definice: binární relace =====
===== Definice: funkce (zobrazení) =====
===== Definice: ostré uspořádání, lineární uspořádání =====
===== Definice: isomorfismus =====
===== Definice: nejmenší, minimální, největší, maximální prvek =====
===== Definice: dobré uspořádání =====
===== Definice: množina předchůdců =====
===== Lemma 1 =====
===== Lemma 2 =====
===== Věta =====
===== Definice: Ordinál =====
===== Věta: O ordinálech =====
===== Věta =====
===== Lemma 3 =====
===== Věta =====
===== Definice a značení =====
===== Lemma 4 =====
===== Definice: ordinální následník ordinálu =====
===== Lemma 5 =====
===== Definice: isolovaný a limitní ordinál =====
===== Definice: přirozené číslo=====
===== Věta =====
=== Kardinály ===
==== Definice: srovnávání mohutností množin ====
==== ... ====
=== Třídy ===
==== ... ====
=== Ordinální aritmetika ===
==== ... ====
=== Nekonečná kombinatorika ===
==== ... ====
=== .... ===
=== Zdroje ===
* [http://lucy.troja.mff.cuni.cz/labtf/poznamky/uvod_do_teorie_mnozin.zip Úvod do teorie množin (zápisky)]
* [http://www.ms.mff.cuni.cz/~zajio1am/notes/temno-ail003-simon-novotna.tar Zápisky z přednášek]
[[category:Matematika]]
