tiistai 15. marraskuuta 2011

Vapaa valinta II.

Matemaatikkoja jo pitkään kiusannut Valinta-aksiooma on äärimmäisen kiehtova tapaus. Olennaisilta osin se sanoo, että jos meillä on kokoelma joukkoja, voimme aina muodostaa joukon niin, että valitaan kustakin joukosta yksi alkio ja laitetaan se tähän joukkoon; jos nämä joukot eivät ole tyhjiä, lopputulos ei myöskään ole tyhjä.

Äärellisissä tapauksissa tämä tuntuu olevan mielekäs aksioma, intuitiivisesti "tosi". Se ei edes vaadi itseasiassa äärellisessä tapauksessa omaa aksiomaansa, vaan seuraa muista joukko-opin aksiomista. Monissa äärettömissäkään tapauksissa sitä ei tarvitse soveltaa, kunhan jokin kokoelman tekevä funktio on jostain muusta syystä olemassa. Esimerkiksi jos kokoelma (kokonaislukujen) joukkoja Si = {2i,2i+1}, niin emme tarvitse valinta-aksioomaa erikseen määritelläksemme parillisten lukujen joukon; se saadaan valitsemalla kustakin joukosta se pienempi alkio.

Valinta-aksioomalla on seurauksia, kuten Zermelon lause, joka sanoo, että jokaiselle joukolle voidaan rakentaa "hyvinjärjestys": totaalinen järjestysrelaatio niin, että jokaisella epätyhjällä osajoukolla on pienin alkio. Tällä on myös seuraus, että voidaan esittää totaalinen järjestysrelaatio, jonka mielessä jokaisella alkiolla on "seuraaja". Esimerkiksi jo reaaliluvuilla tällainen relaatio vaikuttaisi mielipuoliselta.

Tällä on kytkös ns. kontinuumihypoteesiin, joka sanoo, että reaalilukujen mahtavuuden (äärettömillä joukoilla puhutaan "mahtavuudesta" eikä koosta) ja luonnollisten lukujen mahtavuuden välillä ei ole mitään. Äärettömille "sama mahtavuus" merkitsee sitä, että on olemassa bijektio joukkojen välillä. Esimerkiksi rationaalilukujen ja luonnollisten lukujen välille voidaan rakentaa bijektio. Cantorin ns. diagonalisointitodistus perustuu siihen, että tällaisen bijektion olemassaolosta seuraa ristiriita.

Cantorin todistuksessa on kyllä yksi reikä (vaikka uskonkin sen olevan oikein). Todistus menee seuraavasti: Olettakaamme, että meillä on numerointi reaaliluvuille väliltä [0,1), so. luettelemalla f(0), f(1), ..., jokainen nollan ja ykkösen välissä oleva reaaliluku tulee ennen pitkää vastaan listassa. Voimme olettaa, että luvuille on jokin desimaalikehitelmä. Valitun välin luonteen vuoksi ne ovat muotoa 0.123... Rakennamme luvun, joka ei voi olla listassa: olkoon g(x,i) luvun x desimaaliesityksen i:s numero. Lukumme z määritellään niin, että sen i:s numero on g(f(i),i) + 1 (missä 9+1 tulkitaan olevan 0). Vertaamalla z:aa jokaiseen listan lukuun, voimme todeta varmaksi, että se on ainakin i:nnen desimaalinsa osalta eri, eikä siten voi olla mikään listan luku.

Todistuksen "aukko" on siinä, että mikään ei takaa, että tämä uusi luku ei ole esimerkiksi 0.9999..., joka ei edes kuulu tuolle välille, eikä sen siten edes pitäisi olla listassa. Muitakin selityksiä tälle voidaan antaa; en puutu niihin tässä. Olennaista on, että voimme joko hyväksyä tai olla hyväksymättä, että reaalilukuja on "aidosti enemmän" kuin luonnollisia lukuja. (Siis, toisin kuin vaikka rationaalilukuja, joita on varmasti yhtä paljon). Kontinuumihypoteesi nimittäin sanoo, että oli niin tahi näin, niiden välissä ei ainakaan ole mitään erisuurta mahtavuutta. Eli siis suomeksi: jokaisessa reaalilukujen joukossa on joko "yhtä monta alkiota" kuin luonnollisissa luvuissa, tai sitten "yhtä monta" kuin reaaliluvuissa. Mitään välimalleja ei ole. Kontinuumihypoteesi itse ei ole valinta-aksioomasta riippuvainen.

Sensijaan ns. yleistetty kontinuumihypoteesi sanoo, että jos X on ääretön joukko, niin X:n ja X:n osajoukkojen kokoelman väliin ei voi tunkea mitään mahtavuutta. Lisäksi se sanoo, että luonnollisten lukujen joukko on "ensimmäinen" ääretön joukko; jos joukko ei ole yhtä mahtava kuin luonnollisten lukujen joukko, se on äärellinen. Yleistetyn kontinuumihypoteesin seurauksena saadaan kyllä valinta-aksiooma, jos Zermelo-Frankelin joukko-oppi otetaan muuten annettuna.

Todellisuudessa tämä ei ole minua koskaan erityisemmin vaivannut, enkä halua päätäni vaivata muutenkaan tällä liiaksi. Jotkut äärellisen ja äärettömän välimaastoon sijoittuvat ilmiöt kuitenkin toisinaan hämmentävät ja tuovat mieleen nämä pohdinnat. Esimerkiksi prosessialgebrassa voidaan määritellä prosessi valintana toisista prosesseista. Yleensä äärellisenä, mutta myös ääretön tapaus on mahdollinen. Esimerkiksi "kone valitsee kokonaisluvun" on tällainen; usein se ajatellaan rajoitettuna, eli kokonaisluvulla on jokin arvoalue. Toisaalta voimme ajatella myös sen äärettömänä. En väitä, että valinta-aksiooma on tässä olennainen, tietenkään, ainoastaan, että mielikuvia siitä syntyy.

Myös malliteoreettisia argumentteja muotoillessa on joskus tullut mieleen, josko valinta-aksioomaa tulisi soveltaa. En ole vielä kohdannut yhteenkään ongelmaan, jossa se olisi välttämätöntä, mutta en pidä tätäkään mahdottomana. Kun aikanaan opiskelin matematiikkaa, jatkuvan matematiikan, kuten vaikka funktionaalianalyysin kohdalla minua aina kiusasi se, että osa tuloksista vaati valinta-aksiooman käyttöä. Kyse ei ole siitä, ettenkö formalistina niin olisi valmis tekemään, vaan siitä, että heikkous on vahvuutta, ja uudet oletukset tekevät teoriasta vahvemman, eli huonomman.

LISÄYS (25.11.) xkcd strippi samasta aiheesta.

23 kommenttia:

Tomi kirjoitti...

X:n potenssijoukko on aidosti mahtavampi kuin X itse. Tämä on helppo todistaa diagonaali konstruktioilla.

Jos luonnollisten lukujen joukko olisi yhtä mahtava kuin reaalilukujen joukko, se rommuttaisi täysin esim. Lebesguen mitta-konstruktion.

Ainakin minun intuitioni vastaista on se, että reaalilukujen joukko R on yhtä mahtava kuin R^N kaikkilla N:llä.

Tomi kirjoitti...

Valinta-aksiooman avulla voidaan saada varsi epäintuitiviisia tuloksia, kuten Banach-Tarski-paradoksi. Siinä pallo hajotetaan pistevieraisiin osiin ja kuvataan translaatioilla ja rotaatioilla kahdeksi alkuperäisen pallon kopioksi.
Tietenkään kaikki nämä pistevieraat palat eivät voi olla Lebesgue-mitallisia.
Itseasiassa kaikki ei-lebesgue-mitalliset joukot konstruoidaan valinta-aksiooman avulla.

Tiedemies kirjoitti...

Juu, en viitsinyt edes mennä mittateoriaan. Lebesgue-mitan määritelmästä tosiaan seuraa, että jokainen numeroituva joukko on nollamitallinen, koska peitteen, jonka avulla ulkomitta määritellään, ei vaadita olevan äärellinen, so. se saa olla numeroituva. So. numeroituva joukko voidaan peittää omilla alkioillaan jotka yksittäisinä ovat nollamitallisia laatikoita.

Tässä tarvitaa kyllä minusta valinta-aksioomaa, koska ulkomitassa määritellyn peitteen infimum ei vielä kerro, mitkä ne laatikot ovat, joista peitteitä tehdään, so. ne pitää valita kaikkien joukkojen joukosta.

Tiedemies kirjoitti...

Karvalakkiversio tuosta diagonalisointitodistuksesta on muuten rikki siksi, että jokaiselle päättyvälle sekvenssille on aina kaksi päättymätöntä esitystä: luvulle 0.1 on esitykset 0.1000... ja 0.0999... Tämä pätee kaikille päättyville sekvensseille.
Esimerkiksi, jos teemme tuon yllä mainitun "kikan" listalle, jossa toistuu luku 0.0999... loputtomiin, niin saamme aikaiseksi luvun 0.1000..., ja vaikka väittäisimme, ettei tämä luku ole listassa, olisimme väärässä: Kyllä se on, vieläpä äärettömän monta kertaa!!

Tomi kirjoitti...

Lebesguen mittakonstruktiossa ei kaiketi tarvit valinta-aksioomaa. En ole ko. väitteeseen törmännyt.

Diagonaalikonstruktiossa mainitsemasi ongelma voidaan välttää valitsemalla vain sellaiset välin [0,1] luvut, jotka sisältävät esim. vain lukuja 0,1,2.
Diagonaalikonstruktio osoittaa, että luonnollisilta luvuilta ei voi olla bijektiota tälle [0,1]:sen aidolle osajoukolle.

Artoasdf kirjoitti...

"Lukumme z määritellään niin, että sen i:s numero on g(f(i),i) + 1 (missä 9+1 tulkitaan olevan 0)."

Onko tuommosta z:n määritelmää käytetty jossain? Siitä pääsee ainakin eroon, esimerkiksi valitsemalla n:ksi desimaaliksi aina jonkin tietyn luvun k, paitsi siinä tapauksessa, että diagonaalin n. desimaali on k, jolloin valitaan vaikka k+1.

Tiedemies kirjoitti...

Totta kaikki. Siis, diagonaalikonstruktio kyllä on ihan ok. Sen voi tehdä vaikka biteillä.

Lebesguen mitassa ei ehkä tarvita valinta-aksioomaa. Siinä on kuitenkin infimum numeroituvista laatikkopeitteistä. Se vähän arveluttaa, kun siinä oletetaan sellaisen olemassaolo, ja haiskahtaa zornin lemmalta. En ole analyysin asiantuntija, tästä lukemisesta on yli 10 vuotta.

opottone kirjoitti...

Tähän sopii hyvin von Neumann-lainaus, "In mathematics you don't understand things. You just get used to them."

Tarkoititkohan kenties reaalilukuja tuossa kun kerroit hyvinjärjestyksen olemassaolon tuntuvan järjettömält?

Tiedemies kirjoitti...

Reaalilukuja kyllä, olet oikeassa.
Rationaaliluvuillehan hyvinjärjestys kyllä on olemassa, koska niille on olemassa numerointi.

Anonyymi kirjoitti...

Valintaaksioman kummallisuus on siina etta se ei vaikuta miltaan joukkoopilliselta periaatteelta. Se IMO oikeutuu silla mat 101 kurssin funktion kasitteella. Kun ne erillliset joukot siina perheessa ovat epatyhjia niin tottahan sellainen funktiokin loytyy. Tavaraa liitetaan vain toiseen jne.
Lisaksi ja tassa on eras joukkoopillinen periaate kaytossa funktion kuvajoukko on aina pienempi kuin alkukuva mitaan ongelmia ei pitaisi tulla.

Tiedemies kirjoitti...

Gc, joo, mutta kun Zermelon lauseessa nyt vaan ei ole mitään järkeä.

Oikeastaan ainoa selitys, jonka tähän keksin on, että joko Cantorin todistus nyt vaan on väärin, ja reaaliluvut numeroituvat, tai sitten ZF on ristiriitainen. GCH on triviaalisti tosi, jos koko aleph-hierarkia romahtaa, jolloin valinta-aksioomankaan kanssa ei jouduta ongelmiin, joten tässä mielessä Cantorin väärässäoleminen olisi yksi mahdollisuus.

Tässä vaan käy sitten niin, että lebesguen mitan määritelmä on rikki. Ja siis, onhan se Cantorin todistus nyt ihan selvästi oikein.

Siis jäljelle jää ZF:n ristiriitaisuus. Mutta ei siinäkään ole mitään järkeä.

Perinteinen tapa on kai hyväksyä Zermelon lause, ja ajatella, että se nyt vaan on järjetön, eikä sille voi mitään.

Anonyymi kirjoitti...

Se diagonaalitodistus on se huonompi todistus. potenssijoukko todistus on se parempi se ei voi failata.

Anonyymi kirjoitti...

tiede muuttuu kasittomattomaksi kun kulttuurimme on kuolemassa tai kuollut. samoin kavi grequille. ei ne pystyny koskaan ymmartamaan edes konkreettisia irrotionaalilukuja tai nollaa.

Tomi kirjoitti...

Gc, kreikkalaiset halusivat matematiikkansa perustan olevan suhdeoppi.
Tästä penseys irrationaalilukuihin.
He halusivat myös matematiikan olevan konstruoitavissa harpilla ja viivaimella, eli, että se olisi palautettavissa geometriaan.

Tiedemies kirjoitti...

Se diagonaalitodistus on se huonompi todistus. potenssijoukko todistus on se parempi se ei voi failata.

Se ei voi failata, mutta se tarvitsee reaalilukujen konstruktion, jossa reaalit ovat oikeasti isomorfinen luonnollisten lukujen potenssijoukon kanssa. Esimerkiksi Cauchy-jonoille (tai dedekindin leikkauksille) tämän osoittaminen ei riitä, koska monet cauchy-jonot (ja d-leikkaukset) suppenevat kohti samaa reaalilukua.

Korostan nyt, että en todellakaan väitä, että Cantorin todistus on väärin, uskon että se on oikein, mutta jokin failaa, koska valinta-aksioomankin pitäisi olla "totta", ja se on taas Zermelon lauseen kanssa yhtäpitävä, ja tämä ei minusta sovi yhteen Cantorin kanssa. Itseasiassa minusta Zermelon lause ja Cantorin diagonaalitodistukset ovat ihan suoraan ristiriidassa: Otetaan se Zermelon hyvinjärjestys, niin siitä saadaan suoraan numerointi.

Nyt muuten kun luin tarkemmin, niin hyvinjärjestyksen olemassaolo on yhtäpitävä VA:n kanssa vain ensimmäisen kertaluvun teorioissa. Toisen kertaluvun teorioissa hyvinjärjestyslause on aidosti VA:ta vahvempi. Eli ensimmäisen kertaluvun logiikka on liian köykäinen, kun puhutaan äärettömyyksistä. Tämä varmaan on tervejärkisin vaihtoehto muutenkin, koska siellä on kaikenlaisia Skolemin paradokseja nurkissa pyörimässä muutenkin.

Anonyymi kirjoitti...

siis suhdeoppi oli seuraus ei syy. euklideksella oli geometriassaan kai kahdenlaisia aksiomia varsinaiset aksiomat ns. yleiset totuudet ja postulaatit. postulaatit olivat kai lahinna konstruktioita tyyliin kahden pisteen kautta voidaan piirtaa yksi ja vain yksi suora. niiden rooli oli kai sama kuinr eksistenssiaksioomien meidan matematiikassa. joku aksioma tais olla etta kokonaisuus on osaansa suurempi. ei toimi aarettomassa maailmassa.

opottone kirjoitti...

Hyvinjärjestyksen olemassaolo, ja siis Zermelon lause, ei varsinaisesti kerro mitään numeroituvuudesta. Esimerkiksi otetaan joukko M joka sisältää kaikki luonnolliset luvut ja äärettömän, M = {∞, 0, 1, 2, …}, ja tavallinen järjestysrelaatio. M on hyvinjärjestetty, mutta järjestys ei anna meille numerointia.

Siis toki M on numeroituva, mutta sitä numerointia ei pysty konstruoimaan käymällä luvut läpi pienimmästä alkaen.

Jos nyt tuntuu siltä että jokin failaa, niin minusta se on VA. Siitä kun seuraa muutakin epäilyttävää kuin reaalilukujen hyvinjärjestys, esimerkiksi jo yllä mainittu Banach-Tarski. Cantorin diagonaaliargumentti ei ole yhtä epäilyttävä, ja voihan reaalilukujen ylinumeroituvuuden todistaa muutenkin, esimerkiksi konstruoimalla Lebesquen mitan. (En nyt muista oliko sen konstruktiolla jotain luurankoja kaapeissa, luultavasti ei.)

Tomi kirjoitti...

Lebesguen konstruktiossa oletetaan reaalilukujen olevan ylinumeroituva. Joten sitä ei voida käyttää ylinumeroituvuuden todisteena.

Tiedemies kirjoitti...

Tomi, ei lebesguen konstruktiossa käytetä tuota oletusta. Konstruktiosta seuraa, että Lebesquen mitta ei toimi, jos reaaliluvut numeroituvat.

Sanotaan, että joukkokokoelma, joka peittää annetun joukon, on "laatikkopeite", jos se koostuu äärellisistä suljetuista väleistä. Välin ylämitta [a,b] määritellään yksinkertaisesti b-a:ksi. Laatikkopeitteen ylämitta on sen laatikoiden ylämittojen summa.

Lebesguen mitta määritellään niin, että se on infimum joukon numeroituvista laatikkopeitteistä.

Tästä seuraa se, että jos reaaliluvut ovat numeroituvia, niin menetetään mitta-aksiomista muistaakseni ainakin se, että jos mitallinen joukko jaetaan kahteen pistevieraaseen joukkoon ja toinen on mitallinen, niin toinenkin on, koska välin [0,1] rationaaliluvut ja irrationaaliluvut ovat pistevieraat, rationaaliluvuille numeroituva peite koostuu luvuista itsestään, joten ne ovat nollamitalliset. Jos irrationaaliluvut ovat samalla lailla numeroituvat, niin nekin ovat nollamitalliset.

Muitakin kummallisuuksia tulee kyllä. Siinä olen opottonen kanssa samaa mieltä, että VA haisee muutenkin kauas. Paitsi hyvinjärjestys (jota edelleen en suostu hyväksymään. :) ), siitä tosiaan seuraa Banach-Tarski.

Tomi kirjoitti...

TM, jos reaaliluvut olisi numeroituvia, kaikkien joukkojen mitta olisi nolla. Ne voitaisiin siis peittää aina laatikoilla, joiden n-tilavuus summattuna olisi mielivaltaisen pieni.
Elä oletusta reaalilukujen ylinumeroituvuudesta käytetään konstruktiossa implisiittisesti.

Tomi kirjoitti...

Jos reaaliluvut eivät olisi täydellisesti järjestettyjä, niin matematiikka olisi hedelmätöntä. Tietenkin olisi mahdollista luopua reaalilukujen järjestysaksioomasta. Mutta tässä aksioomajärjestelmässä matematiikka olisi hedelmätöntä.

Yleensäkkin ihmettelen natinaa aksioomista. Kuitenkin on kyse sopimuksista. Pystytään luomaan erilaisia aksioomajärjestelmiä, joista toiset ovat hedelmällisempiä kuin toiset. Matematiikka valinta-aksiooman kanssa on hedelmällisempää kuin ilman sitä. Kuitenkaan täydellistä ja ristiriidatonta (ja hedelmällistä) aksioomajärjestelmää ei voida luoda.

Tiedemies kirjoitti...

Reaaliluvut ovat kyllä totaalisesti järjestettyjä, sen tuottaa ihan normaali järjestysvertailu.

Se, mitä vastaan urputan on hyvinjärjestys, joka sanoo, että kaikissa joukoissa on pienin alkio. Tällaiseksi järjestykseksi ei kelpaa se normaali järjestysrelaatio, koska esimerkiksi avoimella välillä ei ole pienintä alkiota. Sillä on seurauksena myös se, että jokaisella joukon luvulla on uniikki seuraaja.

Anonyymi kirjoitti...

Miksi juuri hyvinjärjestyksessä on jotain outoa? Esimerkiksi
0,1,2,3,4,....-1,-2,-3,-4 on hyvinjärjestys, jonka järjestys tyyppi on omega+omega. Hyvinjärjestyksellä ei siis ole välttämättä kaikkia niitä oimaisuuksia kuin luonnollisten lukujen normaalilla järjestyksellä:
0,1,2.... jonka järjestystyyppi on omega.