Laskettava sarja

Matematiikassa laskettava joukko on äärellinen joukko tai jos siinä on vastaavuus luonnollisten lukujen kanssa . Tarkemmin sanottuna joukon sanotaan olevan laskettava (tai laskettava), kun se on äärellinen tai kun tämän joukon ja luonnollisten lukujen joukon välillä on bijektio .

Vuonna 1874 Georg Cantor otti käyttöön termin " countable set " , joka erotti joukot , jotka ovat laskettavissa ja jotka ovat lukemattomia . Nykyään laskettavat joukot muodostavat perustan matematiikan haaralle, jota kutsutaan diskreetiksi matematiikaksi.

Määritelmä

Joukko on laskettavissa , jos luonnollisista luvuista on injektiivinen funktio , koska ja välillä on ilmeinen bijektio , ei ole eroa, pidetäänkö 0:ta luonnollisena vai ei; Joka tapauksessa tämä artikkeli noudattaa matemaattisen logiikan vakiosopimusta, jossa a otetaan , eli jokainen n luonnollisista (verkkoalue tai aloitusjoukko) vastaa S:n (kuva- tai saapumisjoukko ) -elementtiä funktion avulla . $Joo$ $F$ $\mathbb {N} =\{0,1,2,3,...\}$ ${\näyttötyyli -}$$\mathbb {N}$$\mathbb {N} 0}=\{1,2,3,...\}$$0\in \mathbb {N}$ $-$$Joo$$F$

${\begin{array}{rccl}f:&S&\longrightarrow &N\end{array}}$

Jos funktio sattuu olemaan myös surjektiivinen (ja siten bijektiivinen ), niin sitä kutsutaan laskettavaksi äärettömäksi. $F$$Joo$

Toisin sanoen joukko on laskettavasti ääretön, jos sillä on yksi yhteen vastaavuus luonnollisten lukujen joukon kanssa . $\mathbb {N}$

Kuten edellä todettiin, tämä terminologia ei ole universaali. Jotkut kirjoittajat käyttävät laskettavaa siinä merkityksessä, mitä tässä kutsutaan countably infiniteksi , eivätkä ne sisällä äärellisiä joukkoja.

Määritelmän vaihtoehtoisia (vastaavia) muotoja voidaan myös esittää bijektiivisenä funktiona tai surjektiivisena funktiona. Katso alempaa.

Historia

Vuonna 1874 Cantor osoitti ensimmäisessä joukkoteoriaa käsittelevässä artikkelissaan , että reaalilukujen joukko on laskematon, mikä osoitti, että kaikki äärettömät joukot eivät ole laskettavissa. Vuonna 1878 hän käytti yksi-yhteen vastaavuuksia määritelläkseen ja vertaillakseen kardinaalisuutta. Vuonna 1883 hän laajensi luonnolliset luvut niiden äärettömillä järjestysluvuilla ja käytti järjestysjoukkoja tuottaakseen äärettömän joukkoja, joilla oli erilaiset äärettömät kardinaalit. ]

Termin alkuperä

Georg Cantor esitteli laskettavuuden käsitteen vuonna 1874 kirjoittamassaan artikkelissa ​Kaikkien todellisten algebrallisten lukujen järjestelmän ominaisuudesta ​, jossa hän toteaa toisaalta, että todellisten algebrallisten lukujen joukko (ts. joukko reaalilukuja, jotka ovat jonkin polynomiyhtälön ratkaisu rationaalisilla kertoimilla) on laskettavissa, ja toisaalta, että kaikkien reaalilukujen joukko ei ole, mistä se päättelee välittömästi transsendenttisten tai ei -lukujen olemassaolon. -algebrallinen, mikä löytää uudelleen Liouvillen tuloksen .

Sen alkuperä liittyy matematiikan äärettömyyden käsitykseen. Cantorin löytöyn asti äärettömyys oli potentiaalinen äärettömyys , mahdollisuus jatkaa prosessia pysähtymättä koskaan. Äärettömien joukkojen vertailu tuo mukanaan käsitteen saavutetusta , todellisesta tai päättyneestä äärettömyydestä: ääretön joukko nähdään kokonaisuutena, käsite, jonka monet matemaatikot ( Gauss tai Cantorin aikana Kronecker jne.) ovat hylänneet. . Heille se tosiasia, että kohteiden äärettömyyttä tarkastellaan kokonaisuutena, toisin sanoen äärettömän joukon käsitettä , ei ole järkevää, vaan ääretön voi syntyä vain luentaprosessista ilman toistoa, joka ei koskaan pysähdy. . Vain laskettavalla äärettömyydellä voi olla tiukasti merkitystä.

Esittely

Joukko on kokoelma elementtejä , ja sitä voidaan kuvata monella tavalla. Lomake on yksinkertaisesti luettelo kaikista sen elementeistä; Esimerkiksi joukkoa, joka koostuu kokonaisluvuista 3, 4 ja 5, voidaan merkitä {3, 4, 5}. Tämä on kuitenkin tehokasta vain pienille sarjoille; suuremmille sarjoille tämä voi viedä aikaa ja olla virhealtista. Kunkin kohteen luettelemisen sijasta käytetään joskus ellipsiä ("..."), jos kirjoittaja uskoo, että lukija voi helposti arvata, mitä puuttuu; esimerkiksi {1, 2, 3, ..., 100} oletettavasti merkitsee kokonaislukujen joukkoa 1 - 100. Tässäkin tapauksessa on silti mahdollista listata kaikki alkiot, koska joukko on äärellinen .

Jotkut joukot ovat äärettömiä ; näissä joukoissa on enemmän kuin n alkiota mille tahansa kokonaisluvulle n . Esimerkiksi luonnollisten lukujen joukossa, joka on kirjoitettu muodossa {0, 1, 2, 3, 4, 5, ...}, on ääretön määrä elementtejä, emmekä voi käyttää mitään normaalilukua sen koon määrittämiseen. Kuitenkin käy ilmi, että äärettömillä joukoilla on hyvin määritelty käsitys koosta (tai pikemminkin kardinaalisuudesta , joka on joukon elementtien lukumäärän tekninen termi), eikä kaikilla äärettömillä joukoilla ole sama kardinaliteetti.

Kokonaislukujen bijektiivinen esitys yhtä suuriin lukuihin.

Ymmärtääksemme, mitä tämä tarkoittaa, tutkimme ensin, mitä se ei tarkoita . Esimerkiksi on olemassa ääretön määrä parittomia kokonaislukuja, ääretön määrä parillisia kokonaislukuja ja (siis) ääretön määrä kokonaislukuja yleensä. Osoittautuu kuitenkin, että parillisten kokonaislukujen määrä, joka on sama kuin parittomien kokonaislukujen määrä, on myös sama kuin kokonaislukujen määrä yleensä. Tämä johtuu siitä, että jokaiselle paritolle kokonaisluvulle on vastine, parillinen kokonaisluku: ... -2 → -4, -1 → -2, 0 → 0, 1 → 2, 2 → 4, ... Kuvassa Kokonaisluvut ja parilliset luvut järjestetään yksi-yhteen-vastaavuuteen (tai bijektioon ), joka on funktio , joka edustaa kahta joukkoa siten, että kunkin joukon jokainen elementti vastaa yhtä alkiota toisessa joukossa.

Kaikilla äärettömillä joukoilla ei kuitenkaan ole samaa kardinaliteettia. Esimerkiksi Georg Cantor (joka esitteli tämän käsitteen) osoitti, että reaaliluvut eivät voi olla yksi-yhteen-vastaavia luonnollisten lukujen (ei-negatiivisten kokonaislukujen) kanssa, ja siksi reaalilukujen joukolla on suurempi kardinaliteetti kuin joukolla. luonnollisista luvuista.

Joukko on laskettava , jos: (1) se on äärellinen tai (2) jos sillä on sama kardinaliteetti (koko) kuin luonnollisten lukujen joukolla. Vastaavasti joukko on laskettava , jos sillä on sama kardinaliteetti kuin jollain luonnollisten lukujen joukon osajoukolla . Muuten se on lukematon .

Yleinen muotoilu ilman yksityiskohtia

Määritelmän mukaan joukko S on laskettavissa , jos on olemassa injektiivinen funktio f  : S → N arvosta S luonnollisten lukujen joukkoon N = {0, 1, 2, 3, ...}.

Saattaa tuntua normaalilta jakaa joukot eri luokkiin: laita kaikki elementin sisältävät joukot yhteen; kaikki joukot, jotka sisältävät kaksi elementtiä yhdessä; ...; koota lopuksi kaikki äärettömät joukot ja pidä niitä samankokoisina. Tämä näkemys ei ole kestävä koon luonnollisen määritelmän puitteissa.

Tämän tarkentamiseksi tarvitsemme bijektion käsitteen . Vaikka bijektio vaikuttaa lukua edistyneemmältä käsitteeltä, tavallinen matematiikan kehitys joukkoteorian kannalta määrittelee funktiot ennen lukuja, koska ne perustuvat paljon yksinkertaisempiin joukkoihin. Tässä tulee esiin bijektion käsite: se määrittelee vastaavuuden

a ↔ 1, b ↔ 2, c ↔ 3

Tämä määrittää bijektion, koska jokainen elementti { a , b, c } vastaa tarkkaa elementtiä {1, 2, 3} ja päinvastoin.

Nyt yleistetään tämä tilanne ja määritellään kaksi samankokoista joukkoa, jos (ja vain jos) niiden välillä on bijektio. Kaikille äärellisille joukoille tämä antaa meille tavallisen ekvivalenttikoon määritelmän . Mitä se kertoo äärettömien joukkojen koosta?

Tarkastellaan joukkoja A = {1, 2, 3, ...}, positiivisten kokonaislukujen joukkoa ja B = {2, 4, 6, ...}, parillisten positiivisten kokonaislukujen joukkoa. Väitämme, että määritelmämme mukaan nämä joukot ovat samankokoisia ja että siksi B on laskettavasti ääretön. Muista, että tämän todistamiseksi meidän on todistettava niiden välinen ristiriita. Mutta tämä on helppoa käyttämällä n ↔ 2 n , joten

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....

Kuten edellisessä esimerkissä, jokainen A:n elementti on yhdistetty B:n elementtiin ja päinvastoin. Siksi ne ovat samankokoisia. Tämä on esimerkki joukosta, joka on samankokoinen kuin yksi sen varsinaisista osajoukoista (jotain mahdotonta äärellisille joukoille).

Samalla tavalla kaikkien järjestellisten luonnollisten lukujen parien joukko on laskettavasti ääretön, kuten voidaan nähdä seuraamalla kuvan kaltaista polkua:

Cantor Matching Function määrittää luonnollisen luvun jokaiselle luonnollisten lukujen parille .

Tuloksena oleva esitys on:

0 ↔ (0,0), 1 ↔ (1,0), 2 ↔ (0,1), 3 ↔ (2,0), 4 ↔ (1,1), 5 ↔ (0,2), 6 ↔ (3,0) ....

Tämä esitys kattaa kaikki järjestetyt parit.

Mielenkiintoista on, että jos käsittelet kutakin paria vulgaarin murto - osan osoittajana ja nimittäjänä , niin kullekin positiiviselle murtoluvulle voimme päätyä eri suureen, joka vastaa sitä. Tämä esitys sisältää myös luonnolliset luvut, koska jokainen luonnollinen luku on myös murto-osa N /1. Tästä syystä voimme päätellä, että positiivisia rationaalilukuja on täsmälleen yhtä monta kuin positiivisia kokonaislukuja. Tämä pätee myös kaikkiin rationaalilukuihin, kuten alla näkyy.

Lause: Äärillisen määrän laskettavien joukkojen karteesinen tulo on laskettava.

Joskus useampi kuin yksi esitys on hyödyllinen. Tässä esität, että joukko, jonka haluat näyttää, on laskettavasti ääretön toisessa joukossa, ja edustaa sitten tätä toista luonnollisten lukujen joukkoa. Esimerkiksi positiiviset rationaaliluvut voidaan helposti osoittaa luonnollisten lukujen pareille (osajoukolle), koska p / q edustaa ( p , q ).

Entä loputtomien laskettavien joukkojen äärettömät osajoukot? Onko näissä vähemmän alkioita kuin N ?

Lause: Jokainen laskettavan joukon osajoukko on laskettava. Erityisesti jokainen laskettavan äärettömän joukon ääretön osajoukko on laskettavan ääretön.

Esimerkiksi alkulukujen joukko on laskettavissa määrittämällä n : nnen alkuluvun n : lle :

• 2 edustaa 1
• 3 edustaa 2
• 5 edustaa 3:a
• 7 edustaa 4:ää
• 11 edustaa 5
• 13 edustaa 6:ta
• 17 edustaa 7:ää
• 19 edustaa 8:aa
• 23 edustaa 9:ää
• ...

Entä joukot, jotka ovat luonnostaan ​​"suurempia" kuin N ? Esimerkiksi kokonaislukujen joukko Z tai rationaalilukujen joukko Q , joka voi intuitiivisesti näyttää paljon suuremmalta kuin N. Mutta ulkonäkö pettää, koska vahvistamme, että:

Lause: Z (kaikkien kokonaislukujen joukko) ja Q (kaikkien rationaalilukujen joukko) ovat laskettavissa.

Samalla tavalla algebrallisten lukujen joukko on laskettavissa. ]

Lause: Mikä tahansa laskettavien joukkojen äärellinen liitto on laskettava. Q voidaan määritellä kaikkien a'/ b -tyypin murtolukujen joukoksi, joissa a ja b ovat kokonaislukuja, joissa b > 0. Tämä voidaan kuvata luonnollisten lukujen ( a , b , c ) järjestettyjen kolmiosien osajoukkoon. siten, että jos a ≥ 0 ja b > 0, a ja b ovat koprimeja ja c ∈ {0, 1} niin c = 0, jos a / b ≥ 0 ja c = 1 muuten.

• 0 tarkoittaa (0,1,0)
• 1 edustaa (1,1,0)
• −1 edustaa (1,1,1)
• 1/2 edustaa (1,2,0)
• −1/2 edustaa (1,2,1)
• 2 edustaa (2,1,0)
• −2 edustaa (2,1,1)
• 1/3 edustaa (1,3,0)
• −1/3 edustaa (1,3,1)
• 3 edustaa (3,1,0)
• −3 edustaa (3,1,1)
• 1/4 edustaa (1,4,0)
• −1/4 edustaa (1,4,1)
• 2/3 edustaa (2,3,0)
• −2/3 edustaa (2,3,1)
• 3/2 edustaa (3,2,0)
• −3/2 edustaa (3,2,1)
• 4 edustaa (4,1,0)
• −4 edustaa (4,1,1)
• ...

Kun tiedämme, että on olemassa laskettavia joukkoja, voimme kysyä, voidaanko tätä viimeistä tulosta jatkaa. Vastaus on "kyllä" ja "ei", voimme laajentaa sitä, mutta meidän on oletettava uusi aksiooma tehdäksemme niin.

Lause: ( Olettaessaan laskettavan valinnan aksiooman ) Laskettavan määrän laskettavien joukkojen liitto on laskettava.

Esimerkiksi jos laskettava joukko a , b , c , ...

Laskettavien joukkojen laskettavien määrien luettelointi.

Yllä olevan kolmioenumin muunnelman käyttäminen:

• a ₀ edustaa 0 :ta
• a ₁ on 1
• b ₀ on 2
• a ₂ on 3
• b ₁ on 4
• c ₀ on 5
• ₃ on 6
• b2 on ₇
• c ₁ on 8
• d ₀ on 9
• ₄ on 10
• ...

Huomaa , että tämä toimii vain , jos joukot a , b , c , ... ovat disjunktoituja joukkoja . Jos ei, niin liitto on vielä pienempi ja siksi myös luetettavissa jollakin yllä olevista lauseista.

Huomaa myös, että tarvitsemme laskettavan valinnan aksiooman indeksoidaksemme kaikki joukot a , b , c , ... samanaikaisesti.

Lause: Kaikkien luonnollisten lukujen äärellisen pituisten sarjojen joukko on laskettavissa.

Tämä joukko on sellaisten sekvenssien liitto, joiden pituus on 1, pituus 2, pituus 3 ja jotka ovat laskettavia joukkoja (äärellinen karteesinen tulo). Puhumme siis laskettavien joukkojen laskettavasta liitosta, joka on laskettavissa yllä olevan lauseen mukaan.

Lause: Luonnollisten lukujen kaikkien äärellisten osajoukkojen joukko on laskettavissa.

Kun on äärellinen osajoukko, voit järjestää elementit äärelliseen sekvenssiin. On olemassa vain laskettava määrä äärellisiä sekvenssejä, joten myös äärellisiä osajoukkoja on vain laskettava määrä.

Seuraava lause antaa vastaavat formulaatiot bijektiivin tai surjektiivisen funktion suhteen . Todiste tästä tuloksesta löytyy Langin tekstistä.

Lause (perus): Olkoon S joukko. Seuraavat lausunnot ovat vastaavia:

1. S on laskettava, eli on olemassa injektiivinen funktio f  : S → N .
2. Ó S on tyhjä tai siinä on surjektiivinen funktio g  : N → S .
3. Ó S on äärellinen tai siinä on bijektio h  : N → S .

Cantorin lause sanoo, että jos A on joukko ja P ( A ) on sen potenssijoukko , eli a:n kaikkien osajoukkojen joukko , ei ole surjektiivista funktiota A :sta P :hen ( A ). Todiste annetaan artikkelissa Kantorin lause . Tämän ja edellisen peruslauseen välittömänä seurauksena meillä on:

Lause: Joukko P ( N ) ei ole laskettavissa; eli se on lukematon .

Lisätietoja tästä tuloksesta on Cantorin diagonaaliargumentissa.

Reaalilukujen joukko on laskematon (katso Cantorin ensimmäinen todiste laskemattomuudesta ), ja niin on myös kaikkien luonnollisten lukujen äärettömien sarjojen joukko.

Joitakin teknisiä yksityiskohtia

Edellisessä osiossa esitetyt ilmoitukset perustuvat tiettyjä ominaisuuksia omaavien funktioiden olemassaoloon. Tässä osiossa esitellään tämän artikkelin yleisimmin käytetyt funktiot, mutta ei tarkisteta, että näillä funktioilla on vaaditut ominaisuudet. Peruslausetta käytetään usein todisteiden yksinkertaistamiseen. Huomaa, että N tässä lauseessa voidaan korvata millä tahansa laskettavasti äärettömällä joukolla.

Lausunto: Mikä tahansa äärellinen joukko on laskettavissa.

Todistus: Määritelmän mukaan ei-tyhjän äärellisen joukon S ja joukon {1, 2, ..., n } välillä on bijektio mille tahansa positiiviselle luonnolliselle luvulle n . Tämä funktio on S :n injektio N :ään .

Lause: Mikä tahansa laskettavan joukon osajoukko on laskettavissa. ]

Todistus : Injektiofunktion rajoittaminen sen toimialueen osajoukkoon on edelleen injektiivinen.

Lause: Jos S on laskettava joukko ja x ∉ S , niin S ∪ { x } on laskettava. ]

Todistus: Olkoon f : S → N injektio, määritä g : S ∪ { x } → N kun g ( x ) = 0 ja g ( y ) = f ( y ) + 1 kaikille S :n y : ille . Tämä funktio g on injektio.

Lause: Jos A ja B ovat laskettavia joukkoja, niin A ∪ B ovat laskettavia. ]

Todistus: Olkoot f : A → N ja g : B → N injektiot, määrittele uusi injektio h : A ∪ B → N kun h ( x ) = 2 f ( x ) , jos x on A: ssa ja h ( x ) = 2 g ( x ) + 1 , jos x on B :ssä mutta ei A: ssa .

Lause: Kahden laskettavan joukon A ja B karteesinen tulo on laskettava. ]

Todistus: Huomaa, että N × N on määritelmän mukaan laskettavissa, koska funktio f  : N × N → N , jonka f ( m , n ) = 2 ^m 3 ⁿ antaa, on injektiivinen. ​ Sitten seuraa karteesinen perustulolause, jossa kahdella laskettavalla joukolla on laskettava tulo. Jos A ja B ovat laskettavissa, on olemassa subjektioita f  : N → A ja g  : N → B . Niin

f × g  : N × N → A × B

on laskettavan joukon N × N alistaminen joukolle A × B ja tästä seuraa, että A × B on laskettavissa. Tämä tulos yleistää minkä tahansa laskettavien joukkojen äärellisen joukon karteesisen tulon ja todisteen joukon lukumäärän induktiolla .

Lause: Kokonaisluvut Z ovat laskettavissa ja rationaaliluvut Q ovat laskettavissa.

Todistus: Kokonaisluvut Z ovat laskettavissa johtuen funktiosta f  : Z → N , jonka antaa f ( n ) = 2 ⁿ jos n ei ole negatiivinen f ( n ) = 3 ^{− n} jos n on negatiivinen, se on injektiivinen funktio. Rationaaliluvut Q ovat laskettavissa funktion g ansiosta  : Z × N → Q , jonka antaa g ( m , n ) = m /( n + 1) on laskettavan joukon Z × N alistaminen rationaaleille Q.

Lause: Algebralliset luvut A ovat laskettavissa.

Todistus: Koska kaikki algebralliset luvut (mukaan lukien kompleksiluvut) ovat polynomin juuria. Antaa olla polynomi , ja algebrallinen luku on polynomin k :s juuri (ensin lajiteltu absoluuttisen arvon mukaan pienimmästä suurimpaan, sitten lajiteltu argumentin mukaan pienimmästä suurimpaan). Voidaan määritellä injektiivinen (eli yksi yhteen) funktio f  : A → Q , jonka antaa , missä on n : s alkuluku .$a_{0}x^{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots +a_{n}x^{n}$$?$$f(\alpha )=2^{k-1}\cdot 3^{a_{0}}\cdot 5^{a_{1}}\cdot 7^{a_{2}}\cdot \dots \cdot {p_{n+2}}^{a_{n}}\cdot \dots$$p_{n}$

Lause: Jos A _n on laskettava joukko jokaiselle n :lle N :ssä, niin myös kaikkien A _n :n liitto on laskettavissa. ]

Todistus: Tämä on seurausta siitä, että jokaiselle n : lle on olemassa subjektiivinen funktio g _n  : N → A _n ja siksi funktio

$G:\mathbf {N} \times \mathbf {N} \to \bigcup{n\in \mathbf {N} }A_{n},$

G ( n , m ) = g n ( m ) on alistaminen _. Koska N × N on laskettava, seurauksena on, että liitto on laskettava. Käytämme tässä todistuksessa laskettavan valinnan aksioomaa valitaksemme kullekin n :lle N : n alaisuuden g _n ei-tyhjästä joukosta N : stä _An :iin .

Topologinen todiste reaalilukujen laskemattomuudesta on kuvattu äärellisen leikkauksen ominaisuudessa .

Joukkoteorian minimimalli

Jos on joukko, joka on ZFC-joukkoteorian vakiomalli (katso sisäinen malli ), niin ei ole olemassa vähimmäisstandardimallia ( katso rakennettava universumi ). Löwenheim -Skolem-lausetta voidaan käyttää osoittamaan, että tämä minimimalli on laskettava. Tosiasia on, että "laskemattomuuden" käsite on järkevä tässä mallissa, ja erityisesti tämä malli M sisältää elementtejä, jotka ovat:

• M : n osajoukot , joten ne voidaan laskea
• Mutta lukemattomia M :n näkökulmasta

Olemassaolon alkuaikoina tätä teoriaa pidettiin paradoksina (katso Skolemin paradoksi ).

Vähimmäisstandardimalli sisältää kaikki algebralliset luvut ja kaikki tehokkaasti laskettavat transsendentaaliset luvut sekä monia muita lukutyyppejä.

Tilaukset yhteensä

Laskettavat sarjat voidaan tilata kokonaan eri tavoin, esim.

• Hyvällä tilauksella (katso myös järjestysnumero ):
  • Tavallinen luonnollisten lukujen järjestys (0, 1, 2, 3, 4, 5, ...)
  • Kokonaisluvut järjestyksessä (0, 1, 2, 3, ...; -1, -2, -3, ...)
• Muut (ei hyvässä järjestyksessä):
  • Tavallinen kokonaislukujen järjestys (..., -3, -2, -1, 0, 1, 2, 3, ...)
  • Tavallinen rationaalilukujen järjestys (ei voida kirjoittaa nimenomaisesti järjestetyksi listaksi)

Huomaa, että molemmissa hyvän järjestyksen esimerkeissä missä tahansa osajoukossa on pieni elementti ; ja väärinjärjestyksen esimerkeissä joissakin osajoukoissa ei ole pienintä elementtiä . Tämä on keskeinen määritelmä, joka määrittää, onko kokonaistilaus myös hyvä tilaus.

Esimerkkejä

${\begin{array}{|rcr|}\hline n&\longmapto &p\\\hline 1&\longmapto &2\\2&\longmapto &0\\3&\longmapto &4\\4&\longmapto &-2\\ 5&\pitkäkartta &6\\6&\pitkäkartta &-4\\7&\pitkäkartta &8\\8&\pitkäkartta &-6\\\cdots &\longmapsto &\cdots \\\end{array}}$

• Kaikkien parillisten lukujen joukko on laskettavissa, koska funktio:

${\begin{array}{rccl}f:&N&\longrightarrow &P\\&n&\longmapsto &p=f(n)\end{array}}$

$f(n)={\begin{cases}p=n+1&,\;if:&n{\teksti{ on pariton}}\\p=2-n&,\;jos:&n{\teksti{ on parillinen}}\loppu{tapaukset}}$

on bijektio : jokainen luonnollinen luku vastaa yhtä parillista lukua ja päinvastoin.

• Kaikkien kokonaislukujen joukko on myös laskettavissa.$\mathbb{Z}$
• Myös kaikkien rationaalilukujen joukko on laskettavissa. ]$\mathbb{Q}$
• Sarja on laskettava.$\mathbb {N} \times \mathbb {N}$
• Edellisestä väittämästä seuraa, että myös kaikkien rationaalien joukko on laskettavissa, kun otetaan huomioon, että , jossa ei sisällä arvoa 0 .$\mathbb {N} \times \mathbb {N'} =\mathbb {Q}$$\mathbb {N'}$
• Induktiolla voidaan osoittaa, että ne ovat laskettavissa mille tahansa luonnolliselle luvulle k .$\mathbb {N}<k},\mathbb {Z}<k},\mathbb {Q}<k}$

Katso myös

• Järjestysluku (joukkoteoria)
• Alef (kardinaalit)
• Kreivi
• perusluku
• Hilbertin hotelliparadoksi
• rajallinen joukko
• ääretön joukko
• kompakti tila
• lukematon joukko
• Continuum hypoteesi

Ulkoiset linkit

• Tämä teos sisältää täydellisen käännöksen, joka on johdettu englanninkielisen Wikipedian " Countable set " -julkaisusta, erityisesti tästä versiosta , jonka sen julkaisijat ovat julkaisseet GNU Free Documentation -lisenssillä ja Creative Commons Attribution-ShareAlike 3.0 Unported License -lisenssillä .