Numeroituvat joukot

Joukon numeroituvuus on eräänlainen vastine joukon koolle, sillä äärettömien joukkojen kohdalla ei voi laskea alkioiden lukumäärää, koska alkioiden lukumäärä on yllättäen … ääretön. Joukon kokoa kutsutaan myös mahtavuudeksi eli kardinaliteetiksi.

Äärettömän joukon koko

Äärellisen joukon koon määrittäminen on helppoa, lasketaan alkioiden lukumäärä. Joukon M = {a, b, c, d, e} koko on siis 5, ja merkitsemme |M| = 5.

Äärettömillä joukoilla tilanne on huomattavasti monimutkaisempi. Miten voisimme vertailla äärettömien joukkojen kokoa? Onko se ylipäätään mahdollista, vai ovatko kaikki äärettömät joukot ”yhtä suuria”?

Otetaan esimerkiksi positiivisten kokonaislukujen joukko ja parillisten positiivisten kokonaislukujen joukko. Meillä on siis joukot ℤ⁺ = {1, 2, 3, 4, 5, 6, …} ja S = {2, 4, 6, …}. Tekisi mieli sanoa, että positiivisten kokonaislukujen joukko on suurempi kuin parillisten lukujen joukko, koska positiivisiin kokonaislukuihin sisältyvät kaikki parilliset luvut ja lisäksi vielä muita alkioita – parittomat luvut.

Voisimme siis kirjoittaa, että S ⊂ ℤ⁺, eli joukko S on joukon ℤ⁺ aito osajoukko. Ja voisimme sanoa, että jos S ⊂ ℤ⁺, joukko ℤ⁺ on suurempi – siinä on kuitenkin enemmän alkioita kuin joukossa S.

Yksi syy siihen, miksi joukkoja ei voi mitata osajoukkorelaation avulla, on se, että joukoilla voi olla eri koko, vaikka kumpikaan joukko ei ole toisen osajoukko. Sen voi osoittaa jo äärellisillä joukoilla: A = {1, 3, 4, 9} ja B = {b, u, r, z, m}. Pätee |A| = 4 ja |B| = 5. Joukko B on suurempi kuin joukko A, mutta silti ei päde A ⊂ B. Äärettömillä joukoilla sen näkee parillisista ja parittomista luvuista. Kumpikaan joukko ei ole toisen osajoukko.

Osajoukkorelaatio ei siis ole paras mahdollinen väline ratkaista, onko yksi joukko suurempi kuin toinen.

Bijektio

Kokeillaan toista lähestymistapaa. Meillä on kaksi joukkoa, A ja B. Voimme sanoa, että niillä on sama koko, jos niiden välillä on bijektiivinen kuvaus. Mitä se tarkoittaa? Otamme joukosta A alkion ja joukosta B alkion ja muodostamme parin (a, b). Nämä alkiot poistetaan joukoista, ja jatkamme. Jos pystymme ”tyhjentämään” molemmat joukot, olemme löytäneet bijektiivisen kuvauksen.

Esimerkki äärellisillä joukoilla: A = {a, b, c} ja B = {1, 2, 3}. Ensimmäinen pari voisi olla (a, 1), seuraava (b, 2) ja lopuksi (c, 3). Käytimme kaikki molempien joukkojen alkiot, joten löysimme bijektiivisen kuvauksen. On tärkeää, että tämä ei ole ainoa bijektiivinen kuvaus. Myös tämä on kelvollinen ratkaisu: (a, 3), (b, 1), (c, 2).

Äärettömillä joukoilla asia on jo hieman mielenkiintoisempi. Kokeillaan parittomia ja parillisia positiivisia kokonaislukuja. Vaistomaisesti tuntuu, että niitä pitäisi olla yhtä paljon. Kokeillaan. Otetaan ensimmäinen pariton luku ja kuvataan se ensimmäiselle parilliselle luvulle: (1, 2). Sitten toinen pariton ja toinen parillinen: (3, 4). Ja niin edelleen. Saamme parit: (1, 2), (3, 4), (5, 6), (7, 8), … Voisimme kirjoittaa, että jokainen pariton luku l kuvautuu parilliselle luvulle l + 1 ja jokainen parillinen luku s on parittoman luvun s − 1 kuva. Jokaiselle parittomalle ja jokaiselle parilliselle luvulle on siis olemassa pari, jossa kyseinen luku on mukana. Parittomien ja parillisten lukujen joukot ovat siis yhtä suuret.

Parilliset luvut ja positiiviset kokonaisluvut

Kokeillaan nyt samaa menetelmää ja vertaillaan positiivisten kokonaislukujen ja parillisten lukujen joukkoja. Meillä on joukot ℤ⁺ = {1, 2, 3, 4, 5, 6, …} ja S = {2, 4, 6, …}. Vaistomaisesti odotamme, että positiivisten kokonaislukujen joukko on suurempi.

Yritetään kuitenkin löytää bijektiivinen kuvaus. Voimme sanoa, että jokainen positiivinen kokonaisluku n kuvautuu omalle kaksinkertaiselleen eli luvulle 2n. Näin saamme parit (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Jokaiselle positiiviselle kokonaisluvulle n on siis pari (n, 2n) ja jokaiselle parilliselle luvulle s on pari (s/2, s). Löysimme bijektiivisen kuvauksen, joten parillisten lukujen joukko ja positiivisten kokonaislukujen joukko ovat yhtä suuret, niillä on sama kardinaliteetti.

Tämä voi tuntua hämmentävältä, koska positiivisissa kokonaisluvuissa on kuitenkin enemmän alkioita kuin parillisissa luvuissa. Positiivisiin kokonaislukuihin sisältyvät kaikki parilliset luvut ja lisäksi kaikki parittomat luvut. Löydämme kuitenkin bijektion, joten molemmat joukot ovat yhtä suuret.

Vertailu positiivisiin kokonaislukuihin

Positiiviset kokonaisluvut määrittävät itse asiassa äärettömän joukon pienimmän koon. Sen, onko jollakin toisella joukolla sama koko kuin positiivisten kokonaislukujen joukolla, voi usein selvittää melko helposti – riittää löytää bijektio positiivisille kokonaisluvuille, mikä käytännössä tarkoittaa, että riittää pystyä numeroimaan eli järjestämään joukkomme M alkiot.

Jos siis pystymme järjestämään joukon alkiot niin, että voimme päättää, mikä alkio on ensimmäinen, mikä toinen, kolmas, neljäs, kymmenes jne., joukko on yhtä suuri kuin ℤ⁺. Tällaista joukkoa sanotaan numeroituvaksi.

Helposti nähdään, että parilliset ja parittomat positiiviset kokonaisluvut ovat numeroituvia, koska osaamme määrittää ensimmäisen, toisen, kolmannen jne. parillisen tai parittoman luvun. Entä parilliset kokonaisluvut? Eli joukko S = {…, −4, −2, 0, 2, 4, …}. Pystymmekö järjestämään ne? Pystymme: otetaan sama järjestys kuin äsken ja kirjoitetaan heti positiivisen parillisen luvun jälkeen sen vastaluku: S = {0, 2, −2, 4, −4, 6, −6, …}. Samalla tavalla esimerkiksi kokonaisluvuille.

Rationaalilukujen joukon koko

Mielenkiintoisempi esimerkki ovat rationaaliluvut eli murtoluvut. Pystymmekö järjestämään ne? Pystymme, mutta se on jo hieman monimutkaisempaa. Muodostamme taulukon, jossa on äärettömän monta riviä ja saraketta. Jokaisessa solussa on murtoluku. n:nnessä sarakkeessa ja m:nnessä rivissä on murtoluku n/m. Siis 1. sarakkeessa ja 2. rivissä on $\frac{1}{2}$ ja kolmannessa sarakkeessa ja neljännessä rivissä on 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Miten nämä luvut nyt järjestetään, numeroidaan? Emme voi numeroida niitä rivi riviltä tai sarake sarakkeelta, koska hukkuisimme heti kyseiseen riviin tai sarakkeeseen. Sen sijaan otamme luvut lävistäjä kerrallaan: (ensimmäinen lävistäjä:) 1/1, (toinen lävistäjä:) 2/1, 1/2, (kolmas lävistäjä:) 3/1, 2/2, 1/3, (neljäs lävistäjä:) 4/1, 3/2, 2/3, 1/4, … Mukana on vielä paljon samoja murtolukuja useaan kertaan, mutta se ei haittaa. Enemmän haittaa, että negatiivisia lukuja ei ole mukana. Sen voi ratkaista helposti: aina kun kirjoitamme jonkin murtoluvun, sijoitamme heti sen perään sen vastaluvun. Ja sitten aivan alusta puuttuu vielä nolla. Siinä kaikki, meillä on kaikki rationaaliluvut jonossa.

Kokonaisuudessaan saamme jonon: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Reaalilukujen joukon koko

Ovatko reaaliluvut yhtä suuri joukko kuin positiiviset kokonaisluvut? Ratkaiseminen on vielä hankalampaa kuin rationaalilukujen tapauksessa. Teemme ristiriitatodistuksen. Oletetaan, että reaaliluvut ovat numeroituvia ja että on olemassa bijektiivinen kuvaus positiivisille kokonaisluvuille. Oletetaan siis, että ne voidaan järjestää. Ja oletetaan, että seuraava taulukko on tuo järjestys:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Taulukossa on järjestyksemme seitsemän ensimmäistä reaalilukua. Järjestys voi tietysti olla mikä tahansa, lukujen ei tarvitse olla suuruusjärjestyksessä.

Oletuksen mukaan tässä äärettömässä taulukossa on järjestettynä kaikki reaaliluvut. (Taulukko on jälleen ääretön, tässä on vain seitsemän ensimmäistä riviä.) Yritämme nyt löytää eli rakentaa luvun, joka on reaaliluku mutta jota ei ole tässä taulukossa. Jos sellaisen luvun löydämme, se on ristiriidassa sen kanssa, että taulukossa on kaikki reaaliluvut, mistä voimme päätellä, ettei reaalilukujen joukko ole numeroituva.

Luvun, jota taulukossa ei ole, rakennamme näin:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Aloitamme kirjoittamalla 0,… Tältä uusi reaalilukumme näyttää alussa. Ensimmäiseksi desimaaliksi tulee numero, joka ei ole järjestyksemme ensimmäisen reaaliluvun ensimmäisenä desimaalina (taulukossa se on korostettu kehyksellä). Siinä on numero 3, joten valitsemme vaikkapa 1, ja saamme luvun 0,1…

Jatketaan. Toiseksi desimaaliksi tulee numero, joka ei ole toisen reaaliluvun toisena desimaalina. Siinä on 9, joten vaikkapa 2. Saamme luvun 0,12… Kolmanneksi desimaaliksi tulee numero, joka eroaa kolmannen reaaliluvun kolmannesta numerosta. Siinä on 3, joten valitsemme vaikkapa 7. Saamme 0,127…

Ja niin edelleen. Uuden luvun n:nnellä paikalla on aina numero, joka eroaa järjestyksemme n:nnen luvun n:nnellä paikalla olevasta numerosta.

Mitä tästä saamme? Saamme luvun, joka eroaa jokaisesta järjestyksemme luvusta vähintään yhdessä numerossa. Otetaan viimeisin väliaikainen tulos: 0,127… Tämä luku eroaa varmasti järjestyksemme ensimmäisestä luvusta vähintään ensimmäisessä numerossa – koska rakensimme sen niin. Toisesta luvusta se eroaa vähintään toisessa numerossa. Kolmannesta kolmannessa numerossa. Yleisesti tämä uusi luku eroaa järjestyksen n:nnellä paikalla olevasta luvusta vähintään n:nnellä paikalla olevassa numerossa.

Tätä vastarakennettua lukua emme siis löydä taulukosta, jonka piti kuvata bijektiota positiivisten kokonaislukujen ja reaalilukujen välillä. Reaaliluvut ovat siis suurempi joukko kuin positiiviset kokonaisluvut. Reaaliluvut eivät ole numeroituvia, ne ovat ylinumeroituvia.