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 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 vil man sige, at man kan skrive elementerne i en uendelig numereret 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

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 rationelle tal kan også listes: 1/1, 1/2, 2/1, 1/3, (2/2), 3/1, 1/4,... Man lister de rationelle 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.

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 nte led er forskelligt fra nte 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 mte element forskellig fra det mte 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å

• Kardinalitet