Teorie množin

Teorie množin

Kód předmětu: NAIL063 Přednáší: Petr Simon

• 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ď $ 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

(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)

Axiomy

(0) Axiom existence množiny

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

(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 $ \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

$ (\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 $ \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

$ (\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 $ 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

$ (\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é $ \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

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

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

O množinách $ a, b $ ří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 $ 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

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

Definice: neuspořádaná dvojice

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

$ (\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 $ 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

$ (\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 $ 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

$ \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) $

Zdroje

• Úvod do teorie množin (zápisky)
• Zápisky z přednášek