Mohutnost

Z Wikipedie, otevřené encyklopedie

Mohutnost množiny (také kardinalita množiny) je pojmem teorie množin vyjadřující velikost konečných ale i nekonečných množin.

Obsah

1 Formální definice
2 Vlastnosti pojmu mohutnosti
3 Příklady motivující pojem mohutnosti a jeho vlastnosti
- 3.1 Příklad ovčáka
- 3.2 Hilbertův hotel
4 Mohutnosti některých množin
5 Podívejte se také na

[editovat] Formální definice

Nechť $A$ , $B$ jsou množiny.

Řekneme, že množina $A$ má stejnou nebo menší mohutnost než množina $B$ jestliže existuje zobrazení $f:A\rightarrow B$ které je injektivní. Píšeme $A \leq B$ .
Řekneme, že množiny $A$ , $B$ mají stejnou mohutnost, jestliže existuje zobrazení $f:A\rightarrow B$ které je bijektivní. Píšeme $A \approx B$ .
Řekneme, že množina $A$ má, menší mohutnost než množina $B$ , jestliže $A \leq B$ ale přitom neplatí $A \approx B$ . Píšeme $A < B$ .

[editovat] Vlastnosti pojmu mohutnosti

[editovat] Základní vlastnosti relace $\approx$

Relace $\approx$ je reflexivní, symetrická a tranzistivní:

$( \forall x)( x \approx x)$
$( \forall x,y)( x \approx y \implies y \approx x)$
$( \forall x,y,z) ((x \approx y \and y \approx z) \implies x \approx z)$

Jedná se tedy o ekvivalenci na univerzální třídě V - všechny myslitelné množiny se rozpadají do skupin (tříd ekvivalence neboli faktortříd) podle své mohutnosti.

[editovat] Základní vlastnosti relace $\leq$

Relace $\leq$ je (na univerzální třídě V) reflexivní a tranzitivní:

$( \forall x)( x \leq x)$
$( \forall x,y,z) ((x \leq y \and y \leq z) \implies x \leq z)$

Nejedná se však o uspořádání, neboť tato relace není antisymetrická a to ani slabě:

Například pro dvě různé množiny x = {0,1} a y = {1,2} platí $x \leq y \and y \leq x$ .

Cantor-Bernsteinova věta uvedená v následujícím odstavci, poukazuje na fakt, že relace $\leq$ je „skoroantisymetrická“ - dává do vztahu relace $\leq$ a $\approx$ v následujícím smyslu. Protože relace $\approx$ je ekvivalencí na universální třídě V, lze univerzální třídu podle této relace faktorizovat. Cantor-Bernsteinova věta pak říká, že relace $\leq$ (resp. její přirozené přenesení na třídu $V_{/ \approx}$ faktortříd V) je na $V_{/ \approx}$ slabě antisymetrická, a tedy je neostrým uspořádáním.

[editovat] Základní vlastnosti relace $<$

Jiná situace je u relace $<$ , která je antireflexivní, antisymetrická i tranzitivní:

$( \forall x) \neg( x < x)$
$( \forall x,y) (x < y \implies \neg(y < x))$
$( \forall x,y,z) ((x < y \and y < z) \implies x < z)$

Je tedy ostrým uspořádáním na V. V případě přijetí axiomu výběru je toto uspořádání lineární vzhledem k ekvivalenci $\approx$ :

$(\forall x,y) (x < y \vee x \approx y \vee y < x)$ .

[editovat] Cantor-Bernsteinova věta

Cantor-Bernsteinova věta uvádí do souvislosti obě relace týkající se mohutnosti:
$( \forall x,y)(( x \leq y \and y \leq x) \implies x \approx y)$

Myšlenka důkazu této věty je uvedena v samostatném článku.

[editovat] Cantorova věta

Cantorova věta uvádí do vztahu mohutnost množiny a její potenční množiny:
$( \forall x)( x < P(x))$

[editovat] Vztah ke kardinálním číslům

S ohledem na to, že $\approx$ je ekvivalence, a že kardinální čísla jsou určena především k „zastupování ostatních množin ve věci jejich mohutnosti“, nabízí se samozřejmě otázka, zda je každá množina stejně mohutná, jako některé z kardinálních čísel, tj. zda v každé třídě rozkladu relace $\approx$ je alespoň jeden kardinál.

Odpověď zní ano - ale pouze za předpokladu, že přijmeme axiom výběru - bez něj mohou ve světě množin existovat takové množiny, které nelze vzájemně jednoznačně zobrazit na žádný kardinál.

[editovat] Příklady motivující pojem mohutnosti a jeho vlastnosti

[editovat] Příklad ovčáka

Představme si ovčáka, který má dvě stáda ovcí - bílých a černých. Ovčák se rozhodne zjistit, které ze stád je větší, ale má velký problém - neumí počítat. Dlouho nad svým problémem přemýšlí, až ho napadne jednoduché řešení. Bere postupně ovce vždy po jedné z každého stáda a přivazuje je k sobě, vždy černou k bílé. Ví, že až s tím skončí, nezbude mu buď žádná volná bílá ovce, ale několik černých ano, nebo nezbude naopak žádná volná černá, ale několik bílých ano a konečně se může stát, že nezbyde žádná bílá ani černá ovce. V prvním případě ovčák ví, že bílých ovcí je méně, ve druhém je černých méně a ve třetím případě jsou všechny ovce svázány po dvojcích k sobě, a tedy jsou obě stáda stejně početná.

Ovčák nemá k dispozici pojmy, které by označovaly jednotlivé počty ovcí (nezná čísla), stejně jako člověk neobeznámený s teorií množin (nebo ten, který teorii množin teprve vytváří) nemá pojmy, které by označovaly jednotlivé počty prvků nekonečných množin (nezná kardinální čísla). Přesto však jsou oba schopni svá stáda resp. množiny porovnávat z hlediska velikosti, neboť k pouhému porovnání není třeba přesné velikosti znát.

[editovat] Hilbertův hotel

Následující příklad uváděl svým studentům David Hilbert, aby jim ukázal, že běžná intuice může při práci s aktuálním nekonečnem velmi klamat.

Představme si hotel s nekonečným (spočetným) počtem pokojů. Na vrátnici tohoto hotelu přijde člověk, který se chce ubytovat, všechny pokoje však jsou již obsazené. Recepční však hosta nepošle pryč. Zato si zavolá pokojskou a nakáže jí, aby obešla všechny pokoje a každého z hostů požádala, aby se přestěhoval do pokoje s číslem o jedna vyšším, než v jakém dosud bydlel. Po té, co hosté udělají vše podle pokynů pokojské, jsou opět všichni ubytováni, ale navíc se uvolnil pokoj s číslem 1, kam se nyní může nastěhovat nově příchozí. Dokud chodí na vrátnici vždy jen konečné skupinky lidí, je vše v pořádku - pokojská vždy požádá hosty, aby se odstěhovali do pokojů s číslem o několik vyšším a požadovaný počet pokojů s nejnižšími čísly zůstane volný pro nové hosty. Jednoho dne však na vrátnici tohoto hotelu přijde nekonečně (spočetně) mnoho lidí najednou a všichni se chtějí ubytovat. Vrátný si se vzniklou situací neví rady, a tak zavolá majitele hotelu, aby tolika rozzuřeným hostům vysvětlil, že pro ně v hotelu již není místo. Hoteliér však dostane nápad. Opět vyšle pokojskou, aby obešla všechny pokoje, ale tentokrát má za úkol hostům vyřídit, aby se přestěhovali do pokoje s číslem dvojnásobným oproti tomu, v němž bydleli dosud. Tím se uvolní všechny pokoje s lichými čísly a všichni noví hosté se mohou pohodlně nastěhovat.

[editovat] Mohutnosti některých množin

Mohutnost množiny přirozených čísel se obvykle označuje $\aleph_0$ ("alef nula" - alef je první písmeno hebrejské abecedy). Mohutnost rovnou $\aleph_0$ mají množiny:

přirozených čísel
celých čísel
racionálních čísel
algebraických čísel
sudých přirozených čísel
prvočísel
všech konečných podmnožin přirozených čísel

Mohutnost množiny všech reálných čísel se obvykle označuje $c$ či $2^{\aleph_0}$ (význam symbolů - viz článek Kardinální aritmetika). Tato mohutnost je ostře větší než mohutnost množiny přirozených čísel. Je mohutností například množiny:

reálných čísel
komplexních čísel
všech podmnožin přirozených čísel
všech spojitých reálných funkcí
všech bodů v rovině
všech bodů v prostoru

Na otázku, zda existuje nějaká mohutnost mezi $\aleph_0$ a $2^{\aleph_0}$ (tj. zda existuje množina reálných čísel, která není spočetná, ale přitom má menší mohutnost, než množina všech reálných čísel) nelze najít odpověď z běžných axiomů teorie množin. Tzv. hypotézu kontinua, která tvrdí, že taková množina neexistuje, tj. že
$\aleph_1 = 2^{\aleph_0}$
nelze z axiomů teorie množin ani vyvrátit, ani dokázat.

Naopak na otázku, zda existuje více než jedna nespočetná mohutnost, dává odpověď Cantorova věta, která říká, že
$(\forall \alpha) ( \aleph_{\alpha} < 2^{\aleph_{\alpha}} ) \,\!$

To znamená, že nespočetných mohutností je nekonečně mnoho, protože
$\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < 2^{2^{2^{\aleph_0}}} < \ldots \,\!$

[editovat] Podívejte se také na

Související články obsahuje:
Portál Matematika

Citováno z „http://cs.wikipedia.org../../../m/o/h/Mohutnost.html“

Kategorie: Teorie množin | Kardinální čísla

Mohutnost

Z Wikipedie, otevřené encyklopedie

Obsah

[editovat] Formální definice

[editovat] Vlastnosti pojmu mohutnosti

[editovat] Základní vlastnosti relace $\approx$

[editovat] Základní vlastnosti relace $\leq$

[editovat] Základní vlastnosti relace $<$

[editovat] Cantor-Bernsteinova věta

[editovat] Cantorova věta

[editovat] Vztah ke kardinálním číslům

[editovat] Příklady motivující pojem mohutnosti a jeho vlastnosti

[editovat] Příklad ovčáka

[editovat] Hilbertův hotel

[editovat] Mohutnosti některých množin

[editovat] Podívejte se také na

Views

Navigace

Hledání

V jiných jazycích

Mohutnost

Z Wikipedie, otevřené encyklopedie

Obsah

[editovat] Formální definice

[editovat] Vlastnosti pojmu mohutnosti

[editovat] Základní vlastnosti relace

[editovat] Základní vlastnosti relace

[editovat] Základní vlastnosti relace <

[editovat] Cantor-Bernsteinova věta

[editovat] Cantorova věta

[editovat] Vztah ke kardinálním číslům

[editovat] Příklady motivující pojem mohutnosti a jeho vlastnosti

[editovat] Příklad ovčáka

[editovat] Hilbertův hotel

[editovat] Mohutnosti některých množin

[editovat] Podívejte se také na

Views

Navigace

Hledání

V jiných jazycích

[editovat] Základní vlastnosti relace $\approx$

[editovat] Základní vlastnosti relace $\leq$

[editovat] Základní vlastnosti relace $<$