Teorie množin

Z ωικι.matfyz.cz
Verze z 28. 3. 2013, 01:35, kterou vytvořil 78.128.196.3 (diskuse) (Teorie množin (Zermel, Fraenkel): Zkomolenina jména Zermelo opravena)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
Teorie množin
Kód předmětu: NAIL063
Přednáší: Petr Simon


Obsah

Cantorova (nefunkční) teorie množin[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Russelův paradox[editovat | editovat zdroj]

Buď $ M $ množina všech množin $ K $ takových, že $ K \notin K $.

Ptáme se, jestli platí $ M \in M $.

Z $ M \in M $ plyne $ M \notin M $, naopak z $ M \notin M $ plyne $ M\in M $.

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[editovat | editovat zdroj]

(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)[editovat | editovat zdroj]

Jazyk teorie množin[editovat | editovat zdroj]

Axiomy[editovat | editovat zdroj]

(0) Axiom existence množiny[editovat | editovat zdroj]

$ (\exists x)(x=x) $

(1) Axiom extenzionality[editovat | editovat zdroj]

$ ((\forall x)(\forall y)((\forall u)((u \in x \leftrightarrow u \in y)) \rightarrow (x=y)) $

(2) Schéma axiomů vydělení[editovat | editovat zdroj]

Je-li $ \phi(x) $ formule jazyka teorie množin, která neobsahuje volně proměnnou $ z $, 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[editovat | editovat zdroj]

$ (\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[editovat | editovat zdroj]

$ (\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[editovat | editovat zdroj]

$ (\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í[editovat | editovat zdroj]

Je-li $ \psi(u,v) $ fromule teorie množin, která neobsahuje volné proměnné $ w,z $, 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[editovat | editovat zdroj]

$ (\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[editovat | editovat zdroj]

$ (\forall a)((a\neq0) \rightarrow (\exists x)((x \in a) \and (x \cap a=0))) $

Dodatky k axiomům[editovat | editovat zdroj]

(1) extenzionalita[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Říkáme, že množina $ x $ je podmnožinou množiny $ y $, zapisujeme $ x\subseteq y $, jestliže platí:

$ (\forall t)(t \in x \rightarrow t \in y) $

Říkáme, že množina $ x $ je vlastní podmnožinou množiny $ y $, zapisujeme $ x\subset y $, jestliže:

$ (x \subseteq y) \and (x \neq y) $

Lemma[editovat | editovat zdroj]

$ (\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í[editovat | editovat zdroj]

  • Pro každé $ \phi $ je to jeden axiom
  • Proč nemůže být $ z $ volná proměnná ve $ \phi $?

Jinak bychom mohli položit $ \phi(x): x \notin z $, 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 $ a formuli $ \phi(x) $

$ z=\{ x\in a : \phi(x) \} = \{x : (x \in a) \and (\phi(x))\} $

Speciální volby $ \phi(x) $

  • $ x \in b $
  • $ x \notin b $
  • $ x \neq x $
Definice: průnik, rozdíl[editovat | editovat zdroj]

Jsou-li $ a, b $ množiny, pak:

  • průnikem množin $ a, b $ 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[editovat | editovat zdroj]

Buď $ z $ libovolná množina ((0) zaručuje její existenci). Pak existuje: $ \{ x : x \in z \and x \neq x \} $ (vydělení pro formuli $ x \neq x $), která je jediná (extenzionalita).

Kdy je $ t \in x $? Pokud $ t \neq t $, což ale neplatí pro žádné $ t $.


$ 0 $ je jediná množna $ y $ splňující $ (\forall x)(x \notin y) $. Nazýváme ji prázdná množina.

Definice: disjunktní množiny[editovat | editovat zdroj]

O množinách $ a, b $ říkáme, že jsou disjunktní, pokud platí:

$ a \cap b = 0 $

Lemma[editovat | editovat zdroj]

$ \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[editovat | editovat zdroj]

$ \neg(\exists z)(\forall x)x\in z $

  • Neexistence množiny všech množiny nás zbavuje Russelova paradoxu.
Důkaz[editovat | editovat zdroj]

Sporem. Nechť existuje množina $ z, (\forall x)x\in z $. Vezměme formuli $ \phi(x): x\notin x $. Vydělení pro tuto $ \phi(x) $ dává množinu: $ u=\{x\in z : x \notin x\} $. Musí platit $ u\in z $.

Jestliže $ u \in u $, pak podle vydělení pro $ x\notin x $ musí platit $ u \notin u $.

Naopak pro $ u \notin u $ je splněna formule $ \phi(x) $, tedy podle vydělení $ u \in u $.

Obě možné cesty vedou ke sporu.

(3) axiom dvojice[editovat | editovat zdroj]

$ (\forall a)(\forall b)(\exists z)(\forall x)((x \in z) \leftrightarrow ((x=a)\or(x=b))) $

Definice: neuspořádaná dvojice[editovat | editovat zdroj]

Jsou-li $ a,b $ množiny, pak neuspořádanou dvojicí množin a,b nazýváme množinu, jejímiž jedinými prvky jsou množiny $ a,b $. Značíme ji $ \{a,b\} $, v případě, že $ a=b: \{a\} $.

  • $ \{a,b\} $...dvouprvková
  • $ \{a\} $...jednoprvková
Lemma[editovat | editovat zdroj]

$ (\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[editovat | editovat zdroj]

Jsou-li $ a,b $ množiny, pak uspořádanou dvojicí množin a,b nazýváme množinu $ \{a,\{a,b\}\} $. Značíme ji $ \langle a,b \rangle $.

Lemma[editovat | editovat zdroj]

$ (\forall x,y,u,v) \langle x,y \rangle = \langle u,v \rangle \leftrightarrow (x=u \and y=v) $

Definice: uspořádaná n-tice[editovat | editovat zdroj]

Jsou-li dány $ a_1,a_2,\dots,a_k, k>1 $, pak uspořádanou k-ticí definujeme takto:

  • $ \langle a_1 \rangle = a_1 $

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[editovat | editovat zdroj]

$ \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[editovat | editovat zdroj]

Šablona:TODO: axiom sumy

Definice: kartézký součin[editovat | editovat zdroj]
Definice: binární relace[editovat | editovat zdroj]
Definice: funkce (zobrazení)[editovat | editovat zdroj]
Definice: ostré uspořádání, lineární uspořádání[editovat | editovat zdroj]
Definice: isomorfismus[editovat | editovat zdroj]
Definice: nejmenší, minimální, největší, maximální prvek[editovat | editovat zdroj]
Definice: dobré uspořádání[editovat | editovat zdroj]
Definice: množina předchůdců[editovat | editovat zdroj]
Lemma 1[editovat | editovat zdroj]
Lemma 2[editovat | editovat zdroj]
Věta[editovat | editovat zdroj]
Definice: Ordinál[editovat | editovat zdroj]
Věta: O ordinálech[editovat | editovat zdroj]
Věta[editovat | editovat zdroj]
Lemma 3[editovat | editovat zdroj]
Věta[editovat | editovat zdroj]
Definice a značení[editovat | editovat zdroj]
Lemma 4[editovat | editovat zdroj]
Definice: ordinální následník ordinálu[editovat | editovat zdroj]
Lemma 5[editovat | editovat zdroj]
Definice: isolovaný a limitní ordinál[editovat | editovat zdroj]
Definice: přirozené číslo[editovat | editovat zdroj]
Věta[editovat | editovat zdroj]

Kardinály[editovat | editovat zdroj]

Definice: srovnávání mohutností množin[editovat | editovat zdroj]

...[editovat | editovat zdroj]

Třídy[editovat | editovat zdroj]

...[editovat | editovat zdroj]

Ordinální aritmetika[editovat | editovat zdroj]

...[editovat | editovat zdroj]

Nekonečná kombinatorika[editovat | editovat zdroj]

...[editovat | editovat zdroj]

....[editovat | editovat zdroj]

Zdroje[editovat | editovat zdroj]