Kardinalitet

Den här artikeln eller det här avsnittet anses vara onödigt fackspråklig. (2017-07) Motivering: Den här artikeln är mycket svårläst för någon som inte är bekant med ämnet. Den förklarar inte ens sin kontext. Hjälp gärna Wikipedia med att förtydliga texten och göra den mer lättläst. Se eventuellt diskussionssidan för mer information. Om artikeln inte åtgärdats inom tre år från dess att den märkts upp kan den komma att raderas.

Kardinalitet eller mäktighet^[1] är ett begrepp från mängdteori. Kardinaliteten hos en mängd ${\displaystyle M}$ betecknas ofta ${\displaystyle |M|}$ eller ${\displaystyle \#M}$, och kan ses som ett formellt sätt att beskriva antalet element som ingår i en viss mängd. Exempelvis innehåller ${\displaystyle \{1,5,4\}}$ 3 element och har därför kardinalitet ${\displaystyle 3}$, vilket skrivs ${\displaystyle |\{1,5,4\}|=3}$. Kardinalitet motsvaras exakt av antalet element i mängden för ändliga mängder. Kardinalitet är användbart för att jämföra två oändliga mängder, som kan ha olika stor kardinalitet och därmed på ett visst sätt kan sägas vara "olika stora". Till varje kardinalitet hör ett kardinaltal.

Två mängder har samma kardinalitet om det finns minst en bijektion mellan dem.^[2] Exempelvis bevisar bijektionen ${\displaystyle \{a\leftrightarrow 1,b\leftrightarrow 6,c\leftrightarrow 9\}}$ att mängderna ${\displaystyle \{a,b,c\}}$ och ${\displaystyle \{1,6,9\}}$ har samma kardinalitet. Detta är intuitivt självklart för ändliga mängder, men definitionen kan även användas för att jämföra olika oändliga mängder. Ett exempel är bijektionen ${\displaystyle f(x)=2x}$, där ${\displaystyle f}$ är en funktion över de naturliga talen. Denna bijektion går mellan heltalen och de jämna heltalen, och kan skrivas som ${\displaystyle \{1\mapsto 2,2\mapsto 4,3\mapsto 6,4\mapsto 8\dots \}}$. Även om heltalen intuitivt har "dubbelt så många" element som de jämna heltalen, visar detta att de båda mängderna har samma kardinalitet, och därmed är lika "stora".

Den minsta kardinaliteten (kardinaltalet) är 0. Den tomma mängden har denna kardinalitet. Nästa större kardinalitet är 1 som är kardinaliteten för varje mängd med exakt ett element, och nästa kardinalitet är 2 som är kardinaliteten för varje mängd med exakt två element och så vidare. Varje naturligt tal ${\displaystyle n}$ är alltså ett kardinaltal för alla mängder med ${\displaystyle n}$ stycken element.

För oändliga mängder räcker inte de naturliga talen till som kardinaltal. ${\displaystyle \mathbb {N} }$ (mängden av de naturliga talen) har kardinaltalet Alef-0, eller ${\displaystyle \aleph _{0}}$. Alef-0 är det minsta oändliga kardinaltalet och betecknar en uppräknelig oändlighet. ${\displaystyle \mathbb {Z} }$ (mängden av heltalen) och ${\displaystyle \mathbb {Q} }$ (mängden av de rationella talen) har också kardinalitet ${\displaystyle \aleph _{0}}$, vilket kan visas genom att hitta ett sätt att räkna upp dem (d.v.s. ordna ett naturligt tal till varje element i respektive mängd). Nästa större kardinalitet är ${\displaystyle \aleph _{1}}$, sedan kommer ${\displaystyle \aleph _{2}}$, ${\displaystyle \aleph _{3}}$ osv. Mängder av dessa kardinaliteter är överuppräkneliga. Kardinaliteten av ${\displaystyle \mathbb {R} }$ (de reella talen), som kallas kontinuum och betecknas med lilla ${\displaystyle c}$, tillhör dessa. Enligt den oavgörbara kontinuumhypotesen finns dessutom inga kardinaltal mellan kontinuum och Alef-0, d.v.s. ${\displaystyle c=\aleph _{1}}$.^[3]

Cantors sats visar att det inte finns någon övre gräns på hur stora kardinaltal som kan bildas.^[4]

• Hilberts hotell