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

• siten, että f on injektio.
• siten, että f on surjektio.
• siten, että f on bijektio.

Esimerkiksi luonnollisten lukujen joukko 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ä

• .

[muokkaa] Rationaalilukujen ja luonnollisten lukujen mahtavuudesta

Perustellaan, miksi rationaalilukuja on "yhtä paljon" kuin luonnollisia lukuja eli on yhtä mahtava kuin .

Koska on osajoukko :sta, edellinen on korkeintaan yhtä mahtava kuin jälkimmäinen. Siis

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 ja Cantorin–Schröderin–Bersteinin lauseen perusteella rationaalilukujen joukon mahtavuus on sama kuin luonnollisten lukujen joukon mahtavuus.

[muokkaa] Katso myös

• Numeroituva joukko
• Ylinumeroituva joukko