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 $\mathbb {N} =\{1,2,3,...\}$, 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 $\mathrm {S}$ 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 $\mathrm {S}$ mahtavuutta merkitään matematiikan kirjallisuudessa joko $\operatorname {card} (S)$ tai $|S|$. Joukkojen mahtavuuden suuruus ilmaistaan heprean kielen aakkosilla $\aleph$ tai $\beth$, joka lausutaan "alef" ja '"beth". Numeroituvan joukon $\mathrm {S}$, kuten myös luonnollisten lukujen joukon $\mathbb {N}$, mahtavuutta merkitään kardinaaliluvulla $\operatorname {card} (\mathrm {S} )=\operatorname {card} (\mathbb {N} )=\aleph _{0}$. Tämän arvo on $\aleph _{0}=\infty$ ja se on pienin ääretön kardinaaliluku.

Jos joukko on ylinumeroituva, joukon mahtavuus ilmaistaan kardinaaliluvuilla $\aleph _{1}$, $\aleph _{2}$, ..., missä kaikki kardinaaliluvut ovat $\aleph _{i}=\infty$, ylinumeroituvuuden laadun mukaan. Kardinaaliluvuilla on suuruusjärjestys $\aleph _{0}<\aleph _{1}<\aleph _{2}<....$

Cantorin ajatus oli, että mahtavuudeltaan pienimmällä ylinumeroituvalla joukolla olisi kardinaaliluku $\aleph _{1}$. Kun hän osoitti reaaliluvut ylinumeroituvaksi joukoksi, hän oletti aluksi, että reaalilukujen kardinaaliluku olisi $\aleph _{1}$. Tätä ei voitu osoittaa todeksi, joten varmuuden vuoksi kardinaaliluvuksi on otettu $\beth _{1}$, joka on $\aleph _{1}\leq \beth _{1}$ .

Ylinumeroituvuuden toteaminen funktion kuvauksesta

Joukko $\mathrm {S}$ on ylinumeroituva, jos ja vain jos on olemassa jokin surjektiivinen kuvaus $f$ joukolta $\mathrm {S}$ luonnollisille luvuille $\mathbb {N}$,

$f\colon \mathrm {S} \to \mathbb {N}$

joka ei ole injektio. Joukko $\mathrm {S}$ on numeroituva, jos ja vain jos kuvaus $f$ on bijektio.

Yleisiä tuloksia

Jos joukon $\mathrm {S}$ osajoukko $\mathrm {S'}$ on ylinumeroituva, niin myös joukko $\mathrm {S}$ on ylinumeroituva.

Jos joukko $\mathrm {S}$ on ylinumeroituva ja

$f\colon \mathrm {S} \to \mathrm {T}$

on bijektio, niin silloin myös $\mathrm {T}$ on ylinumeroituva.

Esimerkkejä ylinumeroituvasti äärettömistä joukoista

Reaaliluvut

Ensimmäisen todistelun reaalilukujen $\mathbb {R}$ 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 $\left(0,1\right)$ 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 $\left(0,1\right)$ on ylinumeroituvasti ääretön. Koko reaalilukujen joukko on ylinumeroituva, koska sen osajoukko $\left(0,1\right)$ on ylinumeroituva. Reaaliluvut ovat ylinumeroituva joukko myös siksi, että voidaan myös määrittää bijektio

$f\colon \left(0,1\right)\to \mathbb {R} ,$

missä bijektiona on esimerkiksi $f(x)=\tan \left(\pi x-{\frac {\pi }{2}}\right).$

Reaalilukujen mahtavuuden määrittäminen on ollut ongelmallista niin sanotun kontinuumihypoteesin epämääräisyyden vuoksi. Siksi reaalilukujen kardinaaliluvuksi on merkitty $\beth _{1}$, joka on suurempi tai yhtäsuuri kuin pienimmän ylinumeroituvan joukon kardinaaliluku $\aleph _{1}.$. 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 $\aleph _{0}$:n avulla $\beth _{1}=2^{\aleph _{0}}.$

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 $\mathrm {A}$ algebralliset luvut ja $\mathrm {T}$ transkendenttiluvut, jolloin $\mathbb {R} =\mathrm {A} \cup \mathrm {T}$. Koska $\mathrm {A}$ on numeroituva joukko, niin $\mathbb {R}$ tulisi olla numeroituva joukko, jos $\mathrm {T}$ on numeroituva. Koska $\mathbb {R}$ on kuitenkin ylinumeroituva, täytyy $\mathrm {T}$ olla myös ylinumeroituva.

Reaalilukujoukkojen karteesinen tulo

Karteesinen tulo $\mathbb {R} \times \mathbb {R}$ 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

$f\colon \left(0,1\right)\to \left(0,1\right)\times \left(0,1\right),$

jolloin kuvauksen lähtö- ja maalijoukolla on sama kardinaaliluku. Aiemmin todettiin, että joukolla $\left(0,1\right)$ on sama kardinaaliluku kuin reaalijoukolla. Samasta syystä myös joukolla $\left(0,1\right)\times \left(0,1\right)$ on sama kardinaaliluku kuin $\mathbb {R} \times \mathbb {R}$, koska se on jälkimmäisen osajoukko.

Kaikilla karteesisilla tuloilla $\mathbb {R} \times \mathbb {R} \times ...\times \mathbb {R}$, joihin osallistuu numeroituvasti ääretön määrä reaalilukujoukkoja, on sama kardinaaliluku kuin reaaliluvuilla.

Joukon osajoukkojen joukko ${\mathcal {P}}(\mathbb {S} )$

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 $S$ potenssijoukkoon ${\mathcal {P}}(\mathbb {S} )$. Tämä tarkoittaa, että potenssijoukon mahtavauus ylittää selvästi oman joukon $S$ mahtavuuden.

Äärettömästi numeroituvan joukon osajoukkojen joukko on yhtä mahtava kuin $\mathbb {R}$. Ylinumeroituva joukko on kaikkien luonnollisten lukujen joukon osajoukkojen joukko eli luonnollisten lukujen joukon potenssijoukko ${\mathcal {P}}(\mathbb {N} )$. Sen kardinaaliluku on $\operatorname {card} ({\mathcal {P}}(\mathbb {N} ))=\operatorname {card} (\mathbb {R} )=\beth _{1}$.

Mikäli reaaliluvuista muodostaa potenssijoukon ${\mathcal {P}}(\mathbb {\mathbb {R} } )$, tulee sen mahtavuudesta vielä suurempi. Sen kardinaaliluku merkitään $\operatorname {card} ({\mathcal {P}}(\mathbb {R} ))=\beth _{2}$.

Potenssijoukkoja voidaan muodostaa edellisestä potenssijoukosta loputtomasti. Näiden kardinaaliluvut kasvavat $\beth _{1}<\beth _{2}<\beth _{3}<...$.

Ylinumeroituvan joukon funktiot

Funktioiden $f:\mathbb {R} \rightarrow \mathbb {R}$ 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 $\beth _{2}$.

Lähteet

• Fuchs, Walter R.: Matematiikka. Suomentanut Mattila, Pekka. Länsi-Saksa: Kirjayhtymä, 1968.
• Barrow, John D.: Lukujen taivas. Suomentanut Vilikko, Risto. Smedjebacken, Ruotsi: Art House, 1999. ISBN 951-884-231-0.

Kirjallisuutta

• Lipschutz, Seymour: Set Theory and Related Topics. McGraw-Hill, 1964. ISBN 0-07-037986-6.