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 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, \dots, n}$ and $g : {1, 2, 3, \dots, 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 $ℵ_{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 $ℵ_{1}, ℵ_{2}, ℵ_{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.

Examples and exercises (possibly as lenses)

Split off a more accessible cardinality page that explains the difference between finite, countably infinite, and uncountably infinite cardinalities without mentioning alephs, ordinals, or the axiom of choice.

Cardinality