I matematikk sies et sett å være tellbar eller uendelig , når elementene kan oppføres uten utelatelse eller repetisjon i en sekvens indeksert av heltall . Enkelte uendelige sett inneholder tvert imot "for mange" elementer til å bli fullstendig dekket av uendelig av heltall og sies derfor å være "utallige".
Det er to bruksområder for ordet "tellbar" i matematikk, avhengig av om en inkluderer blant de tellbare settene endelige sett , hvis elementer kan nummereres med positive heltall mindre enn en gitt verdi . Det er først når vi forstår de endelige mengdene blant de tellbare settene, at det er nyttig å spesifisere tellbar uendelig .
Georg Cantor er den første som bruker dette begrepet, i en artikkel publisert i 1874, som markerer fødselen av mengde teori . Men viktigheten av det tellbare manifesterer seg i mange områder av matematikken, spesielt i analyse , målingsteori og topologi .
Det er to definisjoner av "tellbar" i matematikk som ikke er likeverdige.
I henhold til den første, et sett E sies å være tellbar når det er et Bijeksjon mellom settet N av naturlige tall og E (vi si at det er ekvipotent til settet N av naturlige heltall). Dette er Cantors opprinnelige definisjon .
I følge det andre sies et sett E å være tellbart når det er i tilknytning til en del av N , som tilsvarer å tilføye settene i sammenheng med N de endelige mengdene, hvilken som helst delmengde av N er endelig eller tellbar. Et sett ekvipotent med N kalles da " tellbar uendelig mengde ".
Valget er tatt i resten av artikkelen å ta i bruk den første definisjonen, selv om vi noen ganger spesifiserer "utallige uendelige sett" som er entydige uansett hvilken definisjon som brukes. Settene i kombinasjon med en delmengde av N blir da kalt "mest tellbare sett" eller "endelige eller tellbare sett". En hel (uendelig) utallige, er en uendelig sett som ikke er like potente N . Det argumentet Cantor diagonal kan vise at all reell og alle deler av N er ikke tellbar, men også at det er "mange" andre ikke-tellbar uendelig.
Et sett som inneholder et tellbart uendelig sett er nødvendigvis uendelig , dvs. det er ikke likeverdig med noe avgrenset sett med naturlige heltall. Så snart vi gir oss selv nok aksiomer i mengdeteorien , særlig det valgte aksiomet , viser vi at den teller uendelige er den minste uendelig , i den forstand at ethvert uendelig sett inneholder et telt uendelig sett. Det omvendte utgjør ingen problemer. Vi kan deretter karakterisere et uendelig sett som et sett som inneholder et tellbart sett.
Den kardinal av N , og derfor kardinal av enhver Tellbar, er betegnet ℵ 0 ( aleph-null ). Han er den første av den ordinære rekkefølgen av alephs , som representerer alle de uendelige kardinalene i nærvær av det valgte aksiomet.
Forestillingen ble introdusert av Georg Cantor i en artikkel fra 1874, On a property of the system of all real algebraic numbers , artikkel som markerer fødselen av mengde teori . Vi har opprinnelsen til dette beviset, som ennå ikke er det velkjente ved hjelp av det diagonale argumentet, takket være bokstavene i7. desember og 9. desember 1873fra Georg Cantor til Dedekind , der han på den ene siden fastslår at settet med reelle algebraiske tall (dvs. reelle løsninger av en polynomligning med heltallskoeffisienter) er tellbare, på den annen side at settet med reelle tall ikke er, fra som han umiddelbart utleder eksistensen av transcendente tall (det vil si ikke algebraisk), og finner dermed et resultat av Liouville .
Dens utseende er knyttet til forestillingen om uendelig i matematikk. Inntil Cantor er uendelig potensiell uendelig, muligheten for å fortsette en prosess uten å stoppe. Sammenligningen av uendelige sett antar at det uendelige sies å være fullført, faktisk eller til og med fullstendig: et uendelig sett sett på en helhet, som mange matematikere nektet ( Gauss , eller på tidspunktet for Cantor, Kronecker ). For dem har det ingen betydning å betrakte en uendelig mengde objekter som en helhet, for eksempel alle naturlige tall, det vil si selve forestillingen om et uendelig sett . Uendelig skyldes bare en prosess med oppregning uten repetisjoner som ikke stopper. Bare den tellbare uendelige kan da ha en betydning; den forstås av prosessen som genererer den, snarere enn av hele elementene. Den fullstendige uendelige vil bli bestridt av Henri Poincaré , en konkurranse som også grunnlegger Brouwer sin intuisjonisme , sistnevnte ved å gi den mest forseggjorte formen. For sistnevnte eksisterer bare den tellbare uendelige (som potensiell uendelig), "settet med realer mellom 0 og 1" har ingen betydning, men hvis oppfatningene er sammenhengende, induserer de en dyp spørsmålstegn. Matematikk. Ved å skille mellom de første to forskjellige uendelighetene og ved på en enkel måte å trekke et matematisk resultat som allerede er oppnådd på en annen måte av Joseph Liouville , gir Cantor argumenter for den uendelige, som i dag ikke lenger tenker å diskutere det store flertallet. av matematikere.
Cantor skulle senere vise ekvivalensen til visse utallige mengder, deretter eksistensen av stadig "store" uendelige multipler, som skulle lede ham til utvikling av teorien om kardinalitet , og mer generelt av teorien om sett .
Mengden N av naturlige heltall er selvsagt tellbar per definisjon, men som det vil bli demonstrert senere, er hver av dens uendelige delmengder også tellbare. Vi kan forklare noen spesielle tilfeller. Bemerkningen om at N kunne matches med en streng del har kommet flere ganger siden antikken. For eksempel siteres Galileo ofte for bemerkningen om at det er "like mange" perfekte firkanter som det er naturlige tall. På samme måte oppnår vi ved en eksplisitt oppregning:
Når det gjelder primtall, kan vi bruke en definisjon ved induksjon :
Euclids bevis , som viser at settet med primtall er uendelig, gjør det også mulig å sikre at p n +1 er godt definert, siden settet med primtall som er strengt større enn p n nødvendigvis ikke er fritt (dvs. det inneholder eller primer divisorene p 0 . p 1 ... p n + 1).
Metoden som brukes i sistnevnte tilfelle er generell nok til å tilpasse seg alle uendelige undergrupper av naturlige tall.
Vi viser at visse sett som har N , eller en åpenbar kopi av N , for en streng del er tellbare.
Relative heltallSettet Z av relative heltall kan telles. Faktisk, sekvensen ((-1) n ⌈ n / 2⌉), der ⌈ n / 2⌉ betegner det minste heltallet større enn eller lik n / 2, etablerer faktisk en sammenbinding av naturlige heltall i relative heltall: termer med jevn indekser beskriver naturlige heltall, de med odde indekser beskriver negative heltall som ikke er null.
Par av naturlige tallSett N × N av par med naturlige heltall kan telles; vi kan telle opp parene av naturlige heltall diagonalt for diagonalt, som indikert på vedlagte diagram: ved å følge det definerer vi enkelt ved induksjon en serie par som hver sin opptelling viser alle parene av naturlige heltall. Den gjensidige funksjonen, la f , som derfor er en sammenheng fra N × N til N , kalt Cantor- koblingsfunksjonen , er et polynom av grad 2:
. Det rasjonelleSettet Q av rasjonelle tall kan telles. Faktisk er en rasjonell representert av en brøkdel, det vil si et par som består av et relativt heltall og et naturlig heltall som ikke er null. Ved å komponere korrespondansene som ble opprettet tidligere, oppnår vi en binding fra N til Z × N ∗ . Representasjonen av en rasjonell med en brøkdel er ikke unik, men når vi vet at Q er uendelig, kan vi lett utlede en definisjon ved å indusere en sammenheng fra N til Q (vi tar som bildet av n kvotienten til det første paret i oppregningen av Z × N ∗ som gir en rasjonell som ennå ikke er oppført). Det er også en konsekvens av Cantor-Bernstein-setningen , men det er enkelt å bevise i dette tilfellet.
Andre eksemplerDe to første eksemplene, tellbarhet av Z , men fremfor alt tellbarhet av N × N , bruker et ganske generisk argument for demonstrasjoner av tellbarhet: vi teller elementene i settet betraktet i suksessive blokker, med konstant størrelse i tilfelle Z - to elementer av samme absolutte verdi, av økende størrelse når det gjelder N × N - diagonalene, det vil si parene av samme sum. Vi har også en ensartet måte å bestille, og derfor oppregne, hver endelig blokk.
De generelle setningene som vil bli sett nedenfor kan også brukes til disse sistnevnte eksemplene.
Et sett er ferdig hvis, for et heltall N , der er i Bijeksjon med settet av N prime hel eller {0, 1, ..., N -1}, heltall strengt mindre enn N . For eksempel er det tomme settet (tilfelle N = 0) ferdig (som forventet). Alt endelig er subpotent til N , det vil si at det er en injeksjon av dette settet i N .
En vesentlig egenskap ved endelige mengder er at en injeksjon av et endelig mengde i seg selv nødvendigvis er bindende (se artiklene begrenset sett og prinsipp for skuffer ), dvs. et endelig sett kan ikke være i sammenheng med en ordentlig del av seg selv. Et uendelig sett er rett og slett et sett som ikke er endelig. Mengden N , som er i tilknytning til for eksempel N * , er derfor uendelig, og på samme måte er ethvert tellbart sett uendelig. Vi har til og med:
Proposisjon - Et sett som inneholder et tellbart sett er i tilknytning til en av dets rette deler (spesielt er det uendelig).
Faktisk, la E slikt sett og A en tellbar undergruppe av E . Det var en Bijeksjon på en ren del av E ved å ta identiteten til E - A , og en Bijeksjon fra A til en ren del av A .
Med det valgte aksiomet kan vi vise at hvis et sett er uendelig, så inneholder det en tellbar del (se seksjon # Axiomatisk teori nedenfor).
Vi vil bruke for forhold på N . Et innledende segment av settet med naturlige tall N er enten N selv, eller settet med naturlige tall strengt mindre enn et gitt naturlig tall. Spesielt, er den tomme settet et første segment av N . Vi kan vise at:
Lemme - Til del A i N , er det en Bijeksjon strengt voksende en innledende segment av N i A .
Tilfellet der A er tom er åpenbar, antar vi at dette settet A ikke er tomt. Vi vil bruke det faktum at N er godt ordnet , det vil si at enhver ikke-fri delmengde av N har et mindre element. Vi kan faktisk definere en sekvens ( a n ) ved induksjon som følger:
Denne pakke setter ut en strengt voksende Bijeksjon av en innledende segment heltall i A .
DemonstrasjonVed konstruksjon er enten denne sekvensen definert på alle de naturlige heltallene, eller det eksisterer et helt tall p slik at det er definert for p + 1 første heltall (heltallene fra 0 til p ) og bare disse. Også ved konstruksjonen er det strengt voksende, noe som sikrer at den er injektiv over dens definisjon satt, og, ved induksjon , at hvis en n er definert, så en n ≥ n . Vi utleder derfor at hvis sekvensen er avgrenset, så er den definert bare på heltall opp til en viss p .
Vi viser nå at bildet av denne sekvensen er A . Eller b et element av A . Det eksisterer et helt tall p slik at a p er definert, og et p ≥ b . Enten er ikke sekvensen avgrenset, eller det eksisterer et heltall p slik at sekvensen bare er definert for heltallene til og med p , noe som betyr at a p er definert, og at ingen element av A er den er strengt overlegen den. Vi kan derfor definere, med god ordreegenskap, det minste heltallet n slik at a n ≥ b . La oss vise at b = a n . Ved definisjon av pakken, hvis n = 0 er at b = en 0 , det minste element i A . Hvis n ≠ 0 betyr det at n = m +1, og at a n er det minste elementet blant elementene i A som er strengt større enn a m , hvorav b hører nøyaktig til, per definisjon av n . Så, per definisjon av en n , a n ≤ b , så b = a n .
Sekvensen ( a n ) definerer derfor en sammenheng enten mellom N og A , i hvilket tilfelle per definisjon A kan telles, eller mellom settet med p +1 primærtall og A , i hvilket tilfelle A per definisjon er endelig.
Per definisjon på den ene siden av endelige sett, på den andre siden av tellbare sett, trekker vi fra lemma den første delen av proposisjonen som følger.
Proposisjon - Enhver del A av N er endelig eller tellbar. Dessuten er denne del A endelig hvis den er avgrenset, ellers telles.
For den andre delen (ved igjen å ekskludere det åpenbare tilfellet der A er tom og derfor avgrenset av et hvilket som helst heltall), har vi allerede sett under beviset på lemmaet at hvis A er avgrenset, er det første segmentet S som det er i tilknytning til av skjemaet {0,1,…, p } for et bestemt heltall p (med andre ord: A er endelig) og omvendt, hvis S er av formen {0,1,…, p } så er A avgrenset ( av en p ).
En strøm karakterisering er således et delsett uendelig (dvs. tellbar) av N . For eksempel er en variant av Euklids bevis for eksistensen av en uendelig primtall å vise at for ethvert heltall n , n ! + 1 har minst en hoveddeler, og disse er nødvendigvis større enn n .
En direkte konsekvens av forslaget er:
Resultat : Hvis A er subpotent til N , det vil si hvis det er en injeksjon fra A til N , så er A endelig eller tellbar.
Vi kan derfor snakke om et mest tellbart sett for et endelig eller tellbart sett. Vi utleder også at:
Proposisjon - Hvis det er en overføring fra N til A, er A endelig eller tellbar.
Faktisk, hvis s er en overføring fra N til A , kan vi definere en injeksjon i som er en riktig gjensidig gjengivelse av s , uten å appellere til det valgte aksiomet , siden N , startsettet for overgivelsen, faktisk er ordnet : vi tar for i ( y ), hvor y i A , den minste forgjengeren til y ved s .
Omvendelsen av resultatene er åpenbar per definisjon av endelige mengder og tellbare sett. Det motsatte av proposisjonen er per definisjon åpenbar. Hvis det eksisterer en sammenheng fra et endelig mengde F til et mengde A , og A er ikke-fri, la a ∈ A , så kan vi fullføre denne sammenheng ved en overføring fra N til A , ved å knytte a til et hvilket som helst element av N som ikke er i F . Disse resultatene vil bli samlet i setningen til følgende avsnitt.
Ovennevnte fra N generaliseres direkte til et hvilket som helst tellbart sett, ved å komponere med bindingen som sikrer ekvipotens.
Teorem - Enhver del av et tellbart sett er endelig eller tellbart. Vi har ekvivalensen mellom følgende tre proposisjoner:
Ettersom hvert sett som inneholder et tellbart sett er uendelig (se ovenfor), utleder vi:
Resultat - Følgende tre proposisjoner er ekvivalente:
Denne følge viser i det vesentlige Cantor-Bernstein-setningen i det spesielle tilfellet av tellbare, hvis bevis er blitt tilrettelagt av det faktum at N er ordnet.
Vi bruker disse karakteriseringer i det følgende, men som et første eksempel på anvendelse kan vi vise at for en hvilken som helst ikke-null heltall n , settet N x {0, ..., n } er tellbar. Faktisk injiseres dette settet ved inkludering i N × N , som vi har vist å være tellbare, og vi har en injeksjon av N i dette settet ved å assosiere med et helt tall p paret ( p , 0) (det gjør det imidlertid ikke ville ikke være veldig vanskelig å gi en eksplisitt sammenheng ved hjelp av euklidisk inndeling ).
Vi har sett at N × N kan telles (Cantor coupling function). Vi kan lett utlede at:
Proposisjon - Det kartesiske produktet av en endelig ikke-tom familie av tellbare sett er tellbar .
Vi viser først resultatet for A og B to tellbare sett. Det er en Bijeksjon av A på N og et Bijeksjon av B på N . La oss definere:
Dette kartet er bindende fra A × B til N × N , som kan telles. Så A × B er tellbar.
En endelig, ikke-fri familie kan antas å være indeksert av heltall fra 0 til n for noen n , per definisjon av et endelig sett. Resultatet generaliserer deretter til enhver ikke-ubegrenset endelig familie ved induksjon ved å bruke, for induksjonstrinnet, resultatet vi nettopp har demonstrert for to sett.
Corollary - Det kartesiske produktet av en endelig familie på høyest tellbare sett er høyst tellbar .
Vi bruker karakteriseringene i forrige avsnitt. Hvis familien har for endelig kardinal n , definerer vi som ovenfor en injeksjon av det kartesiske produktet i N n . Nå kan dette settet telles i henhold til forrige forslag (hvis familien er tom, reduseres produktet til ett element).
Vi kan bruke disse egenskapene til å gi en rask begrunnelse for tellbarheten til settet Q av rasjonaliteter . Faktisk er Z , sett med relative heltall, tellbar så vel som N * , sett med strengt positive heltall, og derfor deres kartesiske produkt Z × N * . Enhver rasjonell blir skrevet på minst en måte som en brøk p / q der p ∈ Z og q ∈ N * . Dette gjør det mulig å definere en overføring fra Z × N * til Q , som derfor er høyest tellbar; å være uendelig, er det tellbart.
Proposition - Den gjenforening av en endelig familien på de fleste Tellbar er høyst tellbar. Hvis et av settene til den endelige familien er tellbar, er unionen tellbar.
Anta faktisk at familien til kardinal n + 1 (hvis familien også er tom for gjenforeningen, hvorfra resultatet), kan man alltid redusere til en indeksering av heltallene fra 0 til n . Det er derfor et spørsmål om å vise at hvis settene A 0 ,…, A n er høyest tellebare, så er deres forening også tellbar. For hver A i er en f i en injeksjon av A i i N . Vi definerer en injeksjon av A 0 ∪ ... ∪ A n i det tellbare settet N × {0,…, n }, ved å assosiere med et paret ( f ( i ), i ), hvor i er det minste heltallet slik at en ∈ A i . Hvis dessuten en av A i er telles, A 0 ∪ ... ∪ A n inneholder et Tellbar, er derfor tellbar.
Vi utnytter igjen tellbarheten til N × N , men resultatene i dette avsnittet bruker aksiomet av tellbart valg . Vi viser da at:
Proposisjon - Gjenforeningen av en tellbar familie av tellbare sett er tellbar.
Etter sammensetning, er det alltid mulig å redusere til det tilfelle hvor familien er indeksert av N . Det er da et spørsmål om å vise at hvis ( A i ) i ∈ N er en familie av tellbare mengder, så er foreningen av disse settene, A = ∪ i ∈ N A i , et tellbart sett. Da A i er tellbar, eksisterer det for hvert heltall i , en sammenheng fra N på A i . Ved å anvende aksiomet av (tellbar) valg på sekvensen ( F i ) i ∈ N , der F i er settet med bindinger fra N til A i , får vi en funksjonssekvens ( f i ) i ∈ N , hvor f jeg er en sammenheng fra N til A i . Vi kan derfor definere følgende kart over N 2 i A :
Kartet f er surjektiv, fordi hver av kartene f i er, og hvert element av A er et element av i det minste ett A i .
Dermed er settet A maksimalt tellbart, ettersom det inneholder et tellbart sett, er det tellbart.
Proposisjon - En tellbar forening av maksimalt tellbare sett er høyest tellbar.
I det tilfelle hvor noen A i endelig, er det tilstrekkelig å gjenta den foregående bevis, men med den f i surjectives fra N til A i .
Noen av de tidlige eksemplene kan bli undersøkt på nytt i lys av disse resultatene. For eksempel er settet med endelige sekvenser av heltall, som er foreningen av N n for n ∈ N , en tellbar forening av tellbare mengder, derfor tellbar i henhold til den første av disse to proposisjonene. Beviset har derfor blitt veldig enkelt. Imidlertid brukte det første (skisserte) beviset ikke det valgte aksiomet. Faktisk reduserte vi oss til en tellbar forening av endelige sett, og vi brukte leksikografisk rekkefølge for å direkte konstruere en valgfunksjon. Vi kan heller ikke bekymre oss for om vi vil appellere til valgaksiomet eller ikke, spesielt siden det her tross alt bare er aksiomet for tellbart valg.
Vi har et bevis som bruker de samme argumentene for settet med algebraiske tall. Dette settet er uendelig siden heltallene åpenbart er algebraiske. Settet med polynomer med heltallskoeffisienter er åpenbart uendelig, og injiseres i settet med endelige sekvenser av heltall (ved å ta sekvensen av koeffisientene), er derfor tellbar. Et polynom har bare et endelig antall røtter. Settet med algebraiske tall, som er foreningen av settene til røttene til alle polynomer med heltallskoeffisienter, er derfor i det høyeste tellbare ved hjelp av forrige forslag; det er tellbart.
Klassen av tellbare sett er selvfølgelig ikke stengt under alle angitte operasjoner. Den Cantor teorem viser, for de diagonale argumentet , at alle deler av et Tellbar er utallige. Vi trekker ut fra denne teoremet, eller ved å bruke det diagonale argumentet, at settet med sekvenser med heltallverdier indeksert av heltall (funksjonene fra N til N ) ikke er tellbare heller, noe som betyr at et produkt som kan telles av tellbare sett ikke er tellbart.
Som settet med deler av N , eller til og med settet med sekvenser på 0 og 1, som vi betegner med {0, 1} N , har dette settet kraften til kontinuum : kardinalen til settet med reelle tall. Egenskapene til tellbare sett kan utnyttes for å demonstrere at noen sett har kraften i kontinuumet. For eksempel fra ekvipotensen mellom det kartesiske produktet N × N og N , utleder vi ( A B × C er ekvipotent til ( A B ) C ), at mellom ({0.1} N ) N og {0.1} N og derfor at sett med reelle sekvenser indeksert av heltallene har kontinuerlig kraft.
Etter Cantors teorem er det selvfølgelig sett som verken er tellbare eller har kraften i kontinuumet. Vi kan også vise eksistensen av utallige sett uten å bruke Cantors teorem, alltid ved hjelp av et diagonalt argument og forestillingen om god orden , noe som fører til kardinal aleph-un og mer generelt til hierarkiet av alephs .
Et uendelig utallig mengde er per definisjon et sett som verken er likeverdig med et endelig sett, eller til N , eller på annen måte er sagt hvis kardinal ikke er endelig eller tellbar. Det er derfor et sett som ikke er like potente en del av N (se avsnittet Deler av et Tellbar ), dvs. slik at det ikke er noen injeksjon av dette settet i N . Det er fortsatt et ikke-fritt sett som ikke er bildet av N ved en overgivelse ( samme avsnitt ).
Imidlertid er ingen av disse karakteriseringene veldig praktiske, og for å oppnå mer operative, trenger vi det valgte aksiomet (som ikke var tilfelle for de foregående karakteriseringene), noe som gjør det mulig å vise at settene uendelig er settene som inneholder et tellbart sett,
Fakta - I nærvær av det valgte aksiomet, er et uendelig utallig mengde et sett hvis kardinalitet er strengt større enn N , dvs. det er et sett som inneholder en tellbar del, og slik at det ikke er noen injeksjon av dette settet i N .
Imidlertid bør det bemerkes at for mange applikasjoner (se et eksempel i det følgende avsnittet) er det ikke nødvendig å ringe til det valgte aksiomet. Eksistensen av sett som ikke er likeverdige med en del av N , men som ikke inneholder et tellbart sett, kan ikke demonstreres i teorien om sett ZF, siden dette strider mot valgaksiomet, eller Kurt Gödel viste kompatibiliteten til dette en med aksiomene til ZF.
Vi kan også utnytte egenskapene til tellbare sett, for å utlede egenskaper av sett som inneholder et tellbart sett, det vil si i nærvær av det valgte aksiomet (forkortet AC), uendelige sett generelt. Fra det faktum at foreningen av to tellbare sett er tellbar, trekker vi straks ut at:
Proposisjon - Hvis E er et uendelig sett (som inneholder et tellbart sett hvis vi ikke har antatt AC), så er foreningen av E og et tellbart sett likeverdig med E.
La A være en tellbar del av E og B et tellbart sett. Det er en Bijeksjon mellom A og A ∪ ( B \ E ) (foreningen av A og sett forskjellen B \ E ) som er forlenget med identiteten av den komplementære med A i E .
Vi utleder (forutsatt det valgte aksiomet):
Resultat (AC) - Anta at E er et uendelig utallig mengde, og at A er en tellbar del av E, så er E \ A, komplementet til A i E, likeverdig med E.
Korollæren bruker kun aksiomet for å vise at E \ A inneholder et tellbart sett. La oss gi et eksempel der vi trekker det direkte ut. Sett med sekvenser på 0 og 1, E = {0,1} N , kan ikke telles med diagonalt argument . Settet A med sekvenser på 0 og 1 som bruker 1 bare et endelig antall ganger, dvs. slutter med uendelig 0, kan telles: vi har en åpenbar injeksjon av dette settet i endelige sekvenser av heltall, og det er også åpenbart uendelig (for eksempel settet med sekvenser som bare bruker 1 én gang, kan telles). Settet E \ A for sekvensene på 0 og 1 som bruker 1 et uendelig antall ganger inneholder et tellbart sett: for eksempel det av sekvensene som bare bruker 0 en gang. Vi kan derfor bruke følgene uten å trenge det valgte aksiomet: E = {0,1} N er ekvipotent til settet E \ A av endelige sekvenser på 0 og 1 som ikke ender i uendelig 0. Disse sekvensene gir en unik utvidelse i base 2 for virkeligheten av] 0,1]. Vi utleder at {0,1} N og derfor settet med deler av N har kraften i kontinuumet .
Definisjonene og utviklingen rundt det tellbare har blitt utført uten å referere til en presis aksiomatisering av mengdeteorien , men det er lett å verifisere at alt er formalisert i Zermelo-Fraenkel-teorien , og til og med i Zermelo-teorien, med muligens aksiomet. : snarere enn ordningen med erstatningsaksiomer , er ordningen med forståelsesaksiomer tilstrekkelig. Spesielt gjør endelighetsaksiomet det mulig å vise eksistensen av et uendelig sett som har egenskapene som forventes av mengden N av naturlige heltall, og som vi tar som definisjon.
Vi trengte det valgte aksiomet, på den ene siden for å vise at gjenforeningen til en tellbar familie av tellbare sett er tellbar, på den andre siden for å vise at hvis et sett ikke er endelig, inneholder det et tellbart sett. I begge tilfeller kan vi vise at aksiomet av tellbart valg er tilstrekkelig. Dette er åpenbart for den første uttalelsen (se ovenfor).
For det andre, la E være et uendelig sett (dvs. som ikke er i sammenheng med noe sett {0,…, n - 1}, n heltall). Det er naturlig å bygge en injeksjonssekvens ved induksjon ved å bruke en valgfunksjon over de medfiniserte delmengdene av E (alt ikke-tomt ellers ville E være endelig). Vi modifiserer dette beviset litt for kun å bruke aksiomet som kan telles. For hvert heltall n er settet med ( n + 1) -upler av elementene i E skilt to og to (injeksjonene av {0, ..., n } i E ) ikke fritt. I henhold til aksiomet av tellbart valg, eksisterer det en funksjon f definert på N slik at f ( n ) er en ( n + 1) -tuple av elementer av E som skiller seg to og to. Vi kan da definere g på N ved induksjon som følger. Ved 0 er g (0) det eneste elementet i 1-tupel f (0). I n + 1 er g ( n + 1) elementet med den minste indeksen til ( n + 2) -tupelen f ( n + 1) som ikke vises i { g (0),…, g ( n ) } (av kardinalitet på det meste n + 1, så et slikt element eksisterer). Ved konstruksjon av funksjonen g er injektiv, og dens bilde er en tellbar undergruppe av E .
Vi kan vise at det valgte aksiomet er veldig nødvendig for disse to resultatene. Det er modeller av Zermelo-Fraenkel teorien, ZF, (uten valgaksiom, selvfølgelig), der for eksempel settet med reelle tall R er en tellbar forening av tellbare sett. På samme måte er det modeller av ZF der det er uendelige sett som ikke inneholder en tellbar delmengde. Demonstrasjoner bruker avanserte metoder for mengdeori , de kombinerer tvang av Cohen og metoden for permutasjon Fraenkel - Mostowski .
Det tellbare er en slik elementær forestilling at den finnes i nesten alle matematikkområder. For eksempel foretrekker vi å snakke om en tellbar familie (matematikk) fremfor om en sekvens indeksert av naturlige tall, når vi vil understreke det faktum at rekkefølgen ikke er viktig (se for eksempel sammenleggbar familie ).
Mengden Q av rasjonelle er en tett tellbar del av rommet R av realer . Denne egenskapen generaliserer til R n og fører til forestillingen om separerbart topologisk rom . Det har som konsekvens at et sett med åpninger av R nonempty disjoint to og to er høyest tellerbare. Faktisk er skjæringspunktet med Q av unionen (la oss anta at det ikke er tomt) av disse åpningene et tellbart sett, og kartet som til et element i dette settet knytter det unike åpent det tilhører, er antatt. Vi kan vise at en hvilken som helst åpen av R er en forening av ufrie åpne intervaller som er sammenføyde to og to (de tilknyttede komponentene), en forening som derfor maksimalt kan telles (se spaltning av åpningene til ). En annen egenskap med R , som ved å ha en tellbar bunnen av åpninger (åpne intervaller hvis grenser er rasjonelle) fører til tanken om plass med en tellbar basen .
En grunnleggende anvendelse av tellbarhet er Baires teori .
I algebra er det vanlig å legge merke til at for eksempel en gruppe som har et endelig antall generatorer er på det meste teller. For eksempel genererer to refleksjoner av planet en endelig gruppe ( tosidig gruppe ) eller uendelig, men tellbar, avhengig av om vinkelen mellom de to refleksaksene er eller ikke et rasjonelt multiplum av π .
Ethvert element i denne gruppen er faktisk representert av en endelig sekvens av generatorene i gruppen. Dette er et spesielt tilfelle av et mer generelt fenomen. Vi har sett at ordsettet på et endelig eller tellbart språk er tellbar. Denne egenskapen har viktige konsekvenser i logikken . Det er alltid mulig å vise at en førsteordens teori uttrykt i et endelig eller tellbart språk (som Peano-aritmetikk eller mengde teori ) har en tellbar modell. Dette er en svak form av Löwenheim-Skolem-teoremet , som kan trekkes direkte fra beviset på fullstendighetssetningen . Når det gjelder mengde teori er det såkalte paradokset for Skolem , men dette er en nyttig egenskap, som ble brukt av Paul Cohen for hans uavhengige bevis for hypotesen kontinuerlig og aksiomet av valget .
De data håndtakene bare tellbar. Men en mer krevende eiendom er nyttig. Et sett er endelig eller tellbart når det er tomt eller bildet av en funksjon definert på N , og derfor på en bestemt måte "opptellingen" av en funksjon definert på heltall. For at et sett skal være rekursivt opptellingen, kreves det også at denne funksjonen kan beregnes (i den forstand beregnet av en maskin). Det er tellbare sett som ikke rekursivt kan telles. Et eksempel er settet av hele tall som koder for et Turing maskin som ikke stopper for en gitt inngang, kan dette settet ikke være rekursivt enumerable henhold til undecidability av stopp problemet . Et annet eksempel er gitt med setningen av en rekursivt aksiomatiserbar teori som ikke kan avgjøres , som Peanos aritmetikk . Det er et sett med ord på et endelig (eller tellbart) alfabet, derfor tellbart, men ikke rekursivt opptellbart.
Oversettelse til fransk av Cantors 1874-artikkel om ikke-tellbarhet av reelle tall, på en egenskap til systemet med alle reelle algebraiske tall , introduksjon og analyse av Patrick Dehornoy , på BibNum- siden .