{{Stub}} {{predmet|Teorie množin|Petr Simon|AIL063}}
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ď množina všech množin takových, že .
Ptáme se, jestli platí .
Z plyne , naopak z plyne .
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
(1) Axiom extenzionality
$
((\forall x)(\forall y)((\forall u)((u \in x \leftrightarrow u \in y)) \rightarrow
(x=y)) $
(2) Schéma axiomů vydělení
Je-li
formule jazyka teorie množin, která neobsahuje volně proměnnou
, pak následující formule:
$
(\forall a)(\exists z)(\forall x)((x\in z) \leftrightarrow
((x \in a) \and \phi (x))) $
je axiom teorie množin.
(3) Axiom dvojice
$
(\forall a)(\forall b)(\exists z)(\forall x)((x \in z) \leftrightarrow
((x=a)\or(x=b))) $
Libovolné dvě množiny určují dvouprvkovou množinu
(4) Axiom sumy
$ (\forall a)(\exists z)(\forall x)((x \in z)
\leftrightarrow (\exists t)((t \in a) \and (x \in t)))
$
Ke každé množině existuje množina všech prvků jejich prvků
(5) Axiom potence
$ (\forall a)(\exists z)(\forall x)
((x \in z) \leftrightarrow (x \subseteq a)) $
Pro každou množinu existuje množina všech jejich podmnožin.
(6) Schema axiomů nahrazení
Je-li fromule teorie množin, která neobsahuje volné proměnné , pak formule:
$ (\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))) $
je axiom teorie množin.
Obrazem množiny při definovaném zobrazení je množina.
(7) Axiom nekonečna
$ (\exists z)((0 \in z)\and(\forall x)((x \in z) \rightarrow (x \cup {x} \in z)))
$
Existuje nekonečná množina
(8) Axiom fundovanosti
$ (\forall a)((a\neq0) \rightarrow (\exists x)((x \in a) \and (x \cap a=0)))
$
Dodatky k axiomům
(1) extenzionalita
Platí i opačná implikace, něž je v axiomu extenzionality, tj.:
$
(\forall x)(\forall y)(\forall t)(t \in x \leftrightarrow t \in y) \leftrightarrow x = y
$
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 je podmnožinou množiny , zapisujeme , jestliže platí:
$
(\forall t)(t \in x \rightarrow t \in y) $
Říkáme, že množina je vlastní podmnožinou množiny , zapisujeme
, jestliže:
$ (x \subseteq y) \and (x \neq y)
$
Lemma
$ (\forall x)(x \subseteq x) \and \neg (x \subset y)
$
$ (\forall x,y,z)((x\subseteq y) \and (y \subseteq z) \rightarrow (x \subseteq z))
$
$ (\forall x,y,z)((x\subset y) \and (y \subseteq z) \rightarrow (x \subseteq z))
$
$ (\forall x,y,z)((x\subseteq y) \and (y \subset z) \rightarrow (x \subseteq z))
$
$ (\forall x,y)((x\subseteq y) \and (y \subseteq x) \rightarrow (x = y))
$
(2) Schéma axiomů vydělení
Pro každé je to jeden axiom
Proč nemůže být volná proměnná ve ?
Jinak bychom mohli položit , z čehož:
$ (\forall a)(\exists z)(\forall x)
(x \in z \leftrightarrow ((x \in a)\and (x\notin z))) $
což je spor.
Máme-li množinu a formuli
$
z={ x\in a : \phi(x) } = {x : (x \in a) \and (\phi(x))} $
Speciální volby
Definice: průnik, rozdíl
Jsou-li množiny, pak:
průnikem množin nazýváme množinu:
$
a \cap b = { x : x \in a \and x \in b } $
rozdílem nazýváme množinu:
$
a \setminus b = { x : x \in a \and x \notin b } $
Definice: prázdná množina
Buď libovolná množina ((0) zaručuje její existenci). Pak existuje: $
{ x : x \in z \and x \neq x } $
(vydělení pro formuli ), která je jediná (extenzionalita).
Kdy je ? Pokud , což ale neplatí pro žádné .
je jediná množna splňující
. Nazýváme ji prázdná množina.
Definice: disjunktní množiny
O množinách říkáme, že jsou disjunktní, pokud platí:
$ a \cap b = 0
$
Lemma
$ \neg (\exists)(y\in0)
$
$ (\forall x)(0\subseteq x)
$
$ (\forall x)(x \subseteq 0 \leftrightarrow x=0)
$
$ (\forall a) a = { x \in a : x = x}
$ z extenzionality a vydělení.
Věta: Neexistuje množina všech množin
$
\neg(\exists z)(\forall x)x\in z $
Neexistence množiny všech množiny nás zbavuje Russelova paradoxu.
Důkaz
Sporem. Nechť existuje množina . Vezměme formuli
. Vydělení pro tuto dává množinu:
. Musí platit .
Jestliže , pak podle vydělení pro musí platit .
Naopak pro je splněna formule , tedy podle vydělení .
Obě možné cesty vedou ke sporu.
(3) axiom dvojice
$
(\forall a)(\forall b)(\exists z)(\forall x)((x \in z) \leftrightarrow
((x=a)\or(x=b))) $
Definice: neuspořádaná dvojice
Jsou-li množiny, pak neuspořádanou dvojicí množin a,b nazýváme množinu, jejímiž jedinými prvky jsou množiny . Značíme ji , v případě, že .
...dvouprvková
...jednoprvková
Lemma
$
(\forall x,y){x}={y} \leftrightarrow x=y $
$ (\forall x,y){x}={x,y} \leftrightarrow x=y
(\forall x,y,u,v){x,y}={u,v} \leftrightarrow
(x=u \and y=v) \or (x=v \and y=u) $
Definice: uspořádaná dvojice
Jsou-li množiny, pak uspořádanou dvojicí množin a,b nazýváme množinu . Značíme ji
.
Lemma
$ (\forall x,y,u,v)
\langle x,y \rangle = \langle u,v \rangle \leftrightarrow
(x=u \and y=v) $
Definice: uspořádaná n-tice
Jsou-li dány , pak uspořádanou k-ticí definujeme takto:
a dále indukcí:
$
\langle a_1,a_2,\dots,a_k \rangle = \langle \langle a_1,\dots,a_{k-1} \rangle ,a_k \rangle $
Lemma
$
\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) $
(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
category:Matematika