Numeroituva joukko

Joukon ${\displaystyle \mathrm {S} }$ mahtavuutta merkitään matematiikan kirjallisuudessa joko ${\displaystyle \operatorname {card} (S)}$ tai ${\displaystyle |S|}$. Joukkojen mahtavuuden suuruus ilmaistaan heprean kielen aakkosella ${\displaystyle \aleph }$, joka lausutaan "alef". Numeroituvan joukon ${\displaystyle \mathrm {S} }$, kuten myös luonnollisten lukujen joukon ${\displaystyle \mathbb {N} }$, mahtavuutta merkitään kardinaaliluvulla ${\displaystyle \operatorname {card} (\mathrm {S} )=\operatorname {card} (\mathbb {N} )=\aleph _{0}}$. Tämän arvo on ${\displaystyle \aleph _{0}=\infty }$ ja se on pienin ääretön kardinaaliluku.[3]

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

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

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

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

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]

Kokonaisluvut ${\displaystyle \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ä:

${\displaystyle 0,1,-1,2,-2,3,-3,4,-4,...}$

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

${\displaystyle 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 (${\displaystyle n\in \mathbb {N} }$) kokonaisluvuille seuraavasti:

${\displaystyle {\frac {(-1)^{n}\cdot n}{2}}+{\frac {1-(-1)^{n}}{4}}\iff {\begin{cases}{\frac {1-n}{2}},&kun\ n\ pariton\\{\frac {n}{2}},&kun\ n\ 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 ${\displaystyle \aleph _{0}}$.

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

${\displaystyle \mathbb {Z} =\{...,-3,-2,-1\}\cup \{0\}\cup \{1,2,3,...\}}$ [1]

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \mathbb {N} }$ on itsestään selvästi numeroituva ja ${\displaystyle \mathbb {N} \times \mathbb {N} }$ on numeroituva, koska on olemassa bijektio ${\displaystyle f:\mathbb {N} \times \mathbb {N} \to \mathbb {N} }$, kun ${\displaystyle f}$ on esimerkiksi ${\displaystyle f(k,n)=2^{k-1}\cdot (2n-1)}$.

${\displaystyle \overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m\in \mathbb {N} }}$ on numeroituva ${\displaystyle \iff }$ on olemassa bijektio ${\displaystyle g:\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m}\to \mathbb {N} }$.

Olkoon kuvaus ${\displaystyle h:\overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m+1}\to \mathbb {N} }$ määritelty siten, että ${\displaystyle h(k_{1},k_{2},...,k_{m},k_{m+1})=f(\overbrace {g(k_{1},k_{2},...,k_{m})} ^{=l},k_{m+1})}$ ${\displaystyle =2^{l-1}\cdot (2k_{m+1}-1)}$. Koska ${\displaystyle f}$ on bijektio ja koska ${\displaystyle g}$ on induktio-oletuksen nojalla bijektio, niin ${\displaystyle h}$:n on myös oltava bijektio. Tällöin karteesinen tulo ${\displaystyle \overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{m+1}}$ numeroituu.

${\displaystyle \mathbb {N} \times \mathbb {N} }$ on numeroituva. Induktioaskeleessa todistettiin, että ${\displaystyle \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 ${\displaystyle \overbrace {\mathbb {N} \times \mathbb {N} \times ...\times \mathbb {N} } ^{n\in \mathbb {N} }}$ on numeroituva kaikilla ${\displaystyle n\in \mathbb {N} }$.