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

\left\{(1,2),(2,4),(3,6),(4,8),...,(n,2n),...\right\}.

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.^[1]

Määritelmä

Joukko $\mathrm {S}$ on numeroituva kahdessa tapauksessa. $\mathrm {S}$ 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. $\mathrm {S}$ on numeroituvasti ääretön, jos se on yhtä mahtava kuin luonnollisten lukujen $\mathbb {N} =\{1,2,3,...\}$ joukko. Parinmuodostus vertailujoukon $\mathbb {N}$ kanssa jatkuu äärettömän monta kertaa tai jää kesken, mutta jokaiselle joukon $\mathrm {S}$ alkiolle riittää joukosta $\mathbb {N}$ pari.

Jos parinmuodostusprosessissa huomataan tilanne, että joukossa $\mathrm {S}$ on alkioita, joita ei pystytä luetteloimaan joukon $\mathbb {N}$ alkioilla, kutsutaan joukkoa $\mathrm {S}$ ylinumeroituvaksi. Intuitiivisesti ajatellaan, että joukossa $\mathrm {S}$ on "enemmän alkioita" kuin joukossa $\mathbb {N}$ eli se on mahtavampi joukko. Esimerkiksi reaalilukujen joukko $\mathbb {R}$ on osoitettu mahtavammaksi kuin $\mathbb {N}$ eli se on ylinumeroituvasti ääretön.^[2]

Merkintä

Joukon $\mathrm {S}$ mahtavuutta merkitään matematiikan kirjallisuudessa joko $\operatorname {card} (S)$ tai $|S|$ . Joukkojen mahtavuuden suuruus ilmaistaan heprean kielen aakkosella $\aleph$ , joka lausutaan "alef". 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.^[3]

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

Numeroituvuuden määritys funktion kuvauksena

Vertailuparien muodostus voidaan tulkita karteesisen tulon $\mathrm {S} \times \mathbb {N}$ muodostamiseksi, mikä voidaan lausua myös funktion kuvauksen avulla. Silloin kuvaus tutkittavasta lukujoukosta luonnollisten lukujen joukkoon

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

vastaisi parinmuodostusta siten, että kuvauksen $f$ lähtö- ja maalijoukon alkiot ovat pareja. Jos kuvaus $f$ on injektio, on lähtöjoukko numeroituva tai numeroituvasti ääretön. Jos kuvaus on peräti bijektio, on lähtöjoukko $\mathrm {S}$ numeroituvasti ääretön.^[5] Bijektion olemassaolo voidaan todeta myös, kun kahden joukon välille löydetään kaksi injektiota $f$ ja $g$ siten, että $f:A\to B$ ja $g:B\to A$ . Tällöin Cantorin–Schröderin–Bernsteinin lauseen nojalla on olemassa bijektio $h:A\to B$ .

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.^[5]

Esimerkkejä numeroituvista äärettömistä joukoista

Edellisen esimerkin mukaisesti parilliset positiiviset luvut ovat numeroituvasti ääretön joukko. Samoin ovat esimerkiksi kokonaislukujen ( $\mathbb {Z}$ ), algebrallisten lukujen ja rationaalilukujen joukot ( $\mathbb {Q}$ ) numeroituvia.^[1]. Sitä vastoin esimerkiksi reaalilukujen joukko $\mathbb {R}$ ei ole numeroituva vaan ylinumeroituva eli aidosti mahtavampi kuin mikään edellä mainituista.

Todistus kokonaislukujen osalta

Kokonaisluvut $\mathbb {Z} =\{...,-3,-2,-1,0,1,2,3,...\}$ 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ä:

0,1,-1,2,-2,3,-3,4,-4,...

Nämä uudelleen ryhmitellyt luvut numeroidaan luonnollisilla luvuilla seuraavasti:

0\leftrightarrow 1,-1\leftrightarrow 2,2\leftrightarrow 3,-2\leftrightarrow 4,3\leftrightarrow 5,-3\leftrightarrow 6,...

, mikä voidaan myös esittää bijektiona luonnollisilta luvuilta (

n\in \mathbb {N}

) kokonaisluvuille seuraavasti:

${\frac {(-1)^{n}\cdot n}{2}}+{\frac {1-(-1)^{n}}{4}}\iff {\begin{cases}{\frac {1-n}{2}},\quad &{\text{kun}}\ n\ {\text{pariton}}\\{\frac {n}{2}},&{\text{kun}}\ n\ {\text{parillinen}}.\end{cases}}$

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 $\aleph _{0}$ .

Kokonaislukujen joukko on numeroituvasti ääretön myös siksi, että se on unioni kolmesta numeroituvasta joukosta:

\mathbb {Z} =\{...,-3,-2,-1\}\cup \{0\}\cup \{1,2,3,...\}

^[1]

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 $A_{k}$ , jonka alkioilla on nimittäjänä kokonaisluku $k$ :

A_{k}=\{...,{\frac {-2}{k}},{\frac {-1}{k}},{\frac {0}{k}},{\frac {1}{k}},{\frac {2}{k}},...\}.

Joukko $A_{k}$ on $k$ :n arvosta riippumatta numeroituvasti ääretön, koska alkioita on yhtä monta kuin murtolukujen osoittajissa olevat kokonaisluvut.

Kaikki rationaaliluvut $\mathbb {Q}$ saadaan osajoukkojen $A_{k}$ unionina, kun $k$ käy läpi kaikki kokonaisluvut $\mathbb {Z}$

\mathbb {Q} =\bigcup _{k\in \mathbb {Z} }A_{k},

missä osajoukkoja on numeroituvasti ääretön joukko.^[1]

Numeroituvien joukkojen karteesiset tulot

Rationaalukujen todistelu on samantapainen myös kahden numeroituvan joukon karteesisen tulon numeroituvuuden todistelussa. Esimerkiksi kahden luonnollisen joukon karteesinen tulo $\mathbb {N} \times \mathbb {N}$ on siten myös numeroituva joukko. Itse asiassa kaikki numeroituvien joukkojen kaikki karteesiset tulot $\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N}$ ovat numeroituvia joukkoja.

Keksimällä bijektio $f\colon \mathbb {N} \times \mathbb {N} \rightarrow \mathbb {N}$ , missä

f(k,n)=2^{k-1}\cdot (2n-1)

on numeroituvuus toteamisen jälkeen osoitettu.^[1]^[6]

Toinen tapa on havaita injektiot $f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ , jossa $f(n,k)=3^{n}5^{k}$ , ja $g:\mathbb {N} \to \mathbb {N} \times \mathbb {N}$ , jossa $g(m)=(m,m)$ . Näin ollen Cantorin–Schröderin–Bernsteinin lauseen nojalla on olemassa bijektio $h:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ , joten karteesinen $\mathbb {N} \times \mathbb {N}$ tulo numeroituu.

Todistetaan induktiolla, että karteesinen tulo $\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{n\in \mathbb {N} }$ on numeroituva kaikilla $n\in \mathbb {N}$ :

Alkuaskel

\mathbb {N}

on itsestään selvästi numeroituva ja

\mathbb {N} \times \mathbb {N}

on numeroituva, koska on olemassa bijektio

f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}

, kun

f

on esimerkiksi

f(k,n)=2^{k-1}\cdot (2n-1)

.

Induktio-oletus

\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m\in \mathbb {N} }

on numeroituva

\iff

on olemassa bijektio

g:\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m}\to \mathbb {N}

.

Induktioaskel

Olkoon kuvaus

h:\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m+1}\to \mathbb {N}

määritelty siten, että

h(k_{1},k_{2},...,k_{m},k_{m+1})=f(\overbrace {g(k_{1},k_{2},...,k_{m})} ^{=l},k_{m+1})

=2^{l-1}\cdot (2k_{m+1}-1)

. Koska

f

on bijektio ja koska

g

on induktio-oletuksen nojalla bijektio, niin

h

:n on myös oltava bijektio. Tällöin karteesinen tulo

\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m+1}

numeroituu.

$\mathbb {N} \times \mathbb {N}$ on numeroituva. Induktioaskeleessa todistettiin, että $\mathbb {N} \times \mathbb {N} \times \mathbb {N}$ ja jokainen sitä seuraavakin luonnollisten lukujen joukolla konstruoitu karteesinen tulo on numeroituva. Näin ollen on siis osoitettu induktiolla, että karteesinen tulo $\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{n\in \mathbb {N} }$ on numeroituva kaikilla $n\in \mathbb {N}$ .

Katso myös

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

Viitteet

↑ ^a ^b ^c ^d ^e Williams, Michael B.: Cardinality (pdf) (luentomoniste) Texas, USA: University of Texas at Austin. (englanniksi)
↑ Weisstein, Eric W.: Countably Infinite (Math World – A Wolfram Web Resource) Wolfram Research. (englanniksi)
↑ Weisstein, Eric W.: Aleph-0 (Math World – A Wolfram Web Resource) Wolfram Research. (englanniksi)
↑ Weisstein, Eric W.: Aleph-1 (Math World – A Wolfram Web Resource) Wolfram Research. (englanniksi)
↑ ^a ^b Schwartz, Rich: Countable and Uncountable Sets (pdf) (luentomoniste) 2007. Providence: Brown University. (englanniksi)
↑ Jech, Thomas: Basic Set Teory (html) (luentomoniste) California, USA: Stanford University. (englanniksi)

Kirjallisuutta

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

[austin-1] Williams, Michael B.: Cardinality (pdf) (luentomoniste) Texas, USA: University of Texas at Austin. (englanniksi)

[ww1-2] Weisstein, Eric W.: Countably Infinite (Math World – A Wolfram Web Resource) Wolfram Research. (englanniksi)

[ww2-3] Weisstein, Eric W.: Aleph-0 (Math World – A Wolfram Web Resource) Wolfram Research. (englanniksi)

[ww3-4] Weisstein, Eric W.: Aleph-1 (Math World – A Wolfram Web Resource) Wolfram Research. (englanniksi)

[brown-5] Schwartz, Rich: Countable and Uncountable Sets (pdf) (luentomoniste) 2007. Providence: Brown University. (englanniksi)

[stanford-6] Jech, Thomas: Basic Set Teory (html) (luentomoniste) California, USA: Stanford University. (englanniksi)

[1]

[2]

[3]

[4]

[5]

[6]