Kardinalitet

I matematikken er en mængdes kardinalitet eller mægtighed et mål for "antallet af elementer i mængden." Der er to tilgangsvinkler til kardinalitet – en der sammenligner mængder direkte ved brug af bijektioner, injektioner og surjektioner og en anden, der benytter kardinaltal.

Mængdesammenligning

Vi siger, at to mængder A og B har samme kardinalitet, hvis der findes en bijektion, dvs. en injektiv og surjektive afbildning, fra A til B. For eksempel har mængden E = {2, 4, 6, ...} af positive lige tal samme kardinalitet som mængden N = {1, 2, 3, ...} af naturlige tal, da funktionen f(n) = 2n er en bijektion fra N til E.

Vi siger, at en mængde A har en kardinalitet større end eller lig med kardinaliteten af en mængde B (og at B har kardinalitet mindre end eller lig med kardinaliteten af A,) hvis der findes en injektiv afbildning fra B til A. Vi siger, at A har kardinalitet strengt større end kardinaliteten af B, hvis A har kardinalitet større end eller lig kardinaliteten af A samtidig med, at A og B ikke har samme kardinalitet; dvs. hvis der findes en injektiv afbildning fra B til A men ingen bijektiv afbildning fra A til B. For eksempel er kardinaliteten af mængden R af alle reelle tal strengt større end kardinaliteten af mængden N af alle naturlige tal, da inklusionsafbildningen i : N → R er injektiv, men det kan vises, at der ikke findes en bijektiv afbildning fra N til R.

Tællelige og overtællelige mængder

Hvis det antages, at udvælgelsesaksiomet holder, gælder trikotomiloven for kardinalitet, og der dannes grundlag for følgende definitioner.

• Enhver mængde med kardinalitet strengt lavere end de naturlige tals siges at være en endelig mængde. Med andre ord skal findes et n i N, så mængden er et surjektivt billede under {1, ..., n}. En mængde kaldes tællelig, hvis den er et surjektivt billede under N – specielt er en endelig mængde tællelig.
• Enhver mængde, der har samme kardinalitet som mængden af de naturlige tal, kaldes en tællelig uendelig mængde. En uendelig mængde er tællelig, hvis og kun hvis den er et bijektivt billede af N.
• Enhver mængde med kardinalitet større end de naturlige tals siges at være en ikke-tællelig eller overtællelig mængde.