Uppräknelig mängd

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2019-04) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

En uppräknelig mängd är en mängd för vilken man kan införa någon metod för att numrera alla element så att varje element tas upp minst en gång. Mer formellt har en uppräknelig mängd samma kardinaltal som någon 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). Ett exempel på en sådan mängd är de reella talen.

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 vilket som helst element inom ändlig tid. De rationella talen kan räknas upp genom att skriva dem på bråkform i ett 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 ⊂ ℕ : |M| = n } är uppräknelig för alla n. Därför är ℕ^* = {alla ändliga delmängder av ℕ} = ${\displaystyle \scriptstyle {\bigcup _{n=0}^{\infty }}}$ L_n uppräknelig. Notera att |${\displaystyle \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