Uppräknelig

En mängd är uppräknelig om den har samma kardinaltal som en delmängd till de naturliga talen, det vill säga ett ändligt tal eller ℵ₀. Exempel: Mängderna {1, 2, 3, 4, 5, 6, 7} och {A, B, C, D, E, F, G} är båda uppräkneliga med kardinaltalet 7 i båda fallen.

Alla naturliga tal är var för sig uppräkneliga. Ett tal n vilket som helst har ju kardinaliteten n eftersom |n| = n (se artikeln mängd). Men hela mängden av naturliga tal, ℕ, är också uppräknelig, men oändlig, eftersom den är en delmängd till sig själv.

Kardinaltalet för en uppräkneligt oändlig mängd är Alef-noll (Alef-0, ℵ₀), som också är den "minsta" oändligheten. Exempel på uppräkneligt oändliga mängder: naturliga tal, hela tal och rationella tal. En oändlig mängd som ej är uppräknelig kallas överuppräknelig (eller ouppräknelig).

Beteckningen "uppräknelig" kommer av att alla mängder med denna egenskap i princip kan räknas upp. De naturliga talen kan ju räknas upp enligt den vanliga metoden 1, 2, 3, 4 etc. I praktiken kommer vi aldrig hinna räkna upp alla, men vi hinner fram till varje element inom ändlig tid. De rationella talen kan räknas upp genom att skriva dem på bråkform i särskilt kvadratiskliknande schema där man ser att det finns en sick-sack-väg genom schemat med vilken man får med alla talen.

På liknande sätt som man kan visa att |ℚ| = ℵ₀, kan man visa en uppräknelig union av uppräkneliga mängder är uppräknelig.

Exempel

Man kan visa att mängden L_n = { M ⊂ ℕ : } är uppräknelig för alla n. Därför är ℕ^* = {alla ändliga delmängder av ℕ} = $\scriptstyle{\bigcup _{n=0}^\infty}$ L_n uppräknelig. Notera att |$\scriptstyle{\mathcal{P}(\mathbb{N})}$| > |ℕ|, så att motsvarande påstående för mängden av alla delmängder av ℕ, potensmängden av ℕ, inte gäller.

Se även

• Kardinalitet
• Mängdteori
• Oändlig
• kontinuumhypotesen