Mahtavuus

Wikipedia
Loikkaa: valikkoon, hakuun

Joukon mahtavuus eli kardinaliteetti eli koko tarkoittaa joukon alkioiden lukumäärää, jota ilmaistaan kardinaaliluvulla. Kardinaaliluku voi olla luonnollinen luku tai jokin ääretön kardinaaliluku. Käsitteet ovat Georg Cantorin esittelemiä vuonna 1874 julkaisemassa joukko-oppia käsittelevissä kirjoitelmassaan.

Johdanto[muokkaa | muokkaa wikitekstiä]

Esimerkiksi joukossa {1,2,3} alkioita on 3 ja joukossa {1, 2, 3, ..., n} niitä on n. Äärellisillä joukoilla eli sellaisilla joukoilla, joissa on äärellinen määrä alkiota, mahtavuuden sijasta käytetään usein sanaa 'koko. Kardinaliteetti sen sijaan on sanana neutraali ja käytetään äärellisten ja äärettömien joukkojen yhteydessä.

Kun äärettömässä joukossa on äärettömästi alkioita, ilmoitetaan sen mahtavuus sanalla ääretön. Vaikka ääretön tarkoittaa jotain muuta asiaa kuin lukua, on se hyväksytty mahtavuuden kardinaaliksi, koska se ilmaisee sitä loputtomuutta, mikä alkioiden laskeminen vaatisi.

Joukkojen vertaaminen[muokkaa | muokkaa wikitekstiä]

Joukkoja verrataan alkio alkiolta, jotta niiden mahtavuuden erot havaittaisiin. Vertailu on luonnollisesti vain ajatustyötä, jossa mietitään vertailun onnistumista tai epäonnistunista.

Pienten joukkojen vertailussa voidaan käyttää alkioiden laskemista. Kummankin joukon alkiot lasketaan ja verrataan kardinaaleja keskenään. Äärettömillä joukoilla käytetään induktiivista luettelointia. Siinä otetaan joukosta S alkio ja liitetään siihen toisen joukon T alkio pariksi. Jos jokaiselle alkiolle molemmissa joukoissa riittää pari, on joukot yhtä mahtavia eli S \sim T. Se joukko, jolta parinmuodostuksessa jää alkioita yli, on mahtavampi.

Tarkastellaan esimerkkinä kahta äärellistä joukkoa S = \{ a, b, c, d \} ja T = \{1, 2, 3 \}. Vertailu tehdään ensin ottamalla aina joukon T alkiolle pari joukosta S. Silloin saadaan parit \{ (1,a), (2,b), (3,c) \} ja joukon S alkiot riittivät. Tämä ei vielä merkitse, että joukot ovat yhtä mahtavia. Parinmuodostus tulee onnistua myös toisin päin. Tällöin muodostetaan jokaiselle kirjaimelle pari numerosta. Tämä ei onnistu, koska kirjaimelle d ei löydy tyhjentyneestä numerojoukosta paria. Siksi tuomitsemme joukon S mahtavammaksi kuin joukon T.

Joukon S mahtavuus merkitään joko |S| tai card(S). Yhtämahtavuus voidaan merkitä myös |S| = |T| tai card(S) = card(T). Jos joukko S on mahtavampi kuin joukko T, merkitään |S| > |T|.

Äärettömillä joukoilla induktiivinen luetteloiminen ei aina onnistu. Niillä keksitään funktion kuvaus, joka saa arvokseen toisen joukon kaikki alkiot ja tulokseksi saadaan toisen joukon alkioita. Menetelmä toisetaan käänteiskuvauksen avulla, jotta myös käänteinen kuvaus todetaan toimivaksi. Kuvausten onnistumisesta päätellään kuvauksen laatu ja päätellään siitä joukkojen keskinäinen mahtavuus. Mahdolliset vaihtoehdot ovat:

Viimeinen väite saadaan kahdesta edellisesta tuloksesta Cantorin–Schröderin–Bersteinin lauseen avulla.

Esimerkiksi luonnollisten lukujen joukko \mathbb{N} = \{1, 2, 3, 4, 5, ... \} on yhtä mahtava osajoukkonsa {2, 4, 6, 8, 10, ...} kanssa. Tämä nähdään kahdella tavalla. Parinmuodostuksessa saadaan parijono \{ (1,2), (2,4), (3,6), (4,8), (5,10), ... , (n,2n), ... \}, jossa pariksi valitaan toisesta joukosta aina kaksi kertaa suurempi luku. Käänteinen parinvalinta toimii niin, että parillisen luvun pariksi valitaan aina puolet pienempi luku. Tätä voisi jatkaa äärettömän monta kertaa ja siksi todetaankin, että parilliset luvut ja luonnolliset luvut ovat yhtä mahtavat.

Toinen menetelmä on keksiä joukkojen välille kuvaus, jolle löydetään käänteiskuvaus. Tällainen kuvauspari on funktio f(x) = 2x ja sen käänteisfunktio f^{-1}(x) = \frac{1}{2}x. Näillä voidaan kuvata kaikki lähtöjoukon alkiot maalijoukon alkioiksi ilman, että yksikään alkio jäisi kuvaamatta. Funktio onkin bijektio, joten se takaakin kuvauksen onnistumisen. Joukot ovat yhtä mahtavia. [1]

Numeroituva ja ylinumeroituva[muokkaa | muokkaa wikitekstiä]

Cantor tutki äärettömiä joukkoja ja havaitsi pian että jotkin joukot ovat "enemmän äärettömiä" kuin toiset. Tämä johti kardinaalilukujen vertailuun. Koska luonnolliset luvut tiedetään jo äärettömäksi joukoksi, merkitään niiden mahtavuutta kardinaaliluvulla \aleph_0 = \infty (lue:alef-0). Luonnollisisten lukujen joukosta sanotaan, että se on laskettavasti tai numeroituvasti ääretön, koska sen alkioista voidaan muodostaa alkiopareja verrattavan joukon alkioiden kanssa.

Cantor oletti, että oli olemassa suurempia kardinaalilukuja ja että ne voitiin järjestää suuruusjärjestykseen \aleph_0 < \aleph_1 < \aleph_2 < ... . Suurempien joukkojen etsintä tuotti tulosta, kun hän osoitti reaalilukujen olevan suurempi joukko. Vieläkään ei tiedetä, onko reaalilukujen kardinaliteetti \aleph_1 tai \aleph_2 vai jokin muu. Toistaiseksi reaalilukujen kardinalilukuna käytetään merkintää c tai C (engl. continuum) tai joskus \beth_1 (lue: "beth"-1) ja se oli ensimmäinen todettu ylinumeroituvasti ääretön lukujoukko. Koska ylinumeroituva lukujoukko on mahtavampi kuin numeroituva joukko, on sen kardinaaliluku aina ääretön.

Mahtavuuden ymmärtäminen[muokkaa | muokkaa wikitekstiä]

Ei kuitenkaan voi sanoa, että reaalilukuja olisi enemmän kuin vaikkapa kokonaislukuja, koska molempia on äärettömästi. Sen sijaan reaalilukujen joukko on kokonaislukujen joukkoa tiheämpi. Tiheä joukko on sellainen, että joukon kaikkien alkioparien välistä voidaan löytää uusi joukon alkio. Luonnolliset luvut eivät ole tiheä joukko, koska esimerkiksi lukujen 1 ja 2 välistä ei löydy luonnollista lukua. Sen sijaan rationaaliluvut ovat tiheä joukko.

Mahtavuuteen liittyviä yleisiä tuloksia[muokkaa | muokkaa wikitekstiä]

Määritelmän mukaan luonnolliset luvut \N muodostavat numeroituvasti äärettömän lukujoukon. Voidaan osoittaa, että kaikki osajoukot S \subseteq \N ovat myös numeroituvia. Jos S on numeroituva ja ääretön, on olemassa bijektio f: S \leftrightarrow \N ja joukot ovat yhtä mahtavat S \sim \N. Jos S' ylinumeroituva ja S' \subseteq S, niin myös S on ylinumeroituva. [1]

Lukujoukkojen mahtavuus[muokkaa | muokkaa wikitekstiä]

Kaikki luonnollisten lukujen osajoukot ovat edelliseen viitaten numeroituvia. Erityisesti luonnollisten lukujen äärettömän suuret osajoukot ovat yhtä mahtavia kuin luonnollisten lukujen joukko itse. Tällasia osajoukkoja ovat esimerkiksi parilliset- ja parittomat luvut, kolmioluvut, neliöluvut ja alkuluvut. Siis on card(\N) = \aleph_0.

Cantor todisti jo 1874, että card(\Z)=card(\Q) = \aleph_0. Ne hän todisti luettelemalla kokonaisluvut ja rationaaliluvut tietyn systeemin avulla ja osoitti, että jokaiselle luvulle löytyy pari luonnollisista luvuista. Todistamistavat esitelty artikkelissa numeroituva joukko.

Edelleen Cantor osoitti vuonna 1891 reaalilukujen olevan ylinumeroituvasti ääretön joukko. Koska reaaliluvut koostuvat rationaaliluvuista ja irrationaaliluvuista, ovat myös irrationaaliluvut ylinumeroituvasti ääretön joukko. Reaaliluvut voidaan jakaa nyös algebrallisiin ja transkendenttisiin lukuihin. Algebralliset luvut ovat numeroituvasti ja transkendenttiset luvut ylinumeroituvasti ääretön joukko. [1]

Katso myös[muokkaa | muokkaa wikitekstiä]

Lähteet[muokkaa | muokkaa wikitekstiä]

  • Fuchs, Walter R.: Matematiikka. Suom. Mattila, Pekka. Länsi-Saksa: Kirjayhtymä, 1968.
  • Barrow John D.: Lukujen taivas. Suom. Vilikko, Risto. Smedjebacken, Ruotsi: Art House, 1999. ISBN 951-884-231-0.
  1. a b c Schwartz, Rich: Countable and Uncountable Sets (pdf) (luentomoniste) 2007. Providence: Brown University. (englanniksi)