Cardinality

Cardinality#

Definition. Two sets have the same cardinality if there exists a one-to-one mapping between the two.

This is an equivalence relation so that the equivalence classes can be assigned cardinal numbers (along with the Axiom of Regularity; alternatively, without referring to the equivalence relation, Axiom of Choice). The cardinal number of the set \(X\) is denoted \(|X|\). From the Axiom of Choice it follows that every set can be well-ordered, which defines cardinals in ZFC.

A set \(X\) is finite if \(|X|=|n|\) for some \(n\in\mathbb{N}\); finite cardinals are then defined as natural numbers. The ordering of cardinal numbers is defined as \(|X|\leq |Y|\) if there exists an injective map of \(X\) into \(Y\). Now the diagonal argument shows that this concept is not trivial:

Theorem. (Diagonal Argument.) For every set \(X\), \(|X| < |P(X)|\).

The Cantor-Bernstein theorem show that \(<\) is a partial ordering of cardinal numbers:

Theorem. (Cantor-Bernstein.) If \(|A|\leq|B|\) and \(|B|\leq|A|\) then we have \(|A|=|B|\).

Cardinal Arithmetic#

Arithmetic operations can be defined on cardinals, with \(|A| = \kappa, |B| = \lambda\):

• \(\kappa+\lambda = |A\cup B|\) where \(A\) and \(B\) are disjoint and \(|A|=\kappa\) and \(|B|=\lambda\),
• \(\kappa\cdot\lambda = |A\times B|\) ,
• \(\kappa^\lambda = |A^B|\).

Both \(+\) and \(\cdot\) are associative, commutative and distributive. Cardinal arithmetic is more “regular” than ordinal arithmetic.

The cardinality of powersets is special:

Lemma. If \(|A| = \kappa\) then \(|P(A)| = 2^\kappa\).

Thus the diagonal argument shows that for every cardinal \(\kappa\) we have \(\kappa < 2^\kappa\).