Spočítateľná množina

Spočítateľná množina je množina, ktorá má v istom zmysle nanajvýš „rovnako veľa“ prvkov ako množina prirodzených čísel. Presne je spočítateľná množina definovaná ako množina ktorú možno bijektívne zobraziť na podmnožinu prirodzených čísel.^[1] Príkladom spočítateľnej množiny je napríklad množina párnych čísel, keďže každému párnemu číslu možno priradiť jeho polovičnú hodnotu a toto zobrazenie je bijekcia z párnych čísel do prirodzených čísel.

Príklady

• Každá nekonečná podmnožina prirodzených čísel je spočítateľná.
• Množina celých čísel a každá jej podmnožina je spočítateľná.
• Zložitejšími príkladmi spočítateľných množín je množina racionálnych čísel a algebraických čísel.

Vlastnosti

• Každá nespočítateľná množina je nekonečná.
• Zjednotenie spočítateľného množstva spočítateľných množín je spočítateľná množina
• Každá podmnožina spočítateľnej množiny je spočítateľná množina
• Dá sa tiež dokázať, že karteziánsky súčin dvoch spočítateľných množín (napr. ${\displaystyle \mathbb {N} \times {}\mathbb {N} }$) je opäť spočítateľnou množinou. Indukciou sa dá potom dokázať, že aj karteziánsky súčin konečnej množiny spočítateľných množín je opäť spočítateľný.