Räknebart set

En räknebar mängd är en oändlig mängd vars element kan numreras med naturliga tal . Mer formellt: en mängd är räkningsbar om det finns en bijektion med en mängd naturliga tal: med andra ord, en räknebar mängd är en mängd som i kraft är ekvivalent med mängden naturliga tal. I hierarkin av alefs betecknas kardinaliteten av en uppräkningsbar uppsättning ("aleph-noll"). $X$ $X\leftrightarrow \mathbb {N}$ $\aleph _{0}$

Egenskaper

En räknebar mängd är den "enklaste" oändliga mängden i följande betydelse: i vilken oändlig mängd som helst finns det en räknebar delmängd . I själva verket kommer vi att slumpmässigt välja element från en oändlig mängd och associera tal med dem. Eftersom mängden är oändlig, finns det för alla naturliga ett element i den att jämföra med talet , från vilket, enligt induktionsprincipen , den konstruerade delmängden kommer att vara bijektiv med . $1,\,2,\,3,\,\ldots$ $n$ $n+1$ $\mathbb {N}$

Dessutom är varje delmängd av en räknebar mängd antingen finit eller räknebar (inte mer än räknebar). Vi räknar upp elementen i den ursprungliga mängden med naturliga tal, vilket är möjligt eftersom det är räknebart. För varje element vet vi om det ligger i vår delmängd eller inte. Om vi går igenom dessa i ordning, om nästa element inte ligger i delmängden, hoppar vi över det; om det ljuger, tilldela nästa nummer till det (låt oss börja numrera med ). Enligt induktionsprincipen kommer en delmängd att vara ekvivalent om den inte är finit. Observera att vi, sorterat i ordning, bland de element som redan beaktats, inte missade några. $ett$ $\mathbb {N}$

Dessutom är en högst räknebar (ändlig eller räkningsbar) förening av högst räknebara mängder högst en räkningsbar mängd . Vi räknar upp elementen i de kombinerade uppsättningarna (ställ in en bijektion med ). Om det finns ett ändligt antal initiala mängder kommer vi att numrera elementen — deras fackföreningar: Det är lätt att se från induktionen att en bijektion med är etablerad . I fallet med en oändlig förening gäller inte denna regel, men liknande numrering är möjlig. Det kan visualiseras enligt följande (ytterligare slutsats kan dock formaliseras): låt oss skriva ut elementen i varje uppsättning (ordnad efter siffror) i en kolumn. Låt oss göra en tabell från dessa, vars kolumner definierar varje uppsättning som ingår i unionen, och raderna - vissa nummer av var och en av dem. Från det övre vänstra hörnet kommer vi att bli en orm som går förbi hela bordet och numrerar varje cell på vägen. Genom induktion går vi runt hela bordet och den resulterande föreningen visar sig vara räknebar. Generellt sett måste själva bordet "byggas" av samma orm, eftersom det är oändligt. Elementen i ändliga mängder kan alltid tilldelas först, och därigenom skifta numreringen med något nummer. $\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 är också lätt att visa att den direkta produkten av ett ändligt antal av högst räknebara mängder inte är mer än räknebara . Betrakta produkten av två uppsättningar, dess räknebarhet fastställs genom numreringen av tabellen som liknar ovanstående, vars rader är elementen i en uppsättning och kolumnerna i den andra. Produkten av ett ändligt antal mängder delas in i faktorer, som var och en kommer att vara produkten av den ursprungliga multiplikatormängden och den kartesiska produkten av två mängder. Låt oss utöka slutprodukten från slutet: låt oss numrera produkten av två uppsättningar, varav elementen i den ena kommer att erhållas genom att numrera produkten av två "inkommande" uppsättningar, varav elementen i den ena kommer att erhållas på samma sätt . Låt oss fortsätta längs rekursionen, som inte kommer att stängas, eftersom det finns ett ändligt antal uppsättningar. Observera att alla siffror måste sökas genom induktion, och sekventiellt fylla i de nödvändiga plattorna på rätt ställen.

Slutligen , om vi lägger till en ändlig eller räknebar mängd till en oändlig mängd, då får vi en mängd som motsvarar originalet [1] . Påståendets giltighet är lätt att visa om vi väljer en räknebar delmängd i originalmängden . Alltså ,. Att fästa vid högst räknebar mängd ändrar inte dess kardinalitet, så för högst räknebar mängd är det sant: . $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$

Observera att mängden av alla ändliga delmängder av en räknebar mängd är räknebar . Mängden ändliga delmängder av element kan räknas, eftersom den är en delmängd av den kartesiska produkten av originalmängderna. Mängden av alla finita delmängder är föreningen av finita delmängder med ett visst antal element (som är räknebara), det vill säga räknebart. $n$ $n$

Mängden av alla delmängder av en uppräkningsbar uppsättning är dock kontinuerlig och kan inte räknas . Låt oss visa det faktum i en mer allmän mening att det inte finns någon bijektion mellan en viss mängd och mängden av alla dess delmängder. Låt oss anta motsatsen. Vi väljer uppsättningen av alla element i originaluppsättningen som inte är associerade med uppsättningar som innehåller dem själva. Sådant är naturligtvis en del av uppsättningen av alla delmängder. Det kan inte jämföras med något element som ligger i det på ena sidan (per definition), såväl som med något element som inte ligger i det på den andra (för annars skulle ett sådant element redan ligga i det). Således är mängden vi har konstruerat tom, men delmängderna som innehåller ett visst element är alltid fler än ett; Det betyder att korrespondensen inte är en-till-en. En motsägelse innebär att antagandet om förekomsten av en bijektion är felaktigt.

Exempel

Räknebara är uppsättningarna av naturliga tal $\mathbb {N}$ , heltal $\mathbb {Z}$ , rationella tal $\mathbb {Q}$ , algebraiska tal $\mathbb {A}$ . Räknebara är objekt som härrör från rekursiva procedurer , i synnerhet är dessa beräkningsbara siffror , aritmetiska siffror (som ett resultat är ringen av perioder också räknebar , eftersom varje period är beräkningsbar ). Uppsättningen av alla ändliga ord över ett räknebart alfabet och mängden av alla ord över ett ändligt alfabet är räknebara. Alla objekt som kan definieras med en en-till-en-jämförelse med en räknebar mängd kan räknas, till exempel: vilken oändlig familj av icke-skärande öppna intervall som helst på den reella axeln; uppsättningen av alla linjer i planet , som var och en innehåller minst två punkter med rationella koordinater ; vilken oändlig uppsättning punkter som helst i planet, vars alla parvisa avstånd mellan element är rationella.

En oräknelig mängd är en sådan oändlig mängd som inte är räknbar, i synnerhet uppsättningarna av reella tal $\mathbb {R}$ , komplexa tal $\mathbb {C}$ , quaternions , Cayley-tal . Således kan vilken mängd som helst kallas antingen finit, eller countable, eller uncountable. $\mathbb {H}$ $\mathbb O$

Intressanta fakta

Vid första anblicken verkar det vara omöjligt att upprätta en en-till-en-överensstämmelse mellan, säg , och , eftersom elementen i den andra uppsättningen verkar vara dubbelt så många. Men här har vi att göra med vår uppfattning av begreppet oändlighet , som något som inte har något slut. Du kan försöka uppfatta detta faktum på följande, absurda i en mening, exempel. $\mathbb {N}$ $\mathbb {Z}$

Låt oss föreställa oss att ett hotell med ett oändligt antal rum byggdes för ett möte i det galaktiska rådet, och det hände så att alla rum var upptagna. I det ögonblicket anlände diplomater som behövde vidarebosättas. Eftersom det finns ett oräkneligt antal hotellrum och boende själva kommer vi att föreslå följande strategi för att flytta nyanlända. Låt oss flytta gästerna från -th rummet till -th, bor i -th i -th, och sedan i ordning. I de lediga första rummen kommer vi faktiskt att ta emot de som kommit. Hotellet, eftersom det var fullt upptaget, kommer dock att förbli så. Det visade sig att det inte fanns några tomma platser. En motsägelse finns i framställningen av oändligheten som en viss ändlighet. Men oändligheten kännetecknas just av frånvaron av dess slut, med andra ord, oändlighet med tillägg av ett slut är exakt samma oändlighet. $n$ $ett$ $(n+1)$ $2$ $(n+2)$ $n$

Det är också möjligt att linda in i en ganska elegant form beviset på frånvaron av en bijektion mellan en viss uppsättning och mängden av alla dess delmängder. Låt oss kalla den första en uppsättning människor (det kan antas att handlingarna äger rum i samma galax), och den andra för ett samhälle. Låt oss anta att det i varje samhälle finns en (och enda) representant som endast representerar honom. Låt oss kalla hjältar för de som representerar ett samhälle som de inte hör hemma i. Det visar sig att en hjälte inte kan representera alla hjältar. Men en icke-hjälte kan inte heller göra detta, för genom att begå en sådan hjältedåd skulle han bli en hjälte. Därför fanns det inga hjältar i galaxen, annars är vårt antagande fel. Men inte alla samhällen klarar sig utan en hjälte, så vårt antagande är verkligen fel. Det visar sig att det inte finns någon bijektion

Anteckningar

↑ Brudno, 1971 , sid. fjorton.

Litteratur

Brudno A. L. Teori om funktioner för en reell variabel. - M. : Nauka, 1971. - 119 sid.