Överuppräknelig mängd

En överuppräknelig mängd eller ouppräknelig mängd är en mängd där det inte finns något sätt att numrera antalet element på ett sådant sätt att alla räknas minst en gång. Mer formellt har den en kardinalitet som är större än Alef-noll (Alef-0), det vill säga den för de naturliga talen. 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, såsom de rationella talen, 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.