Tælleligt sæt

Et tælleligt sæt er et uendeligt sæt, hvis elementer kan nummereres med naturlige tal . Mere formelt: en mængde kan tælles, hvis der er en bijektion med et sæt naturlige tal: med andre ord er en tællig mængde en mængde, der i magt svarer til mængden af naturlige tal. I alefhierarkiet er kardinaliteten af et tælleligt sæt angivet ("aleph-nul"). $x$ $X\leftrightarrow \mathbb {N}$ $\aleph _{0}$

Egenskaber

En tællig mængde er den "simpelste" uendelige mængde i følgende betydning: i enhver uendelig mængde er der en tællig delmængde . Faktisk vil vi tilfældigt vælge elementer fra en uendelig mængde og associere tal med dem. Da mængden er uendelig, er der for enhver naturlig et element i det at sammenligne med tallet , hvorfra den konstruerede delmængde ifølge induktionsprincippet . vil være bijektiv med . $1,\,2,\,3,\,\ldots$ $n$ $n+1$ $\mathbb {N}$

Derudover er hver delmængde af en tællig mængde enten finit eller tællig (ikke mere end tællig). Vi opregner elementerne i det oprindelige sæt ved naturlige tal, hvilket er muligt, da det kan tælles. For hvert element ved vi, om det ligger i vores delmængde eller ej. Går vi igennem disse i rækkefølge, hvis det næste element ikke ligger i delmængden, springer vi det over; hvis det lyver, tildel det næste nummer (lad os begynde at nummerere med ). Ved induktionsprincippet vil en delmængde være ækvivalent, hvis den ikke er endelig. Bemærk, at vi, sorteret i rækkefølge, blandt de allerede overvejede elementer, ikke savnede nogen. $en$ $\mathbb {N}$

Også en højst tællig (endelig eller tællig) forening af højst tællelige mængder er højst et tælleligt sæt . Vi opregner elementerne i de kombinerede sæt (sæt en bijektion med ). Hvis der er et endeligt antal begyndelsesmængder , vil vi nummerere elementerne - deres foreninger: Det er let at se på induktionen, at der etableres en bijektion med . I tilfælde af en uendelig forening gælder denne regel ikke, men tilsvarende nummerering er mulig. Det kan visualiseres som følger (yderligere konklusion kan dog formaliseres): lad os skrive elementerne i hvert sæt (ordnet efter tal) i en kolonne. Lad os lave en tabel ud fra disse, hvis kolonner definerer hvert sæt, der er inkluderet i foreningen, og rækkerne - visse numre af hver af dem. Fra det øverste venstre hjørne bliver vi en slange for at omgå hele bordet og nummerere hver celle på vejen. Ved induktion går vi rundt om hele bordet, og den resulterende forening viser sig at være tællig. Generelt set vil selve bordet skulle "bygges" af den samme slange, da det er uendeligt. Elementerne i endelige mængder kan altid tildeles først, hvorved nummereringen forskydes med et eller andet tal. $\mathbb {N}$ $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}$

Det er også let at vise, at det direkte produkt af et endeligt antal på ikke mere end tællelige mængder ikke er mere end tælleligt . Overvej produktet af to sæt, dets tællelighed er etableret ved nummereringen af tabellen svarende til ovenstående, hvis rækker er elementerne i det ene sæt og kolonnerne i det andet. Produktet af et endeligt antal mængder er opdelt i faktorer, som hver vil være produktet af den oprindelige multiplikatormængde og det kartesiske produkt af to mængder. Lad os udvide det endelige produkt fra slutningen: lad os nummerere produktet af to sæt, hvoraf elementerne i det ene vil blive opnået ved at nummerere produktet af to "indkommende" sæt, hvoraf elementerne i det ene vil blive opnået på samme måde . Lad os fortsætte langs rekursionen, som ikke vil lukke, da der er et begrænset antal sæt. Bemærk, at alle numre skal søges ved induktion, og sekventielt udfylde de nødvendige plader på de rigtige steder.

Til sidst , hvis vi tilføjer en finit eller tællig mængde til en uendelig mængde, får vi en mængde, der svarer til originalen [1] . Udsagnets gyldighed er let at vise, hvis vi vælger en tællig delmængde i det oprindelige sæt . Således ,. At knytte sig til højst tælleligt sæt ændrer ikke dets kardinalitet, så for højst tælleligt sæt er det sandt: . $EN$ $B$ $A=(A\setminus B)\kop B\;\leftrightarrow (A\setminus B)\kop \mathbb {N}$ $B$ $C$ $A\kop C=(A\setminus B)\kop (B\kop C)\;\leftrightarrow (A\setminus B)\cup \mathbb {N} \;\leftrightarrow A$

Bemærk, at mængden af alle endelige delmængder af et tælleligt sæt kan tælles . Sættet af endelige delmængder af elementer kan tælles, da det er en delmængde af det kartesiske produkt af de oprindelige mængder. Mængden af alle endelige delmængder er foreningen af endelige delmængder med et vist antal elementer (som kan tælles), det vil sige tælleligt. $n$ $n$

Men mængden af alle delmængder af et tælleligt sæt er kontinuerligt og kan ikke tælles . Lad os vise det faktum i en mere generel forstand, at der ikke er nogen bijektion mellem en bestemt mængde og mængden af alle dens delmængder. Lad os antage det modsatte. Vi vælger sættet af alle elementer i det originale sæt, der ikke er forbundet med sæt, der indeholder dem selv. Sådan er selvfølgelig et element i sættet af alle delmængder. Det kan ikke sammenlignes med noget element, der ligger i det på den ene side (per definition), såvel som med ethvert element, der ikke ligger i det på den anden (fordi ellers ville et sådant element allerede ligge i det). Det sæt, vi har konstrueret, er således tomt, men de delmængder, der indeholder et bestemt element, er altid mere end ét; Det betyder, at korrespondancen ikke er én-til-én. En modsigelse betyder, at antagelsen om eksistensen af en bijektion er forkert.

Eksempler

Tællelige er mængderne af naturlige tal $\mathbb {N}$ , heltal $\mathbb {Z}$ , rationelle tal $\mathbb {Q}$ , algebraiske tal $\mathbb {A}$ . Tællelige er objekter, der er et resultat af rekursive procedurer , især er disse beregnelige tal , aritmetiske tal (som følge heraf kan ringen af perioder også tælles , da hver periode kan beregnes ). Mættet af alle endelige ord over et tælleligt alfabet og sættet af alle ord over et endeligt alfabet kan tælles. Alle objekter, der kan defineres med en en-til-en sammenligning med et tælleligt sæt, kan tælles, for eksempel: enhver uendelig familie af ikke-skærende åbne intervaller på den reelle akse; sættet af alle linjer i planet , som hver indeholder mindst to punkter med rationelle koordinater ; ethvert uendeligt sæt af punkter i planet, hvor alle parvise afstande mellem elementer er rationelle.

Et utalligt sæt er sådan et uendeligt sæt , der ikke kan tælles, sådan er især mængderne af reelle tal $\mathbb {R}$ , komplekse tal $\mathbb {C}$ , quaternioner , Cayley-tal . Således kan ethvert sæt kaldes enten endeligt eller tælleligt eller utalligt. $\mathbb {H}$ $\mathbb O$

Interessante fakta

Ved første øjekast synes det umuligt at etablere en en-til-en-korrespondance mellem f.eks . og , fordi elementerne i det andet sæt, ser det ud til, er dobbelt så mange. Men her har vi at gøre med vores opfattelse af uendelighedsbegrebet , som noget der ingen ende har. Du kan prøve at opfatte denne kendsgerning på følgende, absurde i en vis forstand, eksempel. $\mathbb {N}$ $\mathbb {Z}$

Lad os forestille os, at et hotel med et uendeligt antal værelser blev bygget til et møde i det galaktiske råd, og det skete så, at alle værelser var optaget. I det øjeblik ankom diplomater, som skulle genbosættes. Da der er et tælleligt antal hotelværelser og beboere selv, vil vi foreslå følgende strategi for genbosættelse af nyankomne. Lad os flytte gæsterne fra -th værelse til -th, bor i -th i -th, og så i rækkefølge. I de fraflyttede første værelser vil vi faktisk indkvartere dem, der ankom. Hotellet, da det var fuldt besat, vil dog forblive det. Som det viser sig, var der ingen tomme pladser. En modsigelse findes i fremstillingen af uendelighed som en vis endelighed. Imidlertid er uendeligheden kendetegnet ved netop fraværet af dens ende, med andre ord er uendelighed med tilføjelse af en ende nøjagtig den samme uendelighed. $n$ $en$ $(n+1)$ $2$ $(n+2)$ $n$

Det er også muligt at indpakke i en ret elegant form beviset på fraværet af en bijektion mellem et bestemt sæt og sættet af alle dets delmængder. Lad os kalde det første et sæt mennesker (det kan antages, at handlingerne finder sted i den samme galakse), og det andet et samfund. Lad os antage, at der i hvert samfund er én (og eneste) repræsentant, der kun repræsenterer ham. Lad os kalde helte dem, der repræsenterer et samfund, som de ikke hører til. Det viser sig, at en helt ikke kan repræsentere alle helte. Men en ikke-helt kan heller ikke gøre dette, for ved at begå sådan en heltedåd ville han blive en helt. Derfor var der ingen helte i galaksen, ellers er vores antagelse forkert. Men ikke ethvert samfund kan undvære en helt, så vores antagelse er bestemt forkert. Det viser sig, at der ikke er nogen bijektion

Noter

↑ Brudno, 1971 , s. fjorten.

Litteratur

Brudno A. L. Teori om funktioner af en reel variabel. - M. : Nauka, 1971. - 119 s.