Mahtavuus

Joukon mahtavuus eli kardinaliteetti on joukon alkioiden lukumäärää kuvaava käsite, jota ilmaistaan kardinaaliluvulla. Äärellisten joukkojen kardinaaliluku on jokin luonnollinen luku ja äärettömien jokin ääretön kardinaaliluku. Käsitteet esitteli Georg Cantor vuonna 1874 julkaisemassaan joukko-oppia käsittelevässä kirjoitelmassa.

Johdanto

Esimerkiksi joukossa {1,2,3} alkioita on 3 ja joukossa {1, 2, 3, ..., n} niitä on n. Äärellisillä joukoilla eli sellaisilla joukoilla, joissa on äärellinen määrä alkiota, mahtavuuden sijasta käytetään usein sanaa koko. Kardinaliteetti-sanaa sen sijaan voidaan käyttää sekä äärellisistä että äärettömistä joukoista.
Kun äärettömässä joukossa on äärettömästi alkioita, ilmoitetaan sen mahtavuus sanalla ääretön. Vaikka ääretön tarkoittaa jotain muuta asiaa kuin lukua, on se hyväksytty mahtavuuden kardinaaliksi, koska se ilmaisee sitä loputtomuutta, mitä alkioiden laskeminen vaatisi.

Numeroituva ja ylinumeroituva

Cantor tutki äärettömiä joukkoja ja havaitsi pian että jotkin joukot ovat "enemmän äärettömiä" kuin toiset. Tämä johti kardinaalilukujen vertailuun. Koska luonnolliset luvut tiedetään jo äärettömäksi joukoksi, merkitään niiden mahtavuutta kardinaaliluvulla   (lue:alef-0). Luonnollisisten lukujen joukosta sanotaan, että se on laskettavasti tai  numeroituvasti ääretön, koska sen alkioista voidaan muodostaa alkiopareja verrattavan joukon alkioiden kanssa.
Cantor oletti, että oli olemassa suurempia kardinaalilukuja ja että ne voitiin järjestää suuruusjärjestykseen . Suurempien joukkojen etsintä tuotti tulosta, kun hän osoitti reaalilukujen olevan suurempi joukko. Vieläkään ei tiedetä, onko reaalilukujen kardinaliteetti  tai  vai jokin muu. Toisin sanoen ei ole pystytty osoittamaan, onko olemassa ylinumeroituvaa joukkoa, jonka mahtavuus olisi pienempi kuin reaalilukujen joukon. Toistaiseksi reaalilukujen kardinaalilukuna käytetään merkintää c tai C (engl. continuum) tai joskus  (lue: "beth"-1) ja se oli ensimmäinen todettu ylinumeroituvasti ääretön lukujoukko. Koska ylinumeroituva lukujoukko on mahtavampi kuin numeroituva joukko, on sen kardinaaliluku aina ääretön.

Mahtavuuteen liittyviä yleisiä tuloksia

Määritelmän mukaan luonnolliset luvut  muodostavat numeroituvasti äärettömän lukujoukon. Voidaan osoittaa, että kaikki osajoukot  ovat myös numeroituvia. Jos  on numeroituva ja ääretön, on olemassa bijektio  ja joukot ovat yhtä mahtavat . Jos  ylinumeroituva ja , niin myös  on ylinumeroituva.

Lukujoukkojen mahtavuus

Kaikki luonnollisten lukujen osajoukot ovat edelliseen viitaten numeroituvia. Erityisesti luonnollisten lukujen äärettömän suuret osajoukot ovat yhtä mahtavia kuin luonnollisten lukujen joukko itse. Tällasia osajoukkoja ovat esimerkiksi parilliset- ja parittomat luvut, kolmioluvut, neliöluvut ja alkuluvut. Siis on .
Cantor todisti jo 1874, että . Ne hän todisti luettelemalla kokonaisluvut ja rationaaliluvut tietyn systeemin avulla ja osoitti, että jokaiselle luvulle löytyy pari luonnollisista luvuista. Todistamistavat esitelty artikkelissa numeroituva joukko.
Edelleen Cantor osoitti vuonna 1891 reaalilukujen olevan ylinumeroituvasti ääretön joukko. Koska reaaliluvut koostuvat rationaaliluvuista ja irrationaaliluvuista, ovat myös irrationaaliluvut ylinumeroituvasti ääretön joukko. Reaaliluvut voidaan jakaa myös algebrallisiin ja transkendenttisiin lukuihin. Algebralliset luvut ovat numeroituvasti ja transkendenttiset luvut ylinumeroituvasti ääretön joukko.