Mahtavuus

Wikipedia

Joukon mahtavuus eli kardinaliteetti tarkoittaa joukon alkioiden lukumäärää, jota merkitään kardinaaliluvulla. Kardinaaliluku voi olla luonnollinen luku tai ääretön.

Esimerkiksi joukon A = {1,2,3} mahtavuus on 3 ja joukon N = {1, 2, 3, ..., n} mahtavuus on n. Ensimmäinen ääretön kardinaaliluku on $\aleph_0$ (alef-0), jolla tarkoitetaan luonnollisten lukujen joukon mahtavuutta (ns. numeroituvasti ääretön). Jatkumon, esimerkiksi reaalilukujen, kardinaliteettia merkitään usein kirjaimella c (engl. continuum). Epätyhjien joukkojen X ja Y kardinaliteettien vertailu on määritelty seuraavasti:

$\mbox{card}(X) \le \mbox{card}(Y) \Leftrightarrow \exists f:X \rightarrow Y$ siten, että $f$ on injektio.
$\mbox{card}(X) \ge \mbox{card}(Y) \Leftrightarrow \exists f:X \rightarrow Y$ siten, että $f$ on surjektio.
$\mbox{card}(X) = \mbox{card}(Y) \Leftrightarrow \exists f:X \rightarrow Y$ siten, että $f$ on bijektio.

Esim. luonnollisten lukujen joukko $\mathbb{N}$ on yhtä mahtava osajoukkonsa {1, 3, 5, 7, 9, ...} kanssa, sillä funktio f(x) = 2x+1 on bijektio ensin mainitulta joukolta toiselle. Aiemmista määritelmistä on myös helposti osoitettavissa, että

$\mbox{card}(X) \le \mbox{card}(Y) \Leftrightarrow \mbox{card}(Y) \ge \mbox{card}(X)$ .

[muokkaa] Rationaalilukujen ja luonnollisten lukujen mahtavuudesta

Perustellaan, miksi rationaalilukuja on "yhtä paljon" kuin luonnollisia lukuja eli $\mathbb{N}$ on yhtä mahtava kuin $\mathbb{Q}$ .

Koska $\mathbb{N}$ on osajoukko $\mathbb{Q}$ :sta, edellinen on korkeintaan yhtä mahtava kuin jälkimmäinen. Siis $\mbox{card}(\mathbb{N}) \le \mbox{card}(\mathbb{Q})$

Olkoon n ja m keskenään jaottomia positiivisia kokonaislukuja. Muodostetaan injektio rationaaliluvuila luonnollisille luvuille asettamalla

f(0)=1
f(n)=3ⁿ
f(-n)=2·3ⁿ
f(m/n)=3^m5ⁿ
f(-m/n)=2·3^m5ⁿ

Näin jokainen rationaaliluku kuvautuu luonnolliselle luvulle ja alkulukuesityksen yksikäsitteisyydestä seuraa, että kuvaus on injektio.

Injektion olemassaolosta seuraa, että rationaalilukujen joukon mahtavuus on korkeintaan luonnollisten lukujen joukon mahtavuus. Siis $\mbox{card}(\mathbb{Q}) \le \mbox{card}(\mathbb{N})$ ja Cantorin–Schröderin–Bersteinin lauseen perusteella rationaalilukujen joukon mahtavuus on sama kuin luonnollisten lukujen joukon mahtavuus.