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 $N=$ { $1,2,3,4...n,n+1...$ } af alle naturlige tal er uendelig. Det vil sige, at på et vilkårligt N_n, 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 P_n svarer én og kun én T_n, og for enhver T_n ligeledes svarer én og kun én P_n, siger man, at de har samme kardinaltal. Det kaldes også for en bijektiv afbildning.

Lige og ulige tal

Andre eksempler er mængden { $2,4,6,8...$ } eller { $1,3,5,7...$ }. Lad os kalde dem N_lige og N_ulige. Når man kigger på N_lige og N_ulige 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 N_lige, 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 N_lige 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 N_lige og N_ulige. Hvis det passer, må det samtidig gælde, at der for enhver N_n svarer én og kun én N_lige. Det kan igen virke umuligt, da man skulle synes, at der må være halvt så mange N_lige som N. Dette løses heldigvis simpelt. Vi laver en bijektiv afbildning af N på N_lige. 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 → N_lige, vil der for enhver N_n være én N_lige, så

                       en bijektiv afbildning f: N → N_lige  f(1)=2, f(2)=4, f(3)=6, f(4)=8, osv.
                    og en bijektiv afbildning f: N → N_ulige f(1)=1, f(2)=3, f(3)=5, f(4)=7, osv.
                                   N på N_lige    N på N_ulige
                                    2,4,6,8...   1,3,5,7...
                                    1,2,3,4... v 1,2,3,4...

Det ses, at N_lige og N har samme kardinalitet, på trods af, at N_lige er N minus N_ulige. For at kunne forstå dette, er det vigtigt, man accepterer, at ingen af talrækkerne N, N_lige eller N_ulige 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

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

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

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

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

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

Se også