räknbar

Räknbar, eller räknbar mängd, är ett centralt begrepp inom mängdteorin. En mängd anses vara räknbar om den kan listas i en oändlig följd utan upprepningar, vilket formellt innebär att den är ändlig eller att det finns en bijektion mellan mängden och de naturliga talen N. Med en sådan bijektion kan man ordna elementen i en följd a1, a2, a3, … där varje element förekommer exakt en gång.

Exempel på räknbara mängder är naturliga tal N, heltal Z och rationella tal Q. Alla ändliga mängder är räknbara, och varje mängd som kan bijekteras med N räknas också som räknbar. Mängder som består av ordnade par av tal eller av allmänna finite alphabet-strängar kan ofta ordnas i en sådan sekvens, och därmed klassas de som räknbara.

Mängden av reella tal är däremot inte räknbar. Cantors diagonalargument visar att det inte går att lista alla reella tal i en oändlig följd där varje tal förekommer exakt en gång, vilket innebär att R är obräknbar (ohävdat räknbarhet).

Begreppet räknbarhet används ofta inom analys, kartläggning av storleksordningar och mängdlära. Fördelar med att känna till att en mängd är räknbar inkluderar ofta möjligheten att behandla den som en uppräkning eller sekvens och att visa att vissa operationer som unioner eller produktmängder med räknbara mängder förblir räknbara under rätt förutsättningar.