Ylinumeroituva joukko

Ylinumeroituva joukko on matematiikassa joukko-opin termi ja se tarkoittaa joukkoa, joka ei ole numeroituva. Siinä on silloin merkittävästi enemmän alkioita kuin numeroituvassa joukossa eli se on mahtavampi joukko.
Koska numeroituva joukko voi olla alkiomäärältään joko äärellinen tai ääretön, on näitä joukkoja mahtavampi joukko aina alkiomäärältään ääretön. Kansantajuisesti ilmaistuna: kun numeroituvasti ääretön joukko sisältää aina "yhtä monta alkiota" kuin luonnollisten lukujen joukko formula_1, ylinumeroituvassa joukossa on huomattavasti enemmän lukuja. Numeroituvuus voidaan todeta asettamalla tutkittavan joukon alkiot yksi kerrallaan pariksi luonnollisten lukujen alkioiden kanssa siten, että kaikki joukon alkiot tulevat käsiteltyä yhden kerran. Ylinumeroituvan joukon alkioita on niin paljon, ettei sen alkioita pystytä edes luettelemaan missään järjestyksessä, jotta parinmuodostusta voisi suorittaa. 
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. Vuonna 1891 hän keksi menetelmän osoittaa reaaliluvut ylinumeroituvasti äärettömäksi joukoksi.
Määritelmä.
Joukko formula_2 on ylinumeroituva, jos se ei ole äärellinen tai numeroituvasti ääretön joukko. Ylinumeroituvuuden osoittaminen on yleisessä tapauksessa vaikeaa, vaikka joitakin helppoja tapauksia tunnetaankin.
Merkintä.
Joukon formula_2 mahtavuutta merkitään matematiikan kirjallisuudessa joko formula_4 tai formula_5. Joukkojen mahtavuuden suuruus ilmaistaan heprean kielen aakkosilla formula_6 tai formula_7, joka lausutaan "alef" ja '"beth". Numeroituvan joukon formula_2, kuten myös luonnollisten lukujen joukon formula_9, mahtavuutta merkitään kardinaaliluvulla formula_10. Tämän arvo on formula_11 ja se on pienin ääretön kardinaaliluku. 
Jos joukko on ylinumeroituva, joukon mahtavuus ilmaistaan kardinaaliluvuilla formula_12, formula_13, ..., missä kaikki kardinaaliluvut ovat formula_14, ylinumeroituvuuden laadun mukaan. Kardinaaliluvuilla on suuruusjärjestys formula_15 
Cantorin ajatus oli, että mahtavuudeltaan pienimmällä ylinumeroituvalla joukolla olisi kardinaaliluku formula_12. Kun hän osoitti reaaliluvut ylinumeroituvaksi joukoksi, hän oletti aluksi, että reaalilukujen kardinaaliluku olisi formula_12. Tätä ei voitu osoittaa todeksi, joten varmuuden vuoksi kardinaaliluvuksi on otettu formula_18, joka on formula_19 .
Ylinumeroituvuuden toteaminen funktion kuvauksesta.
Joukko formula_2 on ylinumeroituva, jos ja vain jos on olemassa jokin surjektiivinen kuvaus formula_21 joukolta formula_2 luonnollisille luvuille formula_9,
formula_24
joka ei ole injektio. Joukko formula_2 on numeroituva, jos ja vain jos kuvaus formula_21 on bijektio.
Yleisiä tuloksia.
Jos joukon formula_2 osajoukko formula_28 on ylinumeroituva, niin myös joukko formula_2 on ylinumeroituva.
Jos joukko formula_2 on ylinumeroituva ja 
formula_31
on "bijektio", niin silloin myös formula_32 on ylinumeroituva. 
Esimerkkejä ylinumeroituvasti äärettömistä joukoista.
Reaaliluvut.
Ensimmäisen todistelun reaalilukujen formula_33 ylinumeroituvuudesta esitti Cantor vuonna 1891 julkaisussa "Über eine elementare Frage der Mannigfaltigkeitslehre". Tämä kuuluisa todistus tunnetaan nimellä Cantorin diagonaaliargumentti. Hän tarkasteli lukuvälin formula_34 lukuja ja huomasi, ettei niitä pystytä esittämään luettelomuodossa. Jos sitä yritetään, voidaan helposti luoda desimaaliluku, joka puuttuu esitetystä luettelosta. Näin ollen numeroituvuutta ei ole ja väli formula_34 on ylinumeroituvasti ääretön. Koko reaalilukujen joukko on ylinumeroituva, koska sen osajoukko formula_34 on ylinumeroituva. Reaaliluvut ovat ylinumeroituva joukko myös siksi, että voidaan myös määrittää "bijektio"
formula_37
missä bijektiona on esimerkiksi formula_38 
Reaalilukujen mahtavuuden määrittäminen on ollut ongelmallista niin sanotun kontinuumihypoteesin epämääräisyyden vuoksi. Siksi reaalilukujen kardinaaliluvuksi on merkitty formula_18, joka on suurempi tai yhtäsuuri kuin pienimmän ylinumeroituvan joukon kardinaaliluku formula_40. Eräs tulos kardinaaliluvulle saadaan, kun ajatellaan reaalilukujen joukon olevan yhtä mahtava kuin äärettömästi numeroituvan joukon osajoukkojen joukko. Tällöin reaalilukujen mahtavuus voidaan ilmaista formula_41:n avulla formula_42 
Transkendenttiluvut.
Transkendenttiluvut ovat sellaisia reaalilukuja, jotka eivät ole algebrallisia lukuja. Jos kerran algebrallisten lukujen on osoitettu olevan numeroituvasti ääretön joukko, ovatko transkendenttiluvut sitten ylinumeroituva joukko? Tällöin reaalilukujen ylinumeroituvuus johtuisi sen osajoukkona olevan transkendenttilukujen joukon ylinumeroituvuudesta. 
Tämän voi todistaa epäsuorasti. Olkoon formula_43 algebralliset luvut ja formula_32 transkendenttiluvut, jolloin formula_45. Koska formula_43 on numeroituva joukko, niin formula_33 tulisi olla numeroituva joukko, jos formula_32 on numeroituva. Koska formula_33 on kuitenkin ylinumeroituva, täytyy formula_32 olla myös ylinumeroituva. 
Reaalilukujoukkojen karteesinen tulo.
Karteesinen tulo formula_51 voidaan tulkita koordinaatiston "xy"-tasoksi, jossa jokainen tason piste on kahden reaaliluvun koordinaattipari. Onko tässä joukossa enemmän pisteitä kuin suoralla, jota edustaa koordinaattiakseli? Ei ole, vaan molemmilla joukoilla on sama kardinaaliluku. 
Tämä voidaan osoittaa keksimällä "bijektio"
formula_52
jolloin kuvauksen lähtö- ja maalijoukolla on sama kardinaaliluku. Aiemmin todettiin, että joukolla 
formula_34 on sama kardinaaliluku kuin reaalijoukolla. Samasta syystä myös joukolla formula_54 on sama kardinaaliluku kuin formula_51, koska se on jälkimmäisen osajoukko.
Kaikilla karteesisilla tuloilla formula_56, joihin osallistuu numeroituvasti ääretön määrä reaalilukujoukkoja, on sama kardinaaliluku kuin reaaliluvuilla. 
Joukon osajoukkojen joukko formula_57.
Cantorin lauseessa, jonka hän julkaisi vuonna 1891, hän väittää, että joukon osajoukkojen joukko on mahtavampi kuin joukko itse. Tämä siksi, ettei ole olemassa bijektiota joukosta formula_58 potenssijoukkoon formula_57. Tämä tarkoittaa, että potenssijoukon mahtavauus ylittää selvästi oman joukon formula_58 mahtavuuden. 
Äärettömästi numeroituvan joukon osajoukkojen joukko on yhtä mahtava kuin formula_33. Ylinumeroituva joukko on kaikkien luonnollisten lukujen joukon osajoukkojen joukko eli luonnollisten lukujen joukon potenssijoukko formula_62. Sen kardinaaliluku on formula_63.
Mikäli reaaliluvuista muodostaa potenssijoukon formula_64, tulee sen mahtavuudesta vielä suurempi. Sen kardinaaliluku merkitään formula_65.
Potenssijoukkoja voidaan muodostaa edellisestä potenssijoukosta loputtomasti. Näiden kardinaaliluvut kasvavat formula_66. 
Ylinumeroituvan joukon funktiot.
Funktioiden formula_67 joukko on ylinumeroituva. Tämän joukon kardinaaliluku on vielä reaalilukujenkin kardinaliteettia suurempi. Funktioita voidaan muodostaa kaikille reaalilukujen osajoukoille, mikä johtaa potenssijoukkojen mahtavuuteen. Funktioiden joukon mahtavuutta merkitään siksi formula_68.