Keskustelu:Mahtavuus

Jäin miettimään että, eikö pitäisi todistaa myös että NXZ:lta on injektio N:ään eikä vain bijektio (sehän ei ole pelkästään surjektio?) Q:hun? Sellainen injektiohan löytyy kyllä helposti esim. alkulukujen potensseja käyttäen. Se voisi kuvata parin (n,m) luvulle (3 potenssiin n) kertaa (5 potenssiin m) jos m on positiivinen tai nolla. Jos m taas on negatiinvinen, kerrotaan lisäksi 2:lla. Leo Salo 24. marraskuuta 2006 kello 19.50 (UTC)

Todistus on kunnossa, jos oletetaan, että ${\mbox{card}}\mathbb {N} ={\mbox{card}}(\mathbb {Z} \times \mathbb {N} )$. Tämän todistamiseen pitää tarkastaa sekä surjektiivisuus, että injektiivisyys. Mutta jos kahden joukon välillä on bijektio, on niiden välillä taatusti myös injektio. --Matikkapoika 24. marraskuuta 2006 kello 20.16 (UTC)

Koska luonnolliset luvut ovat osa rationaalilukuja on luonnollinen injektio luonnollisilta luvuilta rationaaliluvuille. Silloin rationaalilukujen kardinaliteetti on vähintään luonnollisten lukujen kardinalitetti.

Toisaalta rationaaliluvut voidaan kuvata injektiivisesti luonnollisille luvuille yllä esittämälläni tavalla ja siten rationaalilukujen kardinaliteetti on korkeintaan luonnollisten lukujen kardinaliteetti.

Yhteenvetona seuraa että joukkojen mahtavuus on sama, eli rationaalilukuja on "yhtä paljon" kuin luonnollisia lukuja. Joku voisi muotoilla tämän todistuksen tuohon artikkeliin "Mahtavuus"Leo Salo 30. marraskuuta 2006 kello 17.13 (UTC)

Muotoilin sen itse koska kukaan taitavampi ei sitä näytä tekevän. Toivottavasti joku parantelee esitystä hiukan koska oma taitoni käyttää TeX-iä on puutteellinen.Leo Salo 30. marraskuuta 2006 kello 20.47 (UTC)

OK. Lisäsin yhden tavan todistaa väitteen. --Matikkapoika 30. marraskuuta 2006 kello 21.30 (UTC)

Hetkinen! Onko tuo funktio K injektio? Yksikäsitteinen se kyllä on, mutta injektiivisyys kaipaisi perustelun. Pitäisin omaa todistustani edelleen asiallisesti täsmälleen oikeana (injektiivisyys näkyy välittömästi), mutta sen teknisessä muotoilussa saattoi olla kömpelyyksiä.Leo Salo 1. joulukuuta 2006 kello 07.34 (UTC)

Kyllä se oli injektio. Voit vaikka itse laskea. --Matikkapoika 1. joulukuuta 2006 kello 16.41 (UTC)

Kirjoitin uuden selkeämmän todistuksen, mutta funktion määrittelyssä jostain syystä kohta 4) tuli erilleen yhtä riviä alemmaksi enkä saanut sitä siirrettyä yhtenäisesti samaan "laatikkoon" kuin kohdat 1-3). Yritän korjata joskus myöhemmin,Leo Salo 1. joulukuuta 2006 kello 16.04 (UTC)

Eikö tuon todistamiseen ole jotain tyylikkäämpää tai ainakin yleisempää tapaa (nykyinen itse konstruoitu?). Itse muistan "havainnollistuksen", jossa 2-ulotteisen lukutason ikäänkuin keskipisteestä (0.0) aletaan tekemään laajentuvaa neliö-spiraalia tyyliin (0,0), (0,1),(1,1),(1,0),(1,-1),(0,-1), (-1,-1)... ja näiden järjestys sitten muodostaa sen injektion luonnollisiin lukuihin (bijektion itse asiassa). Tosin tuonkaan esittäminen matemaattisesti ei välttämättä ole kovin yksinkertaista tai selkeää. --ML 1. joulukuuta 2006 kello 16.28 (UTC)

Kyllä sen niinkin voi tehdä. Jonkun matemaatikon mielestä joku todistus on toista kauniimpi. Esimerkiksi Leo Salo halusi oman todistuksen tänne ja poisti minun todistuksen. --Matikkapoika 1. joulukuuta 2006 kello 17.09 (UTC)

Matikkapojan todistuksessa oli osoittaja ja nimittäjä eroteltu parillisin ja parittomin eksponentein, ja tosiaan toimiihan se koska kyseessä ovat tietenkin jaottomat murtoluvut. Anteeksi, en oivaltanut tuota! Ajattelin liikaa oman ideani suuntaan. Myönnän että todistuksesi oli aivan hyvä, eikä sitä olisi ollut syytä poistaa.Se joku lause (kaksiosainen nimi)jolla tuloksen perustelit oli minulle outo, vai sanooko se vain jotain että kardinaliteetti on järjestysrelaatio. Parempi olisi kuitenkin olla viittaamatta johonkin nimettyyn lauseeseen kun se ei tässä ole tarpeen. Minun puolestani todistuksesi voisi hyvin palauttaa. Silti oma todistukseni on (ainakin omasta mielestäni tietysti) myös melko selkeä. Tuo ML:n ehdotus on varmaan myös kehittelemisen arvoinen, mutta sieltä joutuu pudottelemaan pisteitä jollain perusteella pois. Miten yksinkertaisen systeemin siihen keksisi, ei tule heti mieleen. Leo Salo 1. joulukuuta 2006 kello 20.16 (UTC)

Eipä se poisto haittaa. Olen kuitenkin eri mieltä kanssa viittauksesta Cantorin–Schröderin–Bersteinin lauseeseen. Joku artikkelin lukija saattaa tuntea tuon lauseen ja tajuta heti, mihin tuo todistuksen kohta perustuu. Ja vaikka ei tuntisikaan, lukija voi helpommin löytää jostain muualta lauseen todistuksen, kun hän tietää lauseen nimen. Oppiipahan yhden uuden tuloksen lisää. Matematiikassa on hyvä perustella, mihin jokin todistuksen kohta perustuu. Mielestäni lause on vieläpä melko perustulos joukko-opissa. --Matikkapoika 2. joulukuuta 2006 kello 00.12 (UTC)

Lisäsit näköjään artikkelin tuosta lauseesta wikipediaan, niin että nyt minäkin sitten tiedän kenen nimiin tuo sinänsä tuttu tulos merkitään. Hyvä! Olen silti sitä mieltä että tuossa olisi syytä sanoa asia myös sillä tavoin kuin itse sen ilmaisin edellisessä versiossa. Asia tulee heti myös ajatuksellisesti selväksi, eikä vain katsomalla Cantorin ym lausetta ja miettimällä miten sitä sovelletaan tähän kohtaan. On aina hankalaa jos joka pikkuasiassa täytyy siirtyä toiseen hakusanaan. Sinänsä on ollut ihan hauskaa keskustella tästä todistuksesta. On löytynyt jo ainakin kolme mahdollista todistuslinjaa asiaan. Ehkä kirjoista löytyisi lisää, koska kyse on varsin yksinkertaisesta perustuloksesta. Kuten Matikkapoika sanoi jokaisella on tosiaan omat mieltymyksensä ja näin kun pätkittäin tätä juttua on katsellut, niin ainakin huomaan etten (aina turhan hätäisenä) ole riittävän tarkkaan "kuunnellut" muita.Leo Salo 2. joulukuuta 2006 kello 12.12 (UTC)

Minusta mahtavuuksien vartaileminen ei ole ihan triviaali asia. Monikohan yliopiston matikan opiskelija osaisi todistaa, että epäyhtälöistä card A <= card B <= card A seuraa card A = card B? --Matikkapoika 3. joulukuuta 2006 kello 19.57 (UTC)

No, äläs nyt. Vuosia sitten minulla tuli ihan muita tehtäviä tehdessäni mieleen tuo kysymys, ja päälle tunnin miettimisen jälkeen olin itse löytänyt sen standarditodistuksen, joka tuolle esitetään. NettiKirjoittaja 14. kesäkuuta 2009 kello 14.45 (EEST)

Joukkojen vertailtavuus

Cantor-Schröder-Berstein-lauseen (Lisäksi se oli Dedekind, joka ilmeisesti esitti sille ensimmäisen todistuksen.) sijaan tärkeämpää olisi osoittaa se, että kaksi joukkoa ovat aina mahtavuus-vertailtavissa (Toiselta löytyy bijektio toisen osajoukolle, josta erikoistapauksena se, että osajoukko on tämä toinen joukko kokonaan, jolloin joukot ovat yhtämahtavat.). Intuitiivisesti tämän pitäisi pitää paikkansa, koska mahtavuus tuntuu mittaavan joukon kokoa, ja on intuitiivisesti selvää, että kullakin joukolla on koko, jonka suuruutta voi aina vertailla. Kuitenkaan tämän osoittaminen ainakaan ZFC-joukko-opissa ei ole täysin triviaalia, ja olen tämän professorilta ja kirjoistakin varmistanut. Todistus ei kuitenkaan ole mikään kovin syvällinen, mutta ainakin minun näkemäni perustuu ordinaalilukuihin, transfiniittiin induktioon ja Zermelon hyvänjärjestyksen lauseeseen, jotka edelleen ovat aksiomaattisen joukko-opin perusasioita. NettiKirjoittaja 4. maaliskuuta 2009 kello 15.01 (EET)

Oikeastaan tuosta selviää kyllä ilman ordinaalilukuja ja transfiniittia induktiotakin. Joukko-opin kirjoista löytyy yleensä alkusivuilta tulos, jossa osoitetaan seuraava. Jos on kaksi joukkoa A ja B, joilla molemmilla on oma hyvinjärjestyksensä (eli A ja B ovat hyvinjärjestyviä joukkoja), tämä mahtavuusvertailu A:n ja B:n välillä voidaan varmasti tehdä. Nyt tarvitaan siis enää se tieto, että jokaiselle joukolle on olemassa hyvinjärjestys. Tämä on kuuluisa hyvänjärjestyksen-lause. Erästä reaalianalyysin kirjaa selatessani löysin siitä kirjasta tälle lauseelle nerokkaan ja lyhyen todistuksen, jossa osoitetaan kuinka hyvänjärjestyksen-lause seuraa valinta-aksioomasta. Tapana on, että valinta-aksiooma otetaan "annettuna" asiana, joka kuuluu "todellisuuden perusrakenteeseen". NettiKirjoittaja 14. kesäkuuta 2009 kello 14.53 (EEST)