# 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.