Laskettava setti

Laskettava joukko on ääretön joukko, jonka alkiot voidaan numeroida luonnollisilla luvuilla . Muodollisesti: joukko on laskettava, jos luonnollisten lukujen joukolla on bijektio : toisin sanoen, laskettava joukko on joukko, joka vastaa teholtaan luonnollisten lukujen joukkoa. Alefien hierarkiassa laskettavan joukon kardinaalisuus on merkitty ("aleph-nolla"). $X$ $X\leftrightarrow \mathbb {N}$ $\aleph _{0}$

Ominaisuudet

Laskettava joukko on "yksinkertaisin" ääretön joukko seuraavassa mielessä: missä tahansa äärettömässä joukossa on laskettava osajoukko . Todellakin, valitsemme satunnaisesti alkioita äärettömästä joukosta ja yhdistämme niihin lukuja. Koska joukko on ääretön, siinä on jokaisessa luonnollisessa alkio, jota voidaan verrata numeroon , josta induktioperiaatteella muodostettu osajoukko on bijektiivinen kanssa . ${\näyttötyyli 1,\,2,\,3,\,\ldots }$ $n$ $n+1$ $\mathbb {N}$

Lisäksi jokainen laskettavan joukon osajoukko on joko äärellinen tai laskettava (enintään laskettava). Luetteloimme alkuperäisen joukon alkiot luonnollisilla luvuilla, mikä on mahdollista, koska se on laskettavissa. Jokaisen elementin osalta tiedämme, onko se osajoukkossamme vai ei. Kun nämä käydään läpi järjestyksessä, jos seuraava elementti ei ole osajoukossa, ohitamme sen; jos se valehtelee, anna sille seuraava numero (aloitan numerointi painikkeella ). Induktioperiaatteen mukaan osajoukko on ekvivalentti, jos se ei ole äärellinen. Huomaa, että lajittelemme järjestyksessä jo tarkasteltujen elementtien joukossa, emme missannut yhtään. $yksi$ $\mathbb {N}$

Myös korkeintaan laskettava (äärellinen tai laskettava) enintään laskettavien joukkojen liitto on enintään laskettava joukko . Luetteloimme yhdistettyjen joukkojen elementit (asetetaan bijektio painikkeella ). Jos alkujoukkoja on äärellinen määrä, numeroidaan alkiot — niiden liitot: Induktiosta on helppo nähdä, että bijektio kanssa on perustettu . Äärettömän liiton tapauksessa tämä sääntö ei päde, mutta samanlainen numerointi on mahdollista. Se voidaan visualisoida seuraavasti (lisäpäätelmä voidaan kuitenkin formalisoida): kirjoitetaan jokaisen joukon elementit (numerojärjestyksessä) sarakkeeseen. Tehdään näistä taulukko, jonka sarakkeet määrittelevät jokaisen liittoon kuuluvan joukon ja rivit - kunkin tietyt numerot. Vasemmasta yläkulmasta meistä tulee käärme, joka ohittaa koko taulukon ja numeroi jokaisen matkalla olevan solun. Induktiolla kierretään koko pöytä ja tuloksena oleva liitto osoittautuu laskettavaksi. Yleisesti ottaen pöydän tulee olla "rakentamassa" sama käärme, koska se on ääretön. Äärillisten joukkojen alkiot voidaan aina osoittaa ensin, jolloin numerointia voidaan siirtää jollain luvulla. $\mathbb {N}$ ${\näyttötyyli A,\,B,\,C,\,\ldots }$ $n$ $S$ $s_{1}=a_{1},\;s_{2}=b_{1},\;\ldots ,\;s_{n+1}=a_{2},\;s_{n+ 2 }=b_{2},\;\ldots$ $\mathbb {N}$

On myös helppo osoittaa, että äärellisen määrän, enintään laskettavissa olevan joukon, suora tulo on enintään laskettavissa . Tarkastellaan kahden joukon tuloa, sen laskettavuus määritetään edellä olevan kaltaisen taulukon numeroinnilla, jonka rivit ovat yhden joukon alkioita ja toisen sarakkeet. Äärillisen joukon tulo jaetaan tekijöihin, joista jokainen on alkuperäisen kertojajoukon ja kahden joukon karteesinen tulo. Laajennetaan lopputuloa lopusta: numeroidaan kahden joukon tulo, joista toisen alkiot saadaan numeroimalla kahden "saapuvan" joukon tulo, joista toisen alkiot saadaan samalla tavalla . Jatketaan rekursiota, joka ei sulkeudu, koska joukkoja on äärellinen määrä. Huomaa, että kaikki numerot on etsittävä induktiolla täyttämällä peräkkäin tarvittavat levyt oikeisiin paikkoihin.

Lopuksi , jos lisäämme äärettömään joukkoon äärellisen tai laskettavan joukon, niin saadaan jouko, joka vastaa alkuperäistä [1] . Lausunnon pätevyys on helppo osoittaa, jos valitsemme laskettavan osajoukon alkuperäisestä joukosta . Siten ,. Kiinnitys korkeintaan laskettavaan joukkoon ei muuta sen kardinaalisuutta, joten korkeintaan laskettavalle joukolle se pitää paikkansa: . $A$ $B$ $A=(A\setminus B)\cup B\;\leftrightarrow (A\setminus B)\cup \mathbb {N}$ $B$ $C$ $A\cup C=(A\setminus B)\cup (B\cup C)\;\leftrightarrow (A\setminus B)\cup \mathbb {N} \;\leftrightarrow A$

Huomaa, että laskettavan joukon kaikkien äärellisten osajoukkojen joukko on laskettava . Elementtien äärellisten osajoukkojen joukko on laskettavissa, koska se on alkuperäisten joukkojen karteesisen tulon osajoukko. Kaikkien äärellisten osajoukkojen joukko on äärellisten osajoukkojen liitto tietyllä määrällä alkioita (jotka ovat laskettavissa), eli laskettavissa. $n$ $n$

Laskettavan joukon kaikkien osajoukkojen joukko on kuitenkin jatkuva , eikä se ole laskettavissa . Osoittakaamme se tosiasia yleisemmässä mielessä, että tietyn joukon ja sen kaikkien osajoukkojen joukon välillä ei ole bijektiota . Oletetaan päinvastoin. Valitsemme joukon kaikista alkuperäisen joukon elementeistä, joita ei ole liitetty itsensä sisältäviin joukkoihin. Sellainen on tietysti kaikkien osajoukkojen joukon elementti. Sitä ei voi verrata mihinkään elementtiin, joka sijaitsee siinä toisella puolella (määritelmän mukaan), eikä mihinkään elementtiin, joka ei ole siinä toisella puolella (koska muuten sellainen elementti olisi jo siinä). Näin ollen rakentamamme joukko on tyhjä, mutta tietyn alkion sisältäviä osajoukkoja on aina enemmän kuin yksi; Tämä tarkoittaa, että kirjeenvaihto ei ole henkilökohtaista. Ristiriita tarkoittaa, että oletus bijektion olemassaolosta on virheellinen.

Esimerkkejä

Laskettavia ovat joukot luonnollisia lukuja $\mathbb {N}$ , kokonaislukuja $\mathbb {Z}$ , rationaalilukuja $\mathbb {Q}$ ja algebrallisia lukuja $\mathbb {A}$ . Laskettavia ovat rekursiivisista toimenpiteistä johtuvia objekteja , erityisesti nämä ovat laskettavia lukuja , aritmeettisia lukuja (tämän seurauksena jaksojen rengas on myös laskettava , koska jokainen jakso on laskettavissa ). Kaikkien äärellisten sanojen joukko laskettavan aakkoston yli ja kaikkien äärellisten aakkosten sanojen joukko ovat laskettavissa. Kaikki objektit, jotka voidaan määrittää yksi-yhteen-vertailulla laskettavan joukon kanssa, ovat laskettavissa, esimerkiksi: mikä tahansa ääretön perhe ei-leikkaavia avoimia intervalleja reaaliakselilla; tason kaikkien suorien joukko , joista jokainen sisältää vähintään kaksi pistettä , joilla on rationaaliset koordinaatit ; mikä tahansa ääretön joukko tasossa olevia pisteitä, joiden kaikki elementtien väliset parivälit ovat rationaalisia.

Laskematon joukko on sellainen ääretön joukko , joka ei ole laskettavissa, sellaisia ovat erityisesti joukot reaaliluvut $\mathbb {R}$ , kompleksiluvut $\mathbb {C}$ , kvaternionit , Cayley-luvut . Siten mitä tahansa joukkoa voidaan kutsua joko äärelliseksi, laskettavaksi tai laskemattomaksi. $\mathbb {H}$ $\mathbb O$

Mielenkiintoisia faktoja

Ensi silmäyksellä näyttää mahdottomalta muodostaa yksi-yhteen vastaavuus esimerkiksi , ja välillä , koska toisen joukon elementtejä näyttää olevan kaksi kertaa enemmän. Mutta tässä on kyse käsityksestämme äärettömyyden käsitteestä jonakin, jolla ei ole loppua. Voit yrittää havaita tämän tosiasian seuraavassa, tavallaan absurdissa esimerkissä. $\mathbb {N}$ $\mathbb {Z}$

Kuvitellaan, että galaktisen neuvoston kokousta varten rakennettiin hotelli, jossa oli ääretön määrä huoneita, ja niin tapahtui, että kaikki huoneet olivat varattu. Sillä hetkellä saapui diplomaatteja, jotka piti sijoittaa uudelleen. Koska hotellihuoneita ja itse asukkaita on lukematon määrä, ehdotamme seuraavaa strategiaa uusien tulokkaiden uudelleensijoittamiseen. Siirretään vieraat -: nnesta huoneesta -: nteen, -:nneen -: nteen asumaan ja sitten järjestyksessä. Vapautuneisiin ensimmäisiin huoneisiin itse asiassa majoitamme saapuneet. Hotelli pysyy kuitenkin sellaisena kuin se oli täysin käytössä. Kuten kävi ilmi, tyhjiä paikkoja ei ollut. Ristiriita löytyy äärettömyyden esittämisestä tiettynä rajallisuutena. Äärettömyydelle on kuitenkin ominaista nimenomaan sen pään puuttuminen, toisin sanoen äärettömyys loppusummalla on täsmälleen sama ääretön. $n$ $yksi$ $(n+1)$ $2$ ${\näyttötyyli (n+2)}$ $n$

On myös mahdollista kääriä melko eleganttiin muotoon todiste siitä, että tietyn joukon ja sen kaikkien osajoukkojen välillä ei ole bijektiota . Kutsukaamme ensimmäistä ihmisjoukoksi (voidaan olettaa, että toimet tapahtuvat samassa galaksissa) ja toista yhteiskunnaksi. Oletetaan, että jokaisessa yhteiskunnassa on yksi (ja ainoa) edustaja, joka edustaa vain häntä. Kutsukaamme sankareita niitä, jotka edustavat yhteiskuntaa, johon he eivät kuulu. Osoittautuu, että sankari ei voi edustaa kaikkia sankareita. Mutta ei-sankari ei myöskään voi tehdä tätä, koska tekemällä tällaisen sankariteon hänestä tulisi sankari. Siksi galaksissa ei ollut sankareita, muuten oletuksemme on väärä. Mutta jokainen yhteiskunta ei tule toimeen ilman sankaria, joten olettamuksemme on varmasti väärä. Kävi ilmi, ettei mitään bijektiota ole

Muistiinpanot

↑ Brudno, 1971 , s. neljätoista.

Kirjallisuus

Brudno A. L. Reaalimuuttujan funktioiden teoria. - M .: Nauka, 1971. - 119 s.