Pitäisi siis osoittaa, että rationaalilukujen joukko on numeroituva. Riittänee siis määritellä bijektio N (positiiviset kokonaisluvut) -> Q (rationaaliluvut). Itse en keksinyt kyllä tuohon sopivaa funktiota.
Todista: Q on numeroituva.
pösilö pasi persreikä
10816
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 10
Vanhimmat
(Positiiviset) rationaaliluvut voidaa laittaa numeroituvaan jonoon osoittajan ja nimittäjän summan mukaan eli
1/1,1/2,2/1,1/3,2/2,3/1,1/4,2/3,3/2,4/1,...
Selvästi jokainen positiivinen rationaaliluku p/q esiintyy jonossa. Pitää vain laskea p q ja etsiä sopivasta kohtaa jonoa.
Jonossa esiintyy monta kertaa sama luku (esim. 1/1=2/2), mutta koska tästä vain seuraa että jonossa on _ainakin_ yhtä monta lukua kuin rationaalilukuja on, niin saadaan itseasiassa vain alkuperäistä tulosta vahvempi tulos.
Luonnollisesti jonoon voidaan laittaa jokaisen positiivisen luvun jälkeen vastaava negatiivinen rationaaliluku ja lyödä 0 jonon alkuun. Tällöin siinä on kaikki rationaaliluvut.
Siis Q on numeroituva.
Kuten alkuperäisessä viestissä todettiinkin, asian todistamiseksi riittää ja tulee löytää bijektio N -> Q. Ylläoleva kyhäelmä ei missään nimessä ole matemaattinen todistus, eikä se ole edes summittaisesti riittävä. Tämä siis alkuperäiselle kysyjälle vinkiksi.
Esitetty todistus on ihan riittävän täsmällinen, ja lisäksi erittäin havainnollinen.
Numeroituvuudessa on viime kädessä kyse rationaalilukujen "järjestämisestä jonoon", ja se on luontevaa tehdä juuri tuolla tavalla.
Jos kuitenkin formaalimman todistuksen välttämättä haluaa, sen saa vaikkapa näin:
f:Q->N, f(a/b)=(2^a)*(3^b)
f on injektio, jolloin Q on bijektiossa joukon N erään osajoukon kanssa. Koska numeroituvan joukon osajoukko on numeroituva, myös Q on numeroituva.
Toteat f:n injektioksi ilman perusteluja. Se ei käy päinsä.
Kuvauksesi on NxN->N, eikä Q->N.
Tässä kommentteja alla oleviin emeritusproffan huolenaiheisiin.
"f:Q->N, f(a/b)=(2^a)*(3^b)
f on injektio, jolloin Q on bijektiossa joukon N erään osajoukon kanssa. Koska numeroituvan joukon osajoukko on numeroituva, myös Q on numeroituva."
Tämä toimii injektiona positiivisilta rationaaliluvuilta luonnollisille luvuille, kunhan vaaditaan että a/b on esitetty muodossa jossa a:lla ja b:llä ei ole yhteisiä tekijöitä. (Aritmetiikan peruslauseen nojalla tällainen esitys rationaaliluvulle on yksikäsitteinen ja siis tällainen kuvaus f on olemassa.)
Niin ikään kuvauksen f injektiivisyys seuraa aritmetiikan peruslauseesta (alkutekijöihin jako on yksikäsitteinen ja 2 sekä 3 ovat alkulukuja):
jos (2^p)*(3^q)=(2^r)*(3^s), niin p=r ja q=s.
(Kun nyt positiiviset rationaaliluvut on näytetty numeroituvaksi joukoksi tämän f:n avulla, niin selvästi koko Qkin on numeroituva. Vai mitä?)
"Ylläoleva kyhäelmä ei missään nimessä ole matemaattinen todistus, eikä se ole edes summittaisesti riittävä."
Joillekin se on matemaattinen ja riittävä. Minulle ainakin kauniimpi ja konkreettisempi kuin "teknisesti" määritelty kuvaus.
***
Jos pitäisi formaalimmin todistaa niin käyttäisin vaikka tietoa että numeroituvien joukkojen numeroituva yhdiste on numeroituva.
Olkoon
A_1={1/1,1/2,1/3,...}
A_2={2/1,2/2,2/3,...}
.
.
.
A_n={n/1,n/2,n/3,...}
.
.
.
Selvästi jokainen A_n on numeroituva
(f_n:A_n->N_ jolla f_n(n/k)=k on bijektio).
Olkoon U yhdiste joukoista A_1,A_2,....
Koska U on numeroituva yhdiste numeroituvista joukoista niin U on numeroituva.
Koska jokainen A_n sisältyy Q_ :aan, niin U sisältyy Q_ :aan. Toisaalta jokainen positiivinen rationaaliluku p/q sisältyy U:hun (koska se sisältyy erääseen joukkoon A_p). Siis U=Q_ ja siten Q_ on numeroituva.
(Vastaavasti myös neg. rationaaliluvut on numeroituva joukko.)
...nyt halua huomata, että kuvauksesi on itseasiassa N x N -> N. Paljonhan noissa sinun esimerkeissä on totta, mutta ei ne kovin elegantteja ole. Jos pyydetään näyttämään Q numeroituvaksi matemaattisin keinoin, niin ei siinä riitä sanoa, että no otsallahan sen näkee.
Todista ensin, että Q on yhtämahtava kuin N x N ja aseta sitten f: N x N -> N, f(a,b) = 2^a * 3^b. Sitten tuossa voisi ollakin jotain järkeä
"kuvauksesi on itseasiassa N x N -> N"
Kuvaukseni f:Q_ -> N on siis seuraava:
positiivista rationaalilukua r vastaa (yksikäsitteinen) esitysmuoto kahden positiivisen luonnollisen luvun suhteena r=p/q. Käytetään tätä muotoa hyväksi ja kuvataan
f(r)=(2^p)*(3^q).
Kyllä se on injektio ja ihan juuri Q_ :lta N:lle.
Eleganttius olkoon mielipideasia...
"Todista ensin, että Q on yhtämahtava kuin N x N ja aseta sitten f: N x N -> N, f(a,b) = 2^a * 3^b."
Vaikka niinkin...
Eli samaistetaan Q_ niiden NxN:n parien (n,k) kanssa, joilla n:llä ja k:lla ei ole yhteisiä tekijöitä. (Vastaavuus on luonnollisesti
p/q (p,q), kun syt(p,q)=1.)
Ja koska Q_ :lta on siis injektio NxN:lle ja NxN:ltä edelleen N:lle (vaikka se (a,b)->2^a*3^b), niin Q_ :lta on injektio N:lle, joten Q_ on numeroituva. (Näin tullaan käyttämään juuri alkuperäistä kuvausta f, se on vain nyt koottu kahdessa osassa.)
"positiivista rationaalilukua r vastaa (yksikäsitteinen) esitysmuoto kahden positiivisen luonnollisen luvun suhteena r=p/q",
kun vaaditaan että p:llä ja q:lla ei ole yhteisiä tekijöitä (paitsi 1).