Avaa päävalikko

Muutokset

9 390 merkkiä lisätty ,  7 vuotta sitten
ei muokkausyhteenvetoa
'''Ylinumeroituva joukko''' on [[matematiikka|matematiikassa]] [[joukko-oppi|joukko-opin]] termi ja se tarkoittaa joukkoa, joka ei ole [[numeroituva joukko|numeroituva]]. KansantajuisestiSiinä ylinumeroituvuuson tarkoittaasilloin sitä, ettämerkittävästi joukonenemmän alkioita eikuin voinumeroituvassa järjestääjoukossa (mahdollisestieli loputtomaksi)se jonoksi.on [[mahtavuus|mahtavampi]] joukko.
 
Koska numeroituva joukko voi olla alkiomäärältään joko äärellinen tai [[ääretön]], on näitä joukkoja mahtavampi joukko aina alkiomäärältään ääretön. Kansantajuisesti ilmaistuna numeroituvasti ääretön joukko sisältää aina "yhtä monta alkiota" kuin luonnollisten lukujen joukko <math>\mathbb{N} = \{1,2,3,...\}</math>, on ylinumeroituvassa joukossa huomattavasti enemmän lukuja. Numeroituvuus voidaan todeta asettamalla tutkittavan joukkon alkiot yksi kerrallaan pariksi [[luonnollinen luku|luonnollisten lukujen]] alkioiden kanssa siten, että kaikki joukon alkiot tulevat käsiteltyä yhden kerran. Ylinumeroituvan joukon alkioita on niin paljon, ettei sen alkioita pystytä edes luettelemaan missään järjestyksessä, jotta parinmuodostusta voisi suorittaa.
Numeroituvuus tarkoittaa, että joukon [[mahtavuus]] on äärellinen tai numeroituvasti ääretön. Tästä seuraa, että kaikki ylinumeroituvat joukot ovat äärettömiä. Ylinumeroituvan joukon mahtavuus on aidosti suurempi kuin <math>\aleph_0</math>, [[luonnollinen luku|luonnollisten lukujen]] joukon mahtavuus.
 
Numeroituvuuden termin otti käyttöön [[joukko-oppi|joukko-opin]] luoja [[Georg Cantor]] vuonna 1874 julkaistussa kirjoituksessaan ja hän todisti sillä monien joukkojen mahtavuuden ollevan saman kuin luonnollisten lukujen joukolla. Vuonna 1891 hän keksi menetelmän osoittaa [[reaaliluku|reaaliluvut]] ylinumeroiluvasti äärettömäksi joukoksi.
 
==Määritelmä==
Joukko <math>\mathrm{S}</math> on ylinumeroituva, jos se ei ole äärellinen tai numeroituvasti ääretön joukko. Ylinumeroituvuuden osoittaminen on yleisessä tapauksessa vaikeaa, vaikka joitakin helppoja tapauksia tunnetaankin.
 
===Merkintä===
Joukon <math>\mathrm{S}</math> mahtavuutta merkitään matematiikan kirjallisuudessa joko <math>card ( S )</math> tai <math>| S |</math>. Joukkojen mahtavuuden suuruus ilmaistaan [[hebrea|hebreankielen]] aakkosilla <math>\aleph</math> tai <math>\beth</math>, joka lausutaan ''"alef"'' ja '''"beth"''. Numeroituvan joukon <math>\mathrm{S}</math>, kuten myös luonnollisten lukujen joukon <math>\mathbb{N}</math>, mahtavuutta merkitään [[kardinaaliluku|kardinaaliluvulla]] <math>card ( \mathrm{S} )=card ( \mathbb{N} )=\aleph_0</math>. Tämän arvo on <math>\aleph_0 = \infty</math> ja se on pienin ääretön kardinaaliluku. <ref name=ww2/><ref name=ww1/>
 
Jos joukko on ylinumeroituva, ilmaistaan joukon mahtavuus kardinaaliluvuilla <math>\aleph_1</math> tai <math>\aleph_2</math> tai ..., missä kaikki kardinaaliluvut ovat <math>\aleph_i = \infty</math>, niiden suuremmalla mahtavuudella, riippuen ylinumeroituvuuden laadusta. Kardinaaliluvuilla on suuruusjärjestys <math>\aleph_0 < \aleph_1 < \aleph_2 < ... .</math> <ref name=ww3/>
 
Cantorin ajatus oli, että mahtavuudeltaan pienin ylinumeroituvalla joukolla olisi kardinaaliluku <math>\aleph_1</math><ref name=ww3/>. Kun hän osoitti reaaliluvut ylinumeroituvaksi joukoksi, oletti hän aluksi, että reaalilukujen kardinaaliluku olisi <math>\aleph_1</math>. Tätä ei voitu osoittaa todeksi, joten varmuuden vuoksi kardinaaliluvuksi on otettu <math>\beth_1</math>, joka on <math>\aleph_1 \le \beth_1</math> <ref name=ww4/>.
 
===Ylinumeroituvuuden toteaminen funktion kuvauksesta===
Joukko ''<math>\mathrm{S''}</math> on ylinumeroituva jos ja vain jos ei ole olemassa [[surjektiofunktio|kuvaus]]ta
:<math>f\colon \mathbbmathrm{NS} \to S \mathbb{N}</math>
on ainoastaan [[injektio]]. Jos kuvaus on [[bijektio]], on joukko <math>\mathrm{S}</math> numeroituva.
 
===Yleisiä tuloksia===
Jos joukon <math>\mathrm{S}</math> osajoukko <math>\mathrm{S'}</math> on ylinumeroituva, niin myös joukko <math>\mathrm{S}</math> on ylinumeroituva.
 
Jos joukko <math>\mathrm{S}</math> on ylinumeroituva ja
:<math>f\colon \mathrm{S} \to \mathrm{T}</math>
on ''bijektio'', niin silloin myös <math>\mathrm{T}</math> on ylinumeroituva. <ref name=austin/><ref name=brown/>
 
==Esimerkkejä ylinumeroituvasti äärettömistä joukoista==
===Reaaliluvut===
Ensimmäinen todistelu reaalilukujen <math>\mathbb{R}</math> ylinumeroituvuudesta esitti Cantor vuonna 1891 julkaisussa ''Über eine elementare Frage der Mannigfaltigkeitslehre''. Tämä kuuluisa todistus tunnetaan nimellä [[Cantorin diagonaaliargumentti]]. Hän tarkasteli lukuvälin <math>\left ( 0, 1 \right )</math> lukuja ja huomasi, ettei niitä pystytä esittämään luettelomuodossa. Jos sitä yritetään, voidaan helposti luoda desimaaliluku, joka puuttuu esitetystä luettelosta. Näin ollen numeroituvuutta ei ole ja väli <math>\left ( 0, 1 \right )</math> on ylinumeroituvasti ääretön. Koko reaalilukujen joukko on nyt ylinumeroituva, koska sen osajoukko <math>\left ( 0, 1 \right )</math> on ylinumeroituva. Reaaliluvut ovat ylinumeroituva joukko myös siksi, että voidaan myös määrittää ''bijektio''
:<math>f\colon \left ( 0, 1 \right ) \to \mathbb{R},</math>
missä bijektiona on esimerkiksi <math>f(x)=\tan \left ( \pi x - \frac{\pi}{2} \right ).</math> <ref name=austin/>
 
Reaalilukujen mahtavuuden määrittäminen on ollut ongelmallista niin sanotun [[kontinuumihypoteesi]]n epämääräisyyden vuoksi. Siksi reaalilukujen kardinaaliluvuksi on merkitty <math>\beth_1</math>, joka on suurempi tai yhtäsuuri kuin pienimmän ylinumeroituvan joukon kardinaaliluku <math>\aleph_1.</math> Eräs tulos kardinaaliluvulle saadaan, kun ajatellaan reaalilukujen joukon olevan yhtä mahtava kuin äärettömästi numeroituvan joukon osajoukkojen joukko. Tällöin reaalilukujen mahtavuus voidaan ilmaista <math>\aleph_0</math>:n avulla <math>\beth_1=2^{\aleph_0}.</math> <ref name=ww4/>
 
===Transkendenttiluvut===
[[transkendenttiluku|Transkendenttiluvut]] ovat sellaisia reaalilukuja, jotka eivät ole [[algebrallinen luku|algebrallisia lukuja]]. Jos kerran algebralliset luvut on osoitettu olevan numeroituvasti ääretön joukko, ovatko tarnskendenttiluvut sitten ylinumeroituva joukko? Tällöin reaalilukujen ylinumeroituvuus johtuisi sen osajoukkona olevan transkendenttilukujen joukon ylinumeroituvuudesta.
 
Tämän voi todistaa epäsuorasti. Olkoon <math>\mathrm{A}</math> algebralliset luvut ja <math>\mathrm{T}</math> transkendenttiluvut, jolloin <math>\mathbb{R} = \mathrm{A} \cup \mathrm{T}</math>. Koska <math>\mathrm{A}</math> on numeroituva joukko, niin <math>\mathbb{R}</math> tulisi olla numeroituva joukko, jos <math>\mathrm{T}</math> on numeroituva. Koska <math>\mathbb{R}</math> on kuitenkin ylinumeroituva, täytyy <math>\mathrm{T}</math> olla myös ylinumeroituva. <ref name=brown/>
 
===Reaalijoukkojen karteesinen tulo===
[[Karteesinen tulo]] <math>\mathbb{R} \times \mathbb{R}</math> voidaan tulkita [[koordinaatisto]]n ''xy''-tasoksi, jossa jokainen tason piste on kahden reaaliluvun koordinaattipari. Onko tässä joukossa enemmän pisteitä kuin suoralla, jota edustaa koordinaattiakseli? Ei ole, vaan molemmilla joukoilla on sama kardinaaliluku.
 
Tämä voidaan osoittaa keksimällä ''bijektio''
:<math>f\colon \left ( 0, 1 \right ) \to \left ( 0, 1 \right ) \times \left ( 0, 1 \right ) ,</math>
jolloin kuvauksen lähtö- ja maalijoukolla on sama kardinaaliluku. Aiemmin todettiin, että joukolla
<math>\left ( 0, 1 \right )</math> on sama kardinaaliluku kuin reaalijoukolla. Samasta syystä myös joukolla <math>\left ( 0, 1 \right ) \times \left ( 0, 1 \right )</math> on sama kardinaaliluku kuin <math>\mathbb{R} \times \mathbb{R}</math>, koska se on jälkimmäisen osajoukko.
 
Kaikilla karteesiset tuloilla <math>\mathbb{R} \times \mathbb{R}\times ...\times\mathbb{R}</math>, johon osallistuu numeroituvasti ääretön määrä reaalilukujoukkoja, on sama kardinaaliluku kuin reaaliluvuilla. <ref name=austin/>
 
===Joukon osajoukkojen joukko <math>\mathcal{P}(\mathbb{S})</math>===
[[Cantorin lause]]essa, jonka hän julkaisi vuonna 1891, hän väittää, että joukon osajoukkojen joukko on mahtavampi kuin joukko itse. Tämä siksi, ettei ole olemassa bijektiota joukosta <math>S</math> [[potenssijoukko]]on <math>\mathcal{P}(\mathbb{S})</math>. Tämä tarkoittaa, että potenssijoukon mahtavauus ylittää selvästi oman joukon <math>S</math> mahtavuuden.
 
Äärettömästi numeroituvan joukon osajoukkojen joukko on yhtä mahtava kuin <math>\mathbb{R}</math>. Ylinumeroituva joukko on kaikkien luonnollisten lukujen joukon osajoukkojen joukko eli luonnollisten lukujen joukon potenssijoukko <math>\mathcal{P}(\mathbb{N})</math>. Sen kardinaaliluku on <math>card(\mathcal{P}(\mathbb{N})) = card(\mathbb{R}) = \beth_1</math>.
 
Mikäli reaaliluvuista muodostaa potenssijoukon <math>\mathcal{P}(\mathbb{\R})</math>, tulee sen mahtavuudesta vielä suurempi. Sen kardinaaliluku merkitään <math>card(\mathcal{P}(\mathbb{R})) = \beth_1</math>.
 
Potenssijoukkoja voidaan muodostaa edellisestä potenssijoukosta loputtomasti. Näiden kardinaaliluvut kasvavat <math>\beth_1 < \beth_2 < \beth_3 < ...</math>. <ref name=brown/><ref name=austin/>
 
===Ylinumeroituvan joukon funktiot===
Joukko ''S'' on ylinumeroituva jos ja vain jos ei ole olemassa [[surjektio]]ta
[[Funktio]]iden <math>f: \mathbb{R}\rightarrow \mathbb{R}</math> joukko on ylinumeroituva. Tämän joukon kardinaaliluku on vielä reaalilukujenkin kardinaliteettia suurempi. Funktioita voidaan muodostaa kaikille reaalilukujen osajoukoille, mikä johtaa potenssijoukkojen mahtavuuteen. Funktioiden joukon mahtavuutta merkitään siksi <math>\beth_2</math>.
:<math>f\colon \mathbb{N} \to S </math>
 
==Katso myös==
Esimerkki ylinumeroituvasta joukosta on [[reaaliluku]]jen joukko <math>\mathbb{R}</math>. Se voidaan todistaa ylinumeroituvaksi [[Cantorin diagonaaliargumentti|Cantorin diagonaaliargumentilla]]; samanlaista tekniikkaa voidaan käyttää myös monien muiden joukkojen ylinumeroituvuuden osoittamiseen. Joukon <math>\mathbb{R}</math>. mahtavuutta merkitään usein <math>\beth_1=2^{\aleph_0}</math>. Toinen ylinumeroituva joukko on kaikkien luonnollisten lukujen joukon osajoukkojen joukko eli luonnollisten lukujen joukon [[potenssijoukko]] <math>\mathcal{P}(\mathbb{N})</math>. Sen voidaan osoittaa olevan yhtä mahtava kuin <math>\mathbb{R}</math>.
*[[Numeroituva joukko]]
 
==Lähteet==
Kaikki ylinumeroituvat joukot eivät kuitenkaan ole samankokoisia. Kolmas esimerkki ylinumeroituvasta joukosta on kaikkien [[funktio]]iden ''f'' : <math>\mathbb{R}</math>.&rarr;<math>\mathbb{R}</math>. joukko. Tämä joukko on vielä reaalilukujenkin joukkoa "ylinumeroituvampi". Sen mahtavuutta merkitään <math>\beth_2</math>, joka on suurempi kuin <math>\beth_1</math>.
*{{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>
*<ref name=ww1>{{Verkkoviite | Osoite =http://mathworld.wolfram.com/CountablyInfinite.html | Nimeke =Countably Infinite | Tekijä =Weisstein, Eric W. | Selite =Math World - A Wolfram Web Resource | Julkaisija =Wolfram Research | Kieli ={{en}} }}</ref>
*<ref name=ww2>{{Verkkoviite | Osoite =http://mathworld.wolfram.com/Aleph-0.html | Nimeke =Aleph-0 | Tekijä =Weisstein, Eric W. | Selite =Math World - A Wolfram Web Resource | Julkaisija =Wolfram Research | Kieli ={{en}} }}</ref>
*<ref name=ww3>{{Verkkoviite | Osoite =http://mathworld.wolfram.com/Aleph-1.html | Nimeke =Aleph-1 | Tekijä =Weisstein, Eric W. | Selite =Math World - A Wolfram Web Resource | Julkaisija =Wolfram Research | Kieli ={{en}} }}</ref>
*<ref name=austin>{{Verkkoviite | Osoite =http://www.ma.utexas.edu/users/mwilliams/cardinality.pdf | Nimeke =Cardinality | Tekijä =Williams, Michael B. | Tiedostomuoto =pdf | Selite =luentomoniste | Ajankohta = | Julkaisupaikka =Texas, USA | Julkaisija =University of Texas at Austin | Kieli ={{en}} }}</ref>
*<ref name=ww4>{{Verkkoviite | Osoite =http://mathworld.wolfram.com/Continuum.html | Nimeke =Continuum | Tekijä =Weisstein, Eric W. | Selite =Math World - A Wolfram Web Resource | Julkaisija =Wolfram Research | Kieli ={{en}} }}</ref>
 
}}
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''.
 
<!-- [[Luokka:Joukko-oppi]] -->
 
[[cs:Nespočetná množina]]
117 943

muokkausta