Tællelig mængde

En tællelig mængde er en mængde, der har samme kardinalitet (dvs. i en vis forstand samme antal elementer) som en delmængde af de naturlige tal, eller ækvivalent: en mængde A er tællelig, hvis og kun hvis der findes en injektiv funktion fra A til de naturlige tal. Bemærk at man somme tider som krav stiller eksistensen af en bijektiv funktion fra A til de naturlige tal. Forskellen på de to definitioner er, at enhver endelig mængde vil være tællelig med den første definition, mens det ikke vil være tilfældet med den sidste. Hvis A er uendelig og tællelig, hvilket uformelt betyder, at man kan skrive elementerne i en uendelig nummereret lang liste, kaldes den ofte tællelig uendelig. En mængde der ikke er tællelig kaldes overtællelig (eller nogle steder blot ikke-tællelig).

Eksempler

Tællelig mængde
Eksempler på tællelige mængder er de hele tal og de rationale tal. Mængden af de hele tal (...,-2, -1, 0, 1, 2,...) er tællelig, fordi man kan liste elementerne: 0, 1, -1, 2, -2,.... De positive rationale tal kan også listes: 1/1, 1/2, 2/1, 1/3, (2/2), 3/1, 1/4,... Man lister de rationale tal først efter summen af tæller og nævner og derefter efter tæller. 2/2 er indsat i parentes for at vise systemet, men tæller ikke med da 1/1 allerede er i listen. Alle de rationale tal kan så listes ved at flette de positive og negative sammen på samme måde som med de hele tal.

De naturlige tal
Mængden {} af alle naturlige tal er uendelig. Det vil sige, at på et vilkårligt Nn, kan man altid lægge 1 til og har derved endnu et tal. En talmængde uden grænser så at sige. Det er dog her vigtigt at forstå, at mængden kun er uendelig, så længe vi lader den fortsætte. Vi vil aldrig nå til et bestemt punkt og sige; så, nu nåede vi det endelig. Da vil det nemlig være endeligt. Det at mængden er uendelig, er ikke ensbetydende med, at den ikke er tællelig. Det vil ganske vist være praktisk umuligt for noget menneske at sætte sig ned med sin blyant og krydse samtlige tal i mængden N af, men det skyldes kun omstændigheder, som at han ikke også har uendeligt eller ubegrænset tid – eller at der blot var uendeligt mange til at tælle. Man siger også, at den uendelige mængde N, har tællelig kardinalitet – hvor kardinalitet er mængden af elementer. Enhver mængde har derfor en kardinalitet (størrelse). Samlingen af 10 fingre har kardinaliteten 10. Lægger man de 10 tæer til, er kardinaliteten af den samlede mængde 20. Hvis mængden af to relationer kan parres, altså hvis der for enhver Pn svarer én og kun én Tn, og for enhver Tn ligeledes svarer én og kun én Pn, siger man, at de har samme kardinaltal. Det kaldes også for en bijektiv afbildning.

Lige og ulige tal 
Andre eksempler er mængden {} eller {}. Lad os kalde dem Nlige og Nulige. Når man kigger på Nlige og Nulige vil man umiddelbart synes, at disse to mængder må have samme kardinaltal. Det giver også god mening, da de begge er en lige stor halvdel af N, som er uendelig. Det skal nu vise sig at blive mere kompliceret. Når man kigger på mængden Nlige, vil det umiddelbart se ud som om, at den har et kardinaltal halvt så stort som N. Men da N er uendelig, vil det halve af N ligeledes være uendelig, og derfor vil N og Nlige have samme kardinaltal. Det kan på første hånd virke ulogisk, men det er det heldigvis ikke. Min påstand er nu, at N har samme kardinaltal (mængde af tal), som Nlige og Nulige. Hvis det passer, må det samtidig gælde, at der for enhver Nn svarer én og kun én Nlige. Det kan igen virke umuligt, da man skulle synes, at der må være halvt så mange Nlige som N. Dette løses heldigvis simpelt. Vi laver en bijektiv afbildning af N på Nlige. En bijektiv afbildning vil populært sagt sige, at der skal være lige så mange af mængden H som af mængden G. Billedligt svarer det til, at der er lige så mange kopper som underkopper. Der er hverken overskud af kopper eller underkopper.
Hvis det passer, at der kan laves en bijektiv afbildning af N → Nlige, vil der for enhver Nn være én Nlige, så
                        en bijektiv afbildning f: N → Nlige  f(1)=2, f(2)=4, f(3)=6, f(4)=8, osv.
                     og en bijektiv afbildning f: N → Nulige f(1)=1, f(2)=3, f(3)=5, f(4)=7, osv.
                                    N på Nlige    N på Nulige
                                     2,4,6,8...   1,3,5,7...
                                     1,2,3,4... v 1,2,3,4...
Det ses, at Nlige og N har samme kardinalitet, på trods af, at Nlige er N minus Nulige. For at kunne forstå dette, er det vigtigt, man accepterer, at ingen af talrækkerne N, Nlige eller Nulige har nogle ydre grænser.

Overtællelig mængde
Eksempler på overtællelige mængder er mængden af de reelle tal og mængden af uendelige følger af 0 og 1-taller. 

At den sidstnævnte mængde er overtællelig kan vises med Cantors diagonalbevis:
Antag at man kan liste alle uendelige følger af 0 og 1-taller. Listen kunne f.eks. starte

s1 = (0, 0, 0, 0, 0, 0, 0, ...)
s2 = (1, 1, 1, 1, 1, 1, 1, ...)
s3 = (0, 1, 0, 1, 0, 1, 0, ...)
s4 = (1, 0, 1, 0, 1, 0, 1, ...)
s5 = (1, 1, 0, 1, 0, 1, 1, ...)
s6 = (0, 0, 1, 1, 0, 1, 1, ...)
s7 = (1, 0, 0, 0, 1, 0, 0, ...)
...

Men følgen, hvis n'te led er forskelligt fra n'te led i sn, kan ikke stå på listen:

s1 = (0, 0, 0, 0, 0, 0, 0, ...)
s2 = (1, 1, 1, 1, 1, 1, 1, ...)
s3 = (0, 1, 0, 1, 0, 1, 0, ...)
s4 = (1, 0, 1, 0, 1, 0, 1, ...)
s5 = (1, 1, 0, 1, 0, 1, 1, ...)
s6 = (0, 0, 1, 1, 0, 1, 1, ...)
s7 = (1, 0, 0, 0, 1, 0, 0, ...)
...

s0 = (1, 0, 1, 1, 1, 0, 1, ...)

Antag at den gør, og at den er lig sm for et naturligt m. Fra definitionen på følgen er dens m'te element forskellig fra det m'te element i sm, men så er den netop forskellig fra sm.

Overtælleligheden af de reelle tal følger også af ovenstående resultat.

Se også 
 Kardinalitet
 Cantor's diagonalbevis

Mængdelære