Överuppräknelig

En mängd är överuppräknelig (ouppräknelig) om den har en kardinalitet som är större än Alef-nollen (Alef-0), det vill säga den för de naturliga tal. Det minsta överuppräkneliga kardinaltalet är Alef-1, sedan kommer Alef-2, Alef-3 osv. Det finns ingen gräns för hur stora överuppräkneliga kardinaltal vi kan bilda (se Cantors sats). Efter alla Alef-i (där i är ett naturligt tal) kommer Alef-ω (Alef-omega), sedan Alef-(ω+1), Alef-(ω+2), ... , Alef-(ω+ω), ..., Alef-(ω+ω+ω), ... osv i all oändlighet. De tal som är index till bokstaven alef är alltsÃ¥ ordinaltalen i tur och ordning.

Exempelvis är mängden av de reella talen, R, överuppräknelig och har kardinaltalet 2^Alef-0. Enligt kontinuumhypotesen är 2^Alef-0 = Alef-1. Enligt den generaliserade kontinuumhypotesen är 2^Alef-k = Alef-(k+1) för alla k.

Beteckningen 'ouppräknelig' kommer av att det inte finns något sätt att räkna upp elementen i en sådan mängd. Det betyder att det inte finns något sätt att associera ett unikt naturligt tal till varje element i mängden. För en uppräknelig mängd gäller däremot att det finns ett system för att tilldela ett naturligt tal till varje element, även om mängden innehåller oändligt många element. Därmed kan elementen i en sådan mängd räknas upp i den ordning som det naturliga talet anger och vilket element man än väljer kommer man förr eller senare att nå fram till detta.