Cardinality

The car­di­nal­ity of a set is a for­mal­iza­tion of the “num­ber of el­e­ments” in the set.

Set car­di­nal­ity is an equiv­alence re­la­tion. Two sets have the same car­di­nal­ity if (and only if) there ex­ists a bi­jec­tion be­tween them.

Defi­ni­tion of equiv­alence classes

Finite sets

A set \(S\) has a car­di­nal­ity of a nat­u­ral num­ber \(n\) if there ex­ists a bi­jec­tion be­tween \(S\) and the set of nat­u­ral num­bers from \(1\) to \(n\). For ex­am­ple, the set \(\{9, 15, 12, 20\}\) has a bi­jec­tion with \(\{1, 2, 3, 4\}\), which is sim­ply map­ping the \(m\)th el­e­ment in the first set to \(m\); there­fore it has a car­di­nal­ity of \(4\).

We can see that this equiv­alence class is well-defined — if there ex­ist two sets \(S\) and \(T\), and there ex­ist bi­jec­tive func­tions \(f : S \to \{1, 2, 3, \ldots, n\}\) and \(g : \{1, 2, 3, \ldots, n\} \to T\), then \(g \circ f\) is a bi­jec­tion be­tween \(S\) and \(T\), and so the two sets also have the same car­di­nal­ity as each other, which is \(n\).

The car­di­nal­ity of a finite set is always a nat­u­ral num­ber, never a frac­tion or dec­i­mal.

In­finite sets

As­sum­ing the ax­iom of choice, the car­di­nal­ities of in­finite sets are rep­re­sented by the aleph num­bers. A set has a car­di­nal­ity of \(\aleph_0\) if there ex­ists a bi­jec­tion be­tween that set and the set of all nat­u­ral num­bers. This par­tic­u­lar class of sets is also called the class of countably in­finite sets.

Larger in­fini­ties (which are un­countable) are rep­re­sented by higher Aleph num­bers, which are \(\aleph_1, \aleph_2, \aleph_3,\) and so on through the or­di­nals.

In the ab­sence of the Ax­iom of Choice

Without the ax­iom of choice, not ev­ery set may be well-or­dered, so not ev­ery set bi­jects with an or­di­nal, and so not ev­ery set bi­jects with an aleph. In­stead, we may use the rather cun­ning Scott trick.

todo: Ex­am­ples and ex­er­cises (pos­si­bly as lenses)

todo: Split off a more ac­cessible car­di­nal­ity page that ex­plains the differ­ence be­tween finite, countably in­finite, and un­countably in­finite car­di­nal­ities with­out men­tion­ing alephs, or­di­nals, or the ax­iom of choice.

Parents:

  • Set

    An un­ordered col­lec­tion of dis­tinct ob­jects.