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.
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.
Äärellisten joukkojen vertailussa voidaan käyttää alkioiden laskemista. Kummankin joukon alkiot lasketaan ja verrataan kardinaaleja keskenään. Äärettömillä joukoilla käytetään induktiivista luettelointia. Siinä otetaan joukosta formula_1 alkio ja liitetään siihen toisen joukon formula_2 alkio pariksi. Jos jokaiselle alkiolle molemmissa joukoissa riittää pari, on joukot yhtä mahtavia eli formula_3. Se joukko, jolta parinmuodostuksessa jää alkioita yli, on mahtavampi.
Tarkastellaan esimerkkinä kahta äärellistä joukkoa formula_4 ja formula_5. Vertailu tehdään ensin ottamalla aina joukon formula_2 alkiolle pari joukosta formula_1. Silloin saadaan parit formula_8 ja joukon formula_1 alkiot riittivät. Tämä ei vielä merkitse, että joukot ovat yhtä mahtavia. Parinmuodostus tulee onnistua myös toisin päin. Tällöin muodostetaan jokaiselle kirjaimelle pari numerosta. Tämä ei onnistu, koska kirjaimelle formula_10 ei löydy tyhjentyneestä numerojoukosta paria. Siksi tuomitsemme joukon formula_1 mahtavammaksi kuin joukon formula_2.
Joukon formula_1 mahtavuus merkitään joko formula_14 tai formula_15. Yhtämahtavuus voidaan merkitä myös formula_16 tai formula_17. Jos joukko formula_1 on mahtavampi kuin joukko formula_2, merkitään formula_20.
Äärettömillä joukoilla induktiivinen luetteloiminen ei aina onnistu. Tällöin yritetään löytää funktio eli kuvaus joukosta toiseen ja sille mahdollinen käänteiskuvaus. Kuvausten olemassaolosta ja laadusta päätellään joukkojen keskinäinen mahtavuus. Mahdolliset vaihtoehdot ovat:
Viimeinen väite saadaan kahdesta edellisesta tuloksesta Cantorin–Schröderin–Bersteinin lauseen avulla.
Esimerkiksi luonnollisten lukujen joukko formula_27 on yhtä mahtava osajoukkonsa formula_28 kanssa. Tämä nähdään kahdella tavalla. Parinmuodostuksessa saadaan parijono formula_29, jossa pariksi valitaan toisesta joukosta aina kaksi kertaa suurempi luku. Käänteinen parinvalinta toimii niin, että parillisen luvun pariksi valitaan aina puolet pienempi luku. Tätä voisi jatkaa äärettömän monta kertaa ja siksi todetaankin, että parilliset luvut ja luonnolliset luvut ovat yhtä mahtavat.
Toinen menetelmä on keksiä joukkojen välille kuvaus, jolle löydetään käänteiskuvaus. Tällainen kuvauspari on funktio formula_30 ja sen käänteisfunktio formula_31. Näillä voidaan kuvata kaikki lähtöjoukon alkiot maalijoukon alkioiksi ilman, että yksikään alkio jäisi kuvaamatta. Funktio ja sen käänteisfunktio ovat bijektioita, ja joukot ovat yhtä mahtavia.
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 formula_32 (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 formula_33. Suurempien joukkojen etsintä tuotti tulosta, kun hän osoitti reaalilukujen olevan suurempi joukko. Vieläkään ei tiedetä, onko reaalilukujen kardinaliteetti formula_34 tai formula_35 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 formula_36 (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.
Määritelmän mukaan luonnolliset luvut formula_37 muodostavat numeroituvasti äärettömän lukujoukon. Voidaan osoittaa, että kaikki osajoukot formula_38 ovat myös numeroituvia. Jos formula_1 on numeroituva ja ääretön, on olemassa bijektio formula_40 ja joukot ovat yhtä mahtavat formula_41. Jos formula_42 ylinumeroituva ja formula_43, niin myös formula_1 on ylinumeroituva.
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 formula_45.
Cantor todisti jo 1874, että formula_46. 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.