Joukonmahtavuus elikardinaliteetti on joukonalkioiden lukumäärää kuvaava käsite, jota ilmaistaankardinaaliluvulla. Äärellisten joukkojen kardinaaliluku on jokinluonnollinen luku ja äärettömien jokinääretön kardinaaliluku. Käsitteet esitteliGeorg Cantor vuonna 1874 julkaisemassaanjoukko-oppia käsittelevässä kirjoitelmassa.
Esimerkiksi joukossa {1,2,3} alkioita on 3 ja joukossa {1, 2, 3, ...,n} niitä onn.Äärellisillä joukoilla eli sellaisilla joukoilla, joissa on äärellinen määrä alkiota,mahtavuuden sijasta käytetään usein sanaakoko. 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ääninduktiivista luettelointia. Siinä otetaan joukosta alkio ja liitetään siihen toisen joukon alkio pariksi. Jos jokaiselle alkiolle molemmissa joukoissa riittää pari, on joukot yhtä mahtavia eli. Se joukko, jolta parinmuodostuksessa jää alkioita yli, on mahtavampi.
Tarkastellaan esimerkkinä kahta äärellistä joukkoa ja. Vertailu tehdään ensin ottamalla aina joukon alkiolle pari joukosta. Silloin saadaan parit ja joukon 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 ei löydy tyhjentyneestä numerojoukosta paria. Siksi tuomitsemme joukon mahtavammaksi kuin joukon.
Joukon mahtavuus merkitään joko tai. Yhtämahtavuus voidaan merkitä myös tai. Jos joukko on mahtavampi kuin joukko, merkitään.
Äärettömillä joukoilla induktiivinen luetteloiminen ei aina onnistu. Tällöin yritetään löytääfunktio eli kuvaus joukosta toiseen ja sille mahdollinenkäänteiskuvaus. Kuvausten olemassaolosta ja laadusta päätellään joukkojen keskinäinen mahtavuus. Mahdolliset vaihtoehdot ovat:
Viimeinen väite saadaan kahdesta edellisesta tuloksestaCantorin–Schröderin–Bersteinin lauseen avulla.
Esimerkiksiluonnollisten lukujen joukko on yhtä mahtavaosajoukkonsa kanssa. Tämä nähdään kahdella tavalla. Parinmuodostuksessa saadaan parijono, 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 ja sen käänteisfunktio. Näillä voidaan kuvata kaikkilähtöjoukon alkiotmaalijoukon alkioiksi ilman, että yksikään alkio jäisi kuvaamatta. Funktio ja sen käänteisfunktio ovat bijektioita, ja joukot ovat yhtä mahtavia.[1]
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 onlaskettavasti tainumeroituvasti ää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 taiC (engl. continuum) tai joskus (lue: "beth"-1) ja se oli ensimmäinen todettuylinumeroituvasti ääretön lukujoukko. Koska ylinumeroituva lukujoukko on mahtavampi kuin numeroituva joukko, on sen kardinaaliluku aina ääretön.
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.[1]
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- japarittomat luvut,kolmioluvut,neliöluvut jaalkuluvut. Siis on.
Cantor todisti jo 1874, että. Ne hän todisti luettelemallakokonaisluvut jarationaaliluvut tietyn systeemin avulla ja osoitti, että jokaiselle luvulle löytyy pari luonnollisista luvuista. Todistamistavat esitelty artikkelissanumeroituva joukko.
Edelleen Cantor osoitti vuonna 1891reaalilukujen olevan ylinumeroituvasti ääretön joukko. Koska reaaliluvut koostuvat rationaaliluvuista jairrationaaliluvuista, ovat myös irrationaaliluvut ylinumeroituvasti ääretön joukko. Reaaliluvut voidaan jakaa myösalgebrallisiin jatranskendenttisiin lukuihin. Algebralliset luvut ovat numeroituvasti ja transkendenttiset luvut ylinumeroituvasti ääretön joukko.[1]
