Matematické Fórum

Olin · 08. 09. 2009 10:41

Zdravím, vsadili jsme se s kolegou, jestli je množina všech podmnožin přirozených čísel spočetná nebo ne. Můžete nás prosím rozsoudit, nejlépe včetně důkazu? Diky moc předem.

Kondr · 08. 09. 2009 11:21

↑ Olin:Množina všech podmnožin přirozených čísel má mocnost kontinua (je jich stejně, jako reálných čísel). Důkaz vede přes bijekci mezi charakteristickými funkcemi těch podmnožin a zápisy čísel z intervalu (0,1) ve dvojkové soustavě. Jen je potřeba ošetřit nejednoznačnosti zápisu typu
0,1001111111111.....=0,1010000.....

Rumburak

↑ Olin:
Je-li M množina, pak nechť P(M) značí množinu všech částí množiny M.
Obecně platí Cantorova věta, která říká:

Pro libovolnou množinu M je $|M| < |P(M)|$ .

Symbolem |X| zde míním muhutnost množiny X. Důkaz dodám rovněž - doufám, že se tak stane po obědě.

EDIT 1 - Slíbený důkaz Cantorovy věty:
Je-li $x\in M$ , potom $\{x\} \in P(M)$ , z toho plyne, že $|M| \le |P(M)|$ .
Předpokládejme nyní, že $|M| = |P(M)|$ . Existuje tedy prosté zobrazení f , jehož definičním oborem je M a oborem hodnot P(M).
Definujme množinu $D=\{x \in M; \,\, x \,\notin \, f(x) \}$ .
Zřejmě $D \in P(M)$ a tedy vzhledem k vlastnostem funkce f existuje (a to právě jedno) $d \in M$ takové, že $D = f(d)$ .
Ptejme se, zda platí $d \in D$ nebo naopak $d \notin D$ .
Snadnou úvahou dospějeme ke sporu
$d \in D$ tehdy a jen tehdy, když $d \notin D$ .

Musí proto platit $|M| < |P(M)|$ .

EDIT 2. Cantorovu větu jsem pro zjednodušení vyslovil ve versi předpokládající platnost axiomu výběru (aby bylo možno bez problémů
hovořit o mohutnostech množin). V teorii množin bez axiomu výběru je nutno větu a jednotlivé partie důkazu formulovat přímo pomocí
pojmů subvalence a akvivalence množin.

Matematické Fórum

#1 08. 09. 2009 10:41

Mohutnost množiny

#2 08. 09. 2009 11:21

Re: Mohutnost množiny

#3 08. 09. 2009 11:43 — Editoval Rumburak (11. 09. 2009 15:11)

Re: Mohutnost množiny

Zápatí