Versio 9. helmikuuta 2012 kello 02.30 muokkaa AvicBot (keskustelu \| muokkaukset) 3 447 muokkausta p r2.6.5) (Botti lisäsi: simple:Cardinality ← Vanhempi muutos		Versio 30. toukokuuta 2012 kello 11.58 muokkaa kumoa J Hokkanen (keskustelu \| muokkaukset) seulojat 212 596 muokkausta Ei muokkausyhteenvetoa Uudempi muutos →
Rivi 1: [[joukko\|Joukon]] '''mahtavuus''' eli '''kardinaliteetti''' eli ''koko'' tarkoittaa joukon [[alkio (joukko-oppi)\|alkioiden]] lukumäärää, jota ~~merkitään~~ilmaistaan '''kardinaaliluvulla'''. Kardinaaliluku voi olla [[luonnollinen luku]] tai jokin [[ääretön]] ~~kardinaali~~kardinaaliluku. Käsitteet ovat [[Georg Cantor]]in esittelemiä vuonna 1874 julkaisemassa [[joukko-oppi]]a käsittelevissä kirjoitelmassaan. ==Johdanto== Esimerkiksi joukon {1,2,3} mahtavuus on 3, ja joukon {1, 2, 3, ..., ''n''} mahtavuus on ''n''. Ensimmäinen ääretön kardinaaliluku on <math>\aleph_0</math> ([[alef]]-0), jolla tarkoitetaan luonnollisten lukujen joukon mahtavuutta (ns. [[numeroituvasti ääretön]]). Jatkumon, esimerkiksi [[reaaliluku]]jen, kardinaliteettia merkitään usein kirjaimella ''c'' (engl. continuum). Esimerkiksi joukossa {1,2,3} alkioita on 3 ja joukossa {1, 2, 3, ..., ''n''} niitä on ''n''. [[äärellinen joukko\|Ää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 [[Ääretön joukko\|ää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. ~~Epätyhjien joukkojen ''X'' ja ''Y'' kardinaliteettien vertailu on määritelty seuraavasti:~~ * <math> \mbox{card}(X) \le \mbox{card}(Y) \Leftrightarrow \exists f:X \rightarrow Y </math> siten, että <math>f</math> on [[injektio]].▼ * <math> \mbox{card}(X) \ge \mbox{card}(Y) \Leftrightarrow \exists f:X \rightarrow Y </math> siten, että <math>f</math> on [[surjektio]].▼ * <math> \mbox{card}(X) = \mbox{card}(Y) \Leftrightarrow \exists f:X \rightarrow Y </math> siten, että <math>f</math> on [[bijektio]].▼ ===Joukkojen vertaaminen=== Esimerkiksi luonnollisten lukujen joukko <math>\mathbb{N}</math> on yhtä mahtava [[osajoukko]]nsa {1, 3, 5, 7, 9, ...} kanssa, sillä [[funktio]] ''f''(''x'') = 2''x''+1 on bijektio ensin mainitulta joukolta toiselle. Aiemmista määritelmistä on myös helposti osoitettavissa, että 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 [[induktio\|induktiivista]] luettelointia. Siinä otetaan joukosta <math>S</math> alkio ja liitetään siihen toisen joukon <math>T</math> alkio pariksi. Jos jokaiselle alkiolle molemmissa joukoissa riittää pari, on joukot yhtä mahtavia eli <math>S \sim T</math>. Se joukko, jolta parinmuodostuksessa jää alkioita yli, on mahtavampi. <math> \mbox{card}(X) \le \mbox{card}(Y) \Leftrightarrow \mbox{card}(Y) \ge \mbox{card}(X) </math>. Tarkastellaan esimerkkinä kahta äärellistä joukkoa <math>S = \{ a, b, c, d \}</math> ja <math>T = \{1, 2, 3 \}</math>. Vertailu tehdään ensin ottamalla aina joukon <math>T</math> alkiolle pari joukosta <math>S</math>. Silloin saadaan parit <math>\{ (1,a), (2,b), (3,c) \}</math> ja joukon <math>T</math> 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 <math>d</math> ei löydy tyhjentyneestä numerojoukosta paria. Siksi tuomitsemme joukon <math>S</math> mahtavammaksi kuin joukon <math>T</math>. ~~==Rationaalilukujen ja luonnollisten lukujen mahtavuudesta==~~ Joukon <math>S</math> mahtavuus merkitään joko <math>\|S\|</math> tai <math>card(S)</math>. Yhtämahtavuus voidaan merkitä myös <math>\|S\| = \|T\|</math> tai <math>card(S) = card(T)</math>. Jos joukko <math>S</math> on mahtavampi kuin joukko <math>T</math>, merkitään <math>\|S\| > \|T\|</math>. ~~Perustellaan, miksi [[rationaaliluku]]ja on "yhtä paljon" kuin [[luonnollinen luku\|luonnollisia lukuja]] eli <math> \mathbb{N} </math> on yhtä mahtava kuin <math> \mathbb{Q} </math> .~~ Äärettömillä joukoilla induktiivinen luetteloiminen ei aina onnistu. Niillä keksitään [[funktio]]n kuvaus, joka saa arvokseen toisen joukon kaikki alkiot ja tulokseksi saadaan toisen joukon alkioita. Menetelmä toisetaan [[käänteisfunktio\|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: Koska <math>\mathbb{N}</math> on osajoukko <math>\mathbb{Q}</math>:sta, edellinen on korkeintaan yhtä mahtava kuin jälkimmäinen. Siis <math>\mbox{card}(\mathbb{N}) \le \mbox{card}(\mathbb{Q})</math> ▲ <math> \mbox{card}(XS) \le \mbox{card}(YT) \Leftrightarrow \exists f:XS \rightarrow YT </math> siten, että <math>f</math> on [[injektio]]. ▲* <math> \mbox{card}(XS) \ge \mbox{card}(YT) \Leftrightarrow \exists f:XS \rightarrow YT </math> siten, että <math>f</math> on [[surjektio]]. ▲* <math> \mbox{card}(XS) = \mbox{card}(YT) \Leftrightarrow \exists f:XS \rightarrow YT </math> siten, että <math>f</math> on [[bijektio]]. Viimeinen väite saadaan kahdesta edellisesta tuloksesta [[Cantorin–Schröderin–Bersteinin lause]]en avulla. Esimerkiksi [[luonnollinen luku\|luonnollisten lukujen]] joukko <math>\mathbb{N} = \{1, 2, 3, 4, 5, ... \}</math> on yhtä mahtava [[osajoukko]]nsa {2, 4, 6, 8, 10, ...} kanssa. Tämä nähdään kahdella tavalla. Parinmuodostuksessa saadaan parijono <math>\{ (1,2), (2,4), (3,6), (4,8), (5,10), ... , (n,2n), ... \}</math>, 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. ~~Olkoon ''n'' ja ''m'' keskenään jaottomia positiivisia kokonaislukuja. Muodostetaan injektio rationaaliluvuilla luonnollisille luvuille asettamalla~~ ''f(0)=1'' ''f(n)=3<sup>n</sup>'' ''f(-n)=2·3<sup>n</sup>'' ''f(m/n)=3<sup>m</sup>5<sup>n</sup>'' ''f(-m/n)=2·3<sup>m</sup>5<sup>n</sup>'' Toinen menetelmä on keksiä joukkojen välille kuvaus, jolle löydetään käänteiskuvaus. Tällainen kuvauspari on funktio <math>f(x) = 2x</math> ja sen käänteisfunktio <math>f^{-1} = \frac{1}{2}x</math>. Näillä voidaan kuvata kaikki [[lähtöjoukko\|lähtöjoukon]] alkiot [[maalijoukko\|maalijoukon]] alkioiksi ilman, että yksikään alkio jäisi kuvaamatta. Funktio onkin bijektio, joten se takaakin kuvauksen onnistumisen. Joukot ovat yhtä mahtavia. ~~Näin jokainen rationaaliluku kuvautuu luonnolliselle luvulle ja alkulukuesityksen yksikäsitteisyydestä seuraa, että kuvaus on injektio.~~ <ref name=brown/> ===Numeroituva ja ylinumeroituva=== Injektion olemassaolosta seuraa, että rationaalilukujen joukon mahtavuus on korkeintaan luonnollisten lukujen joukon mahtavuus. Siis <math>\mbox{card}(\mathbb{Q}) \le \mbox{card}(\mathbb{N})</math> ja [[Cantorin–Schröderin–Bersteinin lause]]en perusteella rationaalilukujen joukon mahtavuus on sama kuin luonnollisten lukujen joukon mahtavuus. 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, mertitään niiden mahtavuutta kardinaaliluvulla <math>\aleph_0 = \infty </math> (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 <math>\aleph_0 < \aleph_1 < \aleph_2 < ... </math>. Suurempien joukkojen etsintä tuotti tulosta, kun hän osoitti reaalilukujen olevan suurempi joukko. Vieläkään ei tiedetä, onko reaalilukujen kardinaliteetti <math>\aleph_1</math> tai <math>\aleph_2</math> vai jokin muu. Toistaiseksi reaalilukujen kardinalilukuna käytetään merkintää ''c'' tai ''C'' (engl. continuum) tai joskus <math>\beth_1</math> (lue: "beth"-1) ja se oli ensimmäinen todettu [[ylinumeroituva]]sti ääretön lukujoukko. Koska ylinumeroituva lukujoukko on mahtavampi kuin numeroituva joukko, on sen kardinaaliluku aina ääretön. ===Mahtavuuden ymmärtäminen=== 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 kaikille 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== Määritelmän mukaan luonnolliset luvut <math>\N</math> muodostavat numeroituvasti äärettömän lukujoukon. Voidaan osoittaa, että kaikki osajoukot <math>S \subseteq \N</math> ovat myös numeroituvia. Jos <math>S</math> on numeroituva ja ääretön, on olemassa bijektio <math>f: S \leftrightarrow \N</math> ja joukot ovat yhtä mahtavat <math>S \sim \N</math>. Jos <math>S'</math> ylinumeroituva ja <math>S' \subseteq S</math>, niin myös <math>S</math> on ylinumeroituva. <ref name=brown/> ==Lukujoukkojen mahtavuus== 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 [[pariton\|parittomat luvut]], [[kolmioluku\|kolmioluvut]], [[neliöluku\|neliöluvut]] ja [[alkuluku\|alkuluvut]]. Siis on <math>card(\N) = \aleph_0</math>. Cantor todisti jo 1874, että <math>card(\Z)=card(\Q) = \aleph_0</math>. Ne hän todisti luettelamalla [[kokonaisluku\|kokonaisluvut]] ja [[rationaaliluku\|rationaaliluvut]] tietyn systeemin avulla ja osoitti, että jokaiselle luvulle löytyy pari luonnollisista luvuista. Todistamistavat esitelty artikkelissa [[numeroituva joukko]]. Edelleen Cantor osoitti vuonna 1891 [[reaaliluku\|reaalilukujen]] olevan ylinumeroituvasti ääretön joukko. Koska reaaliluvut koostuvat rationaaliluvuista ja [[irrationaaliluku\|irrationaaliluvuista]], ovat myös irrationaaliluvut ylinumeroituvasti ääretön joukko. Reaaliluvut voidaan jakaa nyös [[algebrallinen luku\|algebrallisiin]] ja [[transkendenttinen luku\|transkendenttisiin]] lukuihin. Algebralliset luvut ovat numeroituvasti ja transkendenttiset luvut ylinumeroituvasti ääretön joukko. <ref name=brown/> ==Katso myös== [[Numeroituva joukko]] [[Ylinumeroituva joukko]] ==Lähteet== {{Kirjaviite \| Tekijä =Fuchs, Walter R. \| Nimeke =Matematiikka \| Suomentaja =Mattila, Pekka \| Vuosi =1968 \| Julkaisupaikka =Länsi-Saksa \| Julkaisija =Kirjayhtymä \| Viitattu = }} * {{Kirjaviite \| Tekijä =Barrow John D. \| Nimeke =Lukujen taivas \| Suomentaja =Vilikko, Risto \| Vuosi =1999 \| Julkaisupaikka =Smedjebacken, Ruotsi \| Julkaisija =Art House \| Tunniste =ISBN 951-884-231-0 \| Viitattu = }} {{viitteet\|viitteet= *<ref name=brown>{{Verkkoviite \| Osoite =http://www.math.brown.edu/~res/MFS/handout8.pdf \| Nimeke =Countable and Uncountable Sets \| Tekijä =Schwartz, Rich \| Tiedostomuoto =pdf \| Selite =luentomoniste \| Ajankohta =2007 \| Julkaisupaikka =Providence \| Julkaisija =Brown University \| Viitattu = \| Kieli ={{en}} }}</ref> }} [[Luokka:Joukko-oppi]]

Ero sivun ”Mahtavuus” versioiden välillä