Numeroituva joukko

Matematiikassa termiä numeroituva käytetään kuvaamaan joukon sisältämien alkioiden lukumäärää. Jos joukossa on ääretön määrä alkioita, numeroituvuus ilmaisee äärettömän määrän laadun. Äärettömien joukkojen kokoeroja voi selvittää vertailemalla joukkojen alkioiden lukumääriä keskenään. Vaikka molemmat joukot ovat äärettömän suuria, voi toinen joukko sisältää merkittävästi enemmän alkioita kuin toinen joukko. Tällöin sanotaan sen olevan mahtavampi joukko.
Numeroituvuuden termin otti käyttöön joukko-opin luoja Georg Cantor vuonna 1874 julkaistussa kirjoituksessaan ja hän todisti sillä monien joukkojen mahtavuuden olevan sama kuin luonnollisten lukujen joukolla.
Äärettömien joukkojen vertailu.
Eräissä lukujoukoissa on alkioita ääretön lukumäärä, joten tavanomainen lukumäärän laskeminen luettelemalla joukon alkiot ei onnistu. Kahden äärettömän joukon kokoa voidaan kuitenkin verrata muodostamalla alkioparien joukko kummankin joukon alkioista. Esimerkiksi joukoista, joissa on "luonnolliset luvut" ja "parilliset luonnolliset luvut", voidaan muodostaa alkioparijoukko, jossa on alkiot 
formula_1
Tässä joukossa vasen pari on luonnollisen luvun alkio ja oikea pari parillisen luonnollisen luvun alkio. Vaikka kummankin joukon alkioita on ääretön määrä, voidaan niistä muodostaa parit, joiden muodostamiseen osallistuvat lopulta kaikki kummankin joukon alkiot. Tästä päätellään, että alkioiden lukumäärä on "sama", vaikka itse lukumäärää ei määritetä.
Edelliseen esimerkkiin sisältyy paradoksi (katso Galilein paradoksi), joka on kiehtonut matemaatikkoja toista sataa vuotta. Miten voi parillisia lukuja olla yhtä monta kuin luonnollisia lukuja? Eikö parillisia lukuja ole puolet vähemmän kuin luonnollisia lukuja? Cantorin ajatusleikki parinmuodostuksesta osoittaa kuitenkin, että kumpikin lukujoukko on ehtymätön ja jokaiselle alkiolle löytyy aina toisesta lukujoukosta pari. Äärettömien joukkojen tapauksissa joukon "kokoa" kutsutaankin joukon "mahtavuudeksi" erotukseksi äärellisten joukkojen koosta. Äärettömän joukon kokoa ei arvioida numeerisesti vaan sen mahtavuutta arvioidaan vertailujoukon avulla. Vertailun tulos on, että toinen joukko on yhtä mahtava tai mahtavampi kuin toinen joukko. Joukot voidaan asettaa mahtavuusjärjestykseen vertailun avulla.
Määritelmä.
Joukko formula_2 on numeroituva kahdessa tapauksessa. formula_2 on "numeroituva", jos sen mahtavuus on äärellinen. Esimerkiksi suomalaiset aakkoset on numeroituva joukko, koska aakkoset voidaan lueteltuina (aakkosjärjestyksessä) laskea ja niitä on äärellinen määrä 29. formula_2 on "numeroituvasti ääretön", jos se on yhtä mahtava kuin luonnollisten lukujen formula_5 joukko. Parinmuodostus vertailujoukon formula_6 kanssa jatkuu äärettömän monta kertaa tai jää kesken, mutta jokaiselle joukon formula_2 alkiolle riittää joukosta formula_6 pari.
Jos parinmuodostusprosessissa huomataan tilanne, että joukossa formula_2 on alkioita, joita ei pystytä luetteloimaan joukon formula_6 alkioilla, kutsutaan joukkoa formula_2 ylinumeroituvaksi. Intuitiivisesti ajatellaan, että joukossa formula_2 on "enemmän alkioita" kuin joukossa formula_6 eli se on mahtavampi joukko. Esimerkiksi reaalilukujen joukko formula_14 on osoitettu mahtavammaksi kuin formula_6 eli se on ylinumeroituvasti ääretön.
Merkintä.
Joukon formula_2 mahtavuutta merkitään matematiikan kirjallisuudessa joko formula_17 tai formula_18. Joukkojen mahtavuuden suuruus ilmaistaan heprean kielen aakkosella formula_19, joka lausutaan "alef". Numeroituvan joukon formula_2, kuten myös luonnollisten lukujen joukon formula_6, mahtavuutta merkitään kardinaaliluvulla formula_22. Tämän arvo on formula_23 ja se on pienin ääretön kardinaaliluku.
Jos joukko on ylinumeroituva, joukon mahtavuus ilmaistaan kardinaaliluvuilla formula_24 tai formula_25 tai ..., missä kardinaaliluvut ovat formula_26 eri mahtavuudella ylinumeroituvuuden laadun mukaan. Kardinaaliluvuilla on suuruusjärjestys formula_27.
Numeroituvuuden määritys funktion kuvauksena.
Vertailuparien muodostus voidaan tulkita karteesisen tulon formula_28 muodostamiseksi, mikä voidaan lausua myös funktion kuvauksen avulla. Silloin kuvaus tutkittavasta lukujoukosta luonnollisten lukujen joukkoon
formula_29
vastaisi parinmuodostusta siten, että kuvauksen formula_30 lähtö- ja maalijoukon alkiot ovat pareja. Jos kuvaus formula_30 on injektio, on lähtöjoukko numeroituva tai numeroituvasti ääretön. Jos kuvaus on peräti bijektio, on lähtöjoukko formula_2 numeroituvasti ääretön. Bijektion olemassaolo voidaan todeta myös, kun kahden joukon välille löydetään kaksi injektiota formula_33 ja formula_34 siten, että formula_35 ja formula_36. Tällöin Cantorin–Schröderin–Bernsteinin lauseen nojalla on olemassa bijektio formula_37.
Yleisiä tuloksia.
Numeroituvien joukkojen aidot osajoukot ovat myös numeroituvia. Jos esimerkiksi rationaaliluvut on numeroituva joukko, myös sen osajoukko kokonaisluvut on numeroituva. Myös numeroituva määrä numeroituvia joukkoja muodostaa unionina numeroituvan joukon.
Esimerkkejä numeroituvista äärettömistä joukoista.
Edellisen esimerkin mukaisesti parilliset positiiviset luvut ovat numeroituvasti ääretön joukko. Samoin ovat esimerkiksi kokonaislukujen (formula_38), algebrallisten lukujen ja rationaalilukujen joukot (formula_39) numeroituvia.. Sitä vastoin esimerkiksi reaalilukujen joukko formula_14 ei ole numeroituva vaan ylinumeroituva eli aidosti mahtavampi kuin mikään edellä mainituista.
Todistus kokonaislukujen osalta.
Kokonaisluvut formula_41 voidaan osoittaa numeroituvasti äärettömäksi joukoksi Cantorin esittämällä yksinkertaisella tavalla. Vaikka joukko on "molemmista päistään" ääretön, voidaan lukujen luettelointi aloittaa lukujoukon keskeltä:
formula_42
Nämä uudelleen ryhmitellyt luvut numeroidaan luonnollisilla luvuilla seuraavasti:
formula_43, mikä voidaan myös esittää bijektiona luonnollisilta luvuilta (formula_44) kokonaisluvuille seuraavasti: 
formula_45 
Tällä tavalla tavoitetaan kaikki kokonaisluvut ja ne voidaan yhdistää vuorollaan yhden luonnollisen luvun kanssa, kun parinmuodostusta jatketaan äärettömän monta kertaa. Tämän esimerkin perusteella kokonaisluvut ovat numeroituvasti ääretön lukujoukko eli sen mahtavuus on formula_46.
Kokonaislukujen joukko on numeroituvasti ääretön myös siksi, että se on unioni kolmesta numeroituvasta joukosta:
formula_47 
Todistus rationaalilukujen osalta.
Rationaalilukujen numeroituvuus on todistettu artikkelissa mahtavuus Cantorin esittelemällä luettelointimenetelmällä.
Numeroituvaisuus voidaan todistaa myös numeroituvien osajoukkojen unionin numeroituvuudella. Jaetaan rationaaliluvut useaan osajoukkoon, jonka alkioilla on aina samat nimittäjät. Tällainen osajoukko on esimerkiksi formula_48, jonka alkioilla on nimittäjänä kokonaisluku formula_49:
formula_50
Joukko formula_48 on formula_49:n arvosta riippumatta numeroituvasti ääretön, koska alkioita on yhtä monta kuin murtolukujen osoittajissa olevat kokonaisluvut.
Kaikki rationaaliluvut formula_39 saadaan osajoukkojen formula_48 unionina, kun formula_49 käy läpi kaikki kokonaisluvut formula_38
formula_57
missä osajoukkoja on numeroituvasti ääretön joukko.
Numeroituvien joukkojen karteesiset tulot.
Rationaalukujen todistelu on samantapainen myös kahden numeroituvan joukon karteesisen tulon numeroituvuuden todistelussa. Esimerkiksi kahden luonnollisen joukon karteesinen tulo formula_58 on siten myös numeroituva joukko. Itse asiassa kaikki numeroituvien joukkojen kaikki karteesiset tulot formula_59 ovat numeroituvia joukkoja.
Keksimällä bijektio formula_60, missä
formula_61
on numeroituvuus toteamisen jälkeen osoitettu. 
Toinen tapa on havaita injektiot formula_62, jossa formula_63, ja formula_64, jossa formula_65. Näin ollen Cantorin–Schröderin–Bernsteinin lauseen nojalla on olemassa bijektio formula_66, joten karteesinen formula_67 tulo numeroituu. 
Todistetaan induktiolla, että karteesinen tulo formula_68 on numeroituva kaikilla formula_44: 
formula_70 on itsestään selvästi numeroituva ja formula_67 on numeroituva, koska on olemassa bijektio formula_62, kun formula_33 on esimerkiksi formula_61.
formula_75 on numeroituva formula_76 on olemassa bijektio formula_77.
Olkoon kuvaus formula_78 määritelty siten, että formula_79 formula_80. Koska formula_33 on bijektio ja koska formula_34 on induktio-oletuksen nojalla bijektio, niin formula_83:n on myös oltava bijektio. Tällöin karteesinen tulo formula_84 numeroituu. 
Induktioaskel.
formula_67 on numeroituva. Induktioaskeleessa todistettiin, että formula_86 ja jokainen sitä seuraavakin luonnollisten lukujen joukolla konstruoitu karteesinen tulo on numeroituva. Näin ollen on siis osoitettu induktiolla, että karteesinen tulo formula_68 on numeroituva kaikilla formula_44.