Tehtävä:
Rationaalilukujen joukko on nollamitallinen

Lyhyt MathCheck-ohje (uuteen välilehteen)

Tässä tehtävässä todistetaan kahdessa vaiheessa asia, joka on hyvin järjenvastainen, mutta silti totta. Saatava tulos selittää varsin pitkälle, miksi tietokoneet pärjäävät kokonaislukujen kanssa paljon paremmin kuin reaali­lukujen kanssa.

Rationaalilukujen joukko on numeroituva

Tarkastelemme funktiota

`f(m,n) = ((m+n)(m+n-1))/2 - m + 1`

missä ` m in ZZ^+` ja `n in ZZ^+`. Tavoitteemme on ensin saada siihen tuntumaa ja sitten osoittaa, että se saa peräkkäiset arvot siten kuin alla havainnollistetaan:

47
348
2259
113610
12 34

Laske `f(1,1)`. Kyllähän sinä näet heti yltä mitä siitä pitäisi tulla, mutta laske se silti `f`:n määritelmästä. Se on helppo päässälasku.
tai

Valitse oikea. Voit vaikka laskea päässäsi `f(2,1)` ja `f(1,2)`, niin vastauksen pitäisi selvitä.
`m` kasvaa oikealle ja `n` ylös.
`m` kasvaa ylös ja `n` oikealle.
tai

Sievennä `f(1,n)`.
tai

Sievennä `f(m,1)`.
tai

Kun edetään vinottain oikealle alas, niin mikä tulee kohdan `(m,n)` jälkeen seuraavana?
( , ) tai

Kuvan mukaan `f(m,n)`:n arvo kasvaa yhdellä kun edetään yksi askel oikealle alas, mutta ollaksemme varmoja päättelemme määritelmästä, että näin todella on. Ilmaise `m`:n ja `n`:n (tai toisen tai ei kummankaan) funktiona, miten seuraavien lausekkeiden arvot muuttuvat, kun edetään yksi askel oikealle alas. Esim. jos arvelet, että arvo pienenee `(n+3)`:n verran, kirjoita -(n+3).
`m+n`
`m+n-1`
`((m+n)(m+n-1))/2`
`-m+1`
`f(m,n)`
tai

Kun on päästy alimmalle riville, jatketaan seuraavan vinosti alas vievän linjan alkuun. Siis kohdasta `(1,n)` jatketaan kohtaan ( , ).
tai

Tässäkin askeleessa `f`:n arvon pitää kasvaa yhdellä. On siis osoitettava, että `f(`uusi kohta`) - f(1,n) = 1`. Muis­tut­taakohan jompi kumpi tai molemmat kahdesta ylim­mästä jotakin, johon olet vastannut jo aikaisemmin?
`= f`(uusi kohta)
`= f(1,n)`
`= f(`uusi kohta`) - f(1,n)`
tai

Toivottavasti olen saanut sinut vakuuttuneeksi, että kaikki parit `(m,n)`, missä `m in ZZ^+` ja `n in ZZ^+`, saadaan jonoon joka alkaa mutta ei pääty. Jokainen pari on jonossa täsmälleen kerran.

Itse asiassa jo alun kuva on riittävä todistus tälle, mutta asia tuntuu jotenkin vakuuttavammalta, kun mukaan sotketaan lausekkeita ☺. Sitäpaitsi `f`:n lausekkeen rakentamis­tapa on hyödyllinen muissa yhteyksissä, esimerkiksi kun halutaan tallettaa kaupunkien välisten etäisyyksien taulukko siten, että kukin etäisyys talle­tetaan vain yhteen suuntaan.

Tässä vaiheessa on hyvä täsmentää, mitä matemaatikko tarkoittaa, kun hän puhuu päättymättömästä jonosta. Päättymätömän jonon paikat voidaan numeroida posi­tiivisilla kokonais­luvuilla: paikka 1, paikka 2, paikka 3, …. Sellaisella luettelolla on alku muttei loppua. Jokaisen alkion perässä (siis oikealla puolella) on äärettömästi alkioita, mutta minkään alkion edessä (eli vasemmalla puolella) ei ole äärettömästi alkioita. Juuri sellaisen luettelon teimme äsken. Siinä alkion `(m,n)` paikka on `f(m,n)`, ja varmistimme huolellisesti, että eri alkiot saivat eri paikat.

Mitkä seuraavista ovat päättymättömiä jonoja? Mieti ja sitten kokeile jokainen, myös ”ei”-tapaukset, olitko oikeilla jäljillä.
0, 1, 2, 3
…, −2, −1, 0, 1, 2, …
0, −1, 1, −2, 2, …
1, 2, 3, …, 0
0, 1, 2, …, −1, −2, −3, …
0, 0, 0, 0, 0, …
tai

Joukon sanotaan olevan numeroituva, jos ja vain jos sen alkiot voidaan asettaa päättyvään tai päättymättömään jonoon. Muut joukot ovat ylinumeroituvia.

Rationaaliluku on luku, joka voidaan esittää murtolukuna eli muodossa `m/n`, missä `m in ZZ` ja `n in ZZ^+`. Myös kokonaisluvut ovat rationaalilukuja, koska `m = m/1` (siis esim. `5 = 5/1`). Jokaisella rationaaliluvulla on äärettömän monta esitystä murtolukuna, koska `m/n``=``(2m)/(2n)``=``(3m)/(3n)``=``...`.

Valitse oikeat vaihtoehdot.
`f(m,n)` laittaa kaikki rationaaliluvut jonoon siten, että jokainen esiintyy täsmälleen kerran.
`f(m,n)` laittaa kaikki rationaaliluvut jonoon siten, että jokainen esiintyy ainakin kerran.
`f(m,n)` laittaa kaikki positiiviset rationaaliluvut jonoon siten, että jokainen esiintyy täsmälleen kerran.
`f(m,n)` laittaa kaikki positiiviset rationaaliluvut jonoon siten, että jokainen esiintyy ainakin kerran.
Kaikkia rationaalilukuja ei voi laittaa jonoon, koska jono ei saa jatkua loputtomasti vasemmalle.
Kaikki rationaaliluvut voi laittaa jonoon laittamalla nolla ensin ja sitten negatiiviset ja positiiviset vuorotellen.
tai

Jokainen numeroituva reaalilukujen osajoukko on nollamitallinen

Olkoon `p` positiivinen luku. Jos tikku, jonka pituus on `p`, asetetaan lukusuoralle siten, että tikun keskikohta on kohdassa `k`, niin se peittää täsmälleen luvut `< x < ` .
tai

Käytimme vertailua < eikä ≤, koska jatkon kannalta kumpikin kelpaisi ja jotain piti valita.

Katkaisemme tikun keskeltä kahtia ja peitämme toisella puolikkaalla luvun `1/1`. Tikun puolikas peittää luvut `< x < ` .
tai

Katkaisemme jäljelle jääneen tikun puolikkaan keskeltä kahtia ja peitämme toisella osalla luvun `2/1`. Tikun neljännes peittää luvut `< x < ` .
tai

Katkaisemme jäljelle jääneen tikunpätkän keskeltä kahtia ja peitämme toisella osalla luvun `1/2`. Tikun kahdeksasosa peittää luvut `< x < ` .
tai

Näin voidaan jatkaa ja peittää `3/1`, `2/2`, `1/3`, `4/1`, `3/2` ja niin edelleen, edeten alussa olleen kuvan mukaan loputtomasti. Koska MathCheck ei osaa merkintää `f(m,n)` ja koska en halua käskeä sinua kirjoittamaan `f(m,n)`:n pitkää lauseketta, käytämme kirjainta `f` niiden tilalla. Siis `f = f(m,n)`. Luvun `m/n` peittäjäksi tulee tikunpätkä, jonka pituus on .
tai

Tikunpätkiä menee päällekkäin. Esimerkiksi jos `p=4`, niin se tikunpätkä, jolla peitetään `1/2`, menee koko pituudeltaan päällekkäin ja se tikunpätkä, jolla peitetään `2/1`, menee osittain päällekkäin sen tikunpätkän kanssa, jolla peitettiin `1/1`.

<--->  <->
<------->
0---1---2---3

Jos lukua `p` pienennetään, päällekkäisyys vähenee, mutta ei kuitenkaan katoa kokonaan. Vaikka `p` olisi kuinka pieni positiivinen luku tahansa, jokainen tikun­pätkä peittää muitakin murtolukuja kuin keskikohtansa alle jäävän. Sitäpaitsi jokainen murtoluku peitetään äärettömän monella tikunpätkällä, joiden keskikohta on luvun päällä. Luvun `m/n` peittäjäksi tulee paitsi se tikun­pätkä, jonka järjestys­numero on `f(m,n)`, myös ne, joiden järjestys­numerot ovat `f(2m,2n)`, `f(3m,3n)`, …, koska `m/n``=``(2m)/(2n)``=``(3m)/(3n)``=``...`.

Olemme siis peittäneet jokaisen positiivisen rationaali­luvun, vieläpä äärettömän moneen kertaan, yhdestä tikusta leikatuilla pätkillä. Tikun pituus `p` on mieli­valtainen positiivinen luku. Se voi olla 1, 0.1 tai vaikka 0.0000000001. Lukusuoran nollasta oikealle menevä puolisuora on äärettömän pituinen. Näyttää ikään kuin olisimme peittäneet sen äärellisen pituisella janalla. Itse asiassa jana saa olla miten lyhyt tahansa (eli sen pituus saa olla miten pieni positiivinen luku tahansa). Tämä tuntuu järjen­vastaiselta.

Tämän ongelman ratkaisu koostuu kolmesta osasta.

Ensiksi, on hyvä huomata heti alkuun, että ongelma ei koske todellista fysikaalista maailmaamme vaan matemaattisten abstraktioiden maailmaa. Todellista tikkua ei voi puolittaa miten monta kertaa tahansa. Todellinen tikku ei voi olla lyhyempi kuin esim. atomi.

Toiseksi, lukusuoralla on paljon muitakin lukuja kuin rationaali­luvut. Itse asiassa lukusuoran luvuista mität­tömän pieni osa on rationaalilukuja. Tämä voidaan todistaa monella eri tavalla. Juuri läpikäyty todistus osoittaa, että positiivisten rationaalilukujen yhteensä peittämä pituus on nolla. Tämä pätee vaikka todis­tuksessa ei käytetty nollan pituista tikkua, sillä valitsetpa minkä tahansa `r > 0`, valitsemalla `p = r/2` todistus osoittaa, että positiivisten rationaalilukujen yhteensä peittämä pituus on vähemmän kuin `r`. Koska se on vähemmän kuin mikä tahansa positiivinen luku (ja koska pituus ei voi olla negatiivinen), se on nolla. Sanotaan, että positiivisten rationaalilukujen joukko on nolla­mitallinen.

Peitimme edellä tikunpätkillä kaikki positiiiviset rationaali­luvut, mutta sama päättely toimii jokaiselle numeroi­tuvalle lukujoukolle. Siksi jokainen numeroituva lukujoukko on nollamitallinen.

Kolmanneksi, niin omituiselta kuin se tuntuukin, mielivaltaisen pituinen tikku todella riittää peittämään suoran pisteitä siten, että vaikka jokaista pistettä ei peitetäkään, jokaisen peitetyn pisteen lähellä on peitetty piste. Hyvin lähellä. Valitsetpa minkä tahansa reaaliluvun `x` ja minkä tahansa positiivisen luvun `r`, lukujen `x-r` ja `x+r` välillä on äärettömän monta rationaalilukua. Esimerkiksi luku, joka saadaan katkaisemalla `x`:n desimaaliesitys `k` desimaalin jälkeen, on rationaaliluku joka poikkeaa `x`:stä enintään `10^(-k)`:n verran.

Ihmiskunnalla on ollut vaikeuksia löytää, miten tämä asiakokonaisuus menee ja hyväksyä, että niin se menee. Se, että on muitakin lukuja kuin rationaali­luvut, keksittiin antiikin aikana. Legenda kertoo, että keksintö järkytti aikalaisia niin pahasti, että he tappoivat keksijän. Ylinume­roituvuuden keksijä Georg Cantor (1845–1918) kohtasi paljon jyrkkää vastustusta muilta mate­maatikoilta. Elämänsä viimeiset yli 30 vuotta Cantor kärsi toistuvasta masennuksesta. Nykyisin Cantorin katsotaan olleen oikeassa ja hänen vastustajiensa väärässä, ja Cantorin tuloksia pidetään erittäin merkittävinä.

Nykyisinkin netin keskustelu­palstoilta löytyy sinnikkäitä keskustelijoita (tai ehkä ei oikeastaan keskustelijoita vaan vänkääjiä), jotka väittävät kumonneensa ylinume­roi­tuvuuden olemassaolon. Kaksi muuta tulosta, joita vastaan hyökätään netissä raivoisasti, ovat Gödelin epätäydel­lisyyslauseet, joka on modernin logiikan mahdol­lisesti tärkein saavutus; sekä pysähtymistesterin olemattomuus, joka on keskeinen teoreettisessa tietojen­käsittely­tieteessä. Kahden viimeksi mainitun välillä on läheinen yhteys, eivätkä ne ole ylinumeroituvuudesta tolkuttoman kaukana.

Tällä alalla saavutetuissa tuloksissa ei ole sisäisiä ristiriitaisuuksia, moni tulos viittaa samaan suuntaan, ja lähes kaikki asiantuntijat hyväksyvät ne. Siltä varalta, että olet se nero, joka huomaa mikä siinä kaikessa on vikana ja keksii paremman teorian, haluan antaa yhden neuvon. Ennen kuin alat julistaa uutta oppiasi maailmalle, pidä huoli, että tiedät hyvin, hyvin tarkasti, miten nykyinen oppi menee. Muuten kukaan asiantuntija ei kuuntele sinua.

Koetpa itsesi neroksi tai et, ehkä on parempi, että et tutustu Banach-Tarskin paradoksiin.

Nyt kun on jonkin aikaa jaariteltu, katsotaanpa, muistatko tärkeimmät tässä tehtävässä esitellyt käsitteet.

Tarkastelun kohteena on `{`a,b`}^+` eli kaikkien merkeistä a ja b koostuvien epätyhjien äärellisten merkkijonojen joukko.
Joukkoa `{`a,b`}^+` ei voi esittää päättymättömänä jonona.
a, b, aa, ab, ba, bb, aaa, … on `{`a,b`}^+` päätty­mättömänä jonona.
`{`a,b`}^+` voidaan esittää päättymättömänä jonona seuraavasti. Aluksi ovat kaikki a-alkuiset, sitten kaikki b-alkuiset. a-alkuisten aluksi on a, sitten kaikki aa-alkuiset ja lopuksi kaikki ab-alkuiset. b-alkuisten aluksi on b, sitten kaikki ba-alkuiset ja lopuksi kaikki bb-alkuiset. Näin jatketaan.
tai

Joukko {4,5,6} on numeroituva.
Reaalilukujen joukko on numeroituva.
Reaalilukujen joukko on ylinumeroituva.
Rationaalilukujen joukko on numeroituva.
Rationaalilukujen joukko on ylinumeroituva.
Kokonaislukujen joukko on numeroituva.
tai

Tämä riittäköön tällä kertaa!