Cardinality
by aoum, Mar 17, 2025, 11:20 PM
Cardinality: Measuring the Size of Sets
In mathematics, cardinality is a measure of the size or number of elements in a set. It provides a way to compare sets, including finite, infinite, and even "infinitely large" sets. Cardinality is a fundamental concept in set theory, which is the basis for much of modern mathematics.
1. Cardinality of Finite Sets
If a set has a finite number of elements, its cardinality is simply the count of those elements. For a finite set
, we denote its cardinality by 
.
For example:
![\[
A = \{1, 2, 3, 4\} \implies |A| = 4
\]](//latex.artofproblemsolving.com/b/7/2/b72b55840a42056e10560ffee57afdaaca0f99e4.png)
If two finite sets and 
have the same cardinality, there exists a bijection (a one-to-one correspondence) between them. For example, the sets:
![\[
A = \{a, b, c\}, \quad B = \{1, 2, 3\}
\]](//latex.artofproblemsolving.com/2/d/b/2dbb8852fda25573f8c022a779c022f84dc13418.png)
have the same cardinality because we can pair their elements:
![\[
a \leftrightarrow 1, \quad b \leftrightarrow 2, \quad c \leftrightarrow 3.
\]](//latex.artofproblemsolving.com/1/3/b/13b1be4036303fdc60bc734fa17dfbcda569cd00.png)
2. Cardinality of Infinite Sets
Infinite sets are more subtle to compare. Georg Cantor introduced the idea that not all infinities are the same size. To compare the cardinalities of infinite sets, we check whether a bijection exists between them.
Two sets have the same cardinality if and only if there is a bijection between them.
3. Countably Infinite Sets
A set is countably infinite if its elements can be put in one-to-one correspondence with the natural numbers
. Such sets have cardinality 
(aleph-null), the smallest infinite cardinal.
Examples of countably infinite sets:
Proof that
is countable:
We can list the integers in a sequence:
![\[
0, 1, -1, 2, -2, 3, -3, \dots
\]](//latex.artofproblemsolving.com/b/d/3/bd3afb540206f23a79700f3a0146d2a3801f803a.png)
This establishes a bijection with
:
![\[
f(n) = \begin{cases}
\frac{n}{2}, & \text{if $n$ is even} \\
-\frac{n-1}{2}, & \text{if $n$ is odd}.
\end{cases}
\]](//latex.artofproblemsolving.com/f/e/8/fe87e35b97273178a0fc832a5f5fd8c64520b2af.png)
4. Uncountably Infinite Sets
A set is uncountably infinite if it is larger than—that is, it cannot be placed in bijection with . Such sets have cardinality 
(the cardinality of the continuum).
The most famous example of an uncountably infinite set is the real numbers
.
Cantor’s Diagonal Argument:
To prove that is uncountable, Cantor showed that no bijection exists between and . The idea is to assume we have a list of all real numbers in 
:
![\[
x_1 = 0.a_{11} a_{12} a_{13} \dots, \quad x_2 = 0.a_{21} a_{22} a_{23} \dots, \quad \dots
\]](//latex.artofproblemsolving.com/e/1/1/e11110aeeedbd68a274cb168b58661f1359eda9d.png)
By constructing a new number that differs from each
in at least one decimal place, we create a real number not on the list, contradicting the assumption.
Thus,
, meaning is uncountably infinite.
5. Comparing Cardinalities
For any two sets and , we can compare their sizes:
Cantor's Theorem:
For any set
, the power set 
(the set of all subsets of ) has strictly greater cardinality:
![\[
|\mathcal{P}(S)| > |S|.
\]](//latex.artofproblemsolving.com/7/1/a/71a0664d27abb652fb2ae65b977b6f0920be3d1d.png)
For example,
, the cardinality of the continuum.
6. Cardinal Arithmetic
Cardinal numbers follow special arithmetic rules:
7. Continuum Hypothesis (CH)
The Continuum Hypothesis states:
![\[
\text{"There is no set whose cardinality is strictly between } \aleph_0 \text{ and } \mathfrak{c}."
\]](//latex.artofproblemsolving.com/7/7/6/776b450a6213c234b3bb048157883293997c7050.png)
In other words, the smallest uncountable cardinal is the cardinality of the real numbers:
![\[
2^{\aleph_0} = \aleph_1.
\]](//latex.artofproblemsolving.com/c/0/e/c0e34c802f0bdebfdb3b5266a98b0586a0938b07.png)
Kurt Gödel and Paul Cohen showed that the Continuum Hypothesis is independent of the standard axioms of set theory (ZFC), meaning it can neither be proved nor disproved.
8. Examples of Different Cardinalities
9. Summary
Cardinality provides a rigorous way to compare the sizes of sets:
References
In mathematics, cardinality is a measure of the size or number of elements in a set. It provides a way to compare sets, including finite, infinite, and even "infinitely large" sets. Cardinality is a fundamental concept in set theory, which is the basis for much of modern mathematics.
1. Cardinality of Finite Sets
If a set has a finite number of elements, its cardinality is simply the count of those elements. For a finite set
, we denote its cardinality by 
.For example:
![\[
A = \{1, 2, 3, 4\} \implies |A| = 4
\]](http://latex.artofproblemsolving.com/b/7/2/b72b55840a42056e10560ffee57afdaaca0f99e4.png)
If two finite sets
and 
have the same cardinality, there exists a bijection (a one-to-one correspondence) between them. For example, the sets:![\[
A = \{a, b, c\}, \quad B = \{1, 2, 3\}
\]](http://latex.artofproblemsolving.com/2/d/b/2dbb8852fda25573f8c022a779c022f84dc13418.png)
have the same cardinality because we can pair their elements:
![\[
a \leftrightarrow 1, \quad b \leftrightarrow 2, \quad c \leftrightarrow 3.
\]](http://latex.artofproblemsolving.com/1/3/b/13b1be4036303fdc60bc734fa17dfbcda569cd00.png)
2. Cardinality of Infinite Sets
Infinite sets are more subtle to compare. Georg Cantor introduced the idea that not all infinities are the same size. To compare the cardinalities of infinite sets, we check whether a bijection exists between them.
Two sets have the same cardinality if and only if there is a bijection between them.
3. Countably Infinite Sets
A set is countably infinite if its elements can be put in one-to-one correspondence with the natural numbers
. Such sets have cardinality 
(aleph-null), the smallest infinite cardinal.Examples of countably infinite sets:
- The natural numbers:
- The integers:
- The rational numbers:
Proof that
is countable:We can list the integers in a sequence:
![\[
0, 1, -1, 2, -2, 3, -3, \dots
\]](http://latex.artofproblemsolving.com/b/d/3/bd3afb540206f23a79700f3a0146d2a3801f803a.png)
This establishes a bijection with
:![\[
f(n) = \begin{cases}
\frac{n}{2}, & \text{if $n$ is even} \\
-\frac{n-1}{2}, & \text{if $n$ is odd}.
\end{cases}
\]](http://latex.artofproblemsolving.com/f/e/8/fe87e35b97273178a0fc832a5f5fd8c64520b2af.png)
4. Uncountably Infinite Sets
A set is uncountably infinite if it is larger than
—that is, it cannot be placed in bijection with . Such sets have cardinality 
(the cardinality of the continuum).The most famous example of an uncountably infinite set is the real numbers
.Cantor’s Diagonal Argument:
To prove that
is uncountable, Cantor showed that no bijection exists between and . The idea is to assume we have a list of all real numbers in 
:![\[
x_1 = 0.a_{11} a_{12} a_{13} \dots, \quad x_2 = 0.a_{21} a_{22} a_{23} \dots, \quad \dots
\]](http://latex.artofproblemsolving.com/e/1/1/e11110aeeedbd68a274cb168b58661f1359eda9d.png)
By constructing a new number that differs from each
in at least one decimal place, we create a real number not on the list, contradicting the assumption.Thus,
, meaning is uncountably infinite.5. Comparing Cardinalities
For any two sets
and , we can compare their sizes:- If
, there is a bijection between and . - If
, there is an injection (one-to-one map) from to . - If
, there is an injection but no bijection from to .
,
,
,Cantor's Theorem:
For any set
, the power set 
(the set of all subsets of ) has strictly greater cardinality:![\[
|\mathcal{P}(S)| > |S|.
\]](http://latex.artofproblemsolving.com/7/1/a/71a0664d27abb652fb2ae65b977b6f0920be3d1d.png)
For example,
, the cardinality of the continuum.6. Cardinal Arithmetic
Cardinal numbers follow special arithmetic rules:
7. Continuum Hypothesis (CH)
The Continuum Hypothesis states:
![\[
\text{"There is no set whose cardinality is strictly between } \aleph_0 \text{ and } \mathfrak{c}."
\]](http://latex.artofproblemsolving.com/7/7/6/776b450a6213c234b3bb048157883293997c7050.png)
In other words, the smallest uncountable cardinal is the cardinality of the real numbers:
![\[
2^{\aleph_0} = \aleph_1.
\]](http://latex.artofproblemsolving.com/c/0/e/c0e34c802f0bdebfdb3b5266a98b0586a0938b07.png)
Kurt Gödel and Paul Cohen showed that the Continuum Hypothesis is independent of the standard axioms of set theory (ZFC), meaning it can neither be proved nor disproved.
8. Examples of Different Cardinalities
- Finite sets:
- Countably infinite:
- Uncountably infinite:
- Power sets:
9. Summary
Cardinality provides a rigorous way to compare the sizes of sets:
- Finite sets have a natural cardinality (a non-negative integer).
- Infinite sets are either countably infinite () or uncountably infinite ( and beyond).
- Cantor's theorem shows that there are infinitely many sizes of infinity.
- The Continuum Hypothesis remains unresolved within standard mathematics.
References
- Wikipedia: Cardinality
- Cantor, G. Contributions to the Founding of the Theory of Transfinite Numbers.
- Halmos, P. Naive Set Theory (1974).
- AoPS Wiki: Cardinality
April 2025
March 2025