Todista: 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.

Emeritusprofessori kirjoitti:

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.

Lue lisää

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.

nääsääjä kirjoitti:

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.

Lue lisää

Toteat f:n injektioksi ilman perusteluja. Se ei käy päinsä.

nääsääjä kirjoitti:

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.

Lue lisää

Kuvauksesi on NxN->N, eikä Q->N.

nääsääjä kirjoitti:

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.

Lue lisää

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ä?)

Emeritusprofessori kirjoitti:

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.

Lue lisää

"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.)

primer kirjoitti:

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ä?)

Lue lisää

...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ä

jukepuke kirjoitti:

...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ä

Lue lisää

"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.)

primer kirjoitti:

"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.)

Lue lisää

"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).