Cardinality

The cardinality of a set is a formalization of the “number of elements” in the set.

Set cardinality is an equivalence relation. Two sets have the same cardinality if (and only if) there exists a bijection between them.

Definition of equivalence classes

Finite sets

A set \(S\) has a cardinality of a natural number \(n\) if there exists a bijection between \(S\) and the set of natural numbers from \(1\) to \(n\). For example, the set \(\{9, 15, 12, 20\}\) has a bijection with \(\{1, 2, 3, 4\}\), which is simply mapping the \(m\)th element in the first set to \(m\); therefore it has a cardinality of \(4\).

We can see that this equivalence class is well-defined — if there exist two sets \(S\) and \(T\), and there exist bijective functions \(f : S \to \{1, 2, 3, \ldots, n\}\) and \(g : \{1, 2, 3, \ldots, n\} \to T\), then \(g \circ f\) is a bijection between \(S\) and \(T\), and so the two sets also have the same cardinality as each other, which is \(n\).

The cardinality of a finite set is always a natural number, never a fraction or decimal.

Infinite sets

Assuming the axiom of choice, the cardinalities of infinite sets are represented by the aleph numbers. A set has a cardinality of \(\aleph_0\) if there exists a bijection between that set and the set of all natural numbers. This particular class of sets is also called the class of countably infinite sets.

Larger infinities (which are uncountable) are represented by higher Aleph numbers, which are \(\aleph_1, \aleph_2, \aleph_3,\) and so on through the ordinals.

In the absence of the Axiom of Choice

Without the axiom of choice, not every set may be well-ordered, so not every set bijects with an ordinal, and so not every set bijects with an aleph. Instead, we may use the rather cunning Scott trick.