Cardinality

[summary(brief): The cardinality of a Set is a formalization of the "number of elements" in the set.]

[summary: If $A$ is a finite set then the cardinality of $A$, denoted $|A|$, is the number of elements $A$ contains. When $|A| = n$, we say that $A$ is a set of cardinality $n$. There exists a bijection from any finite set of cardinality $n$ to the set $\{0, …, (n-1)\}$ containing the first $n$ natural numbers.

Two infinite sets have the same cardinality if there exists a bijection between them. Any set in bijective correspondence with [45h $\mathbb N$] is called countably infinite, while any infinite set that is not in bijective correspondence with $\mathbb N$ is call uncountably infinite. All countably infinite sets have the same cardinality, whereas there are multiple distinct uncountably infinite cardinalities.]

[summary(technical): The cardinality (or size) $|X|$ of a set $X$ is the number of elements in $X.$ For example, letting $X = \{a, b, c, d\}, |X|=4.$

[todo: technical summary of infinite 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 [ordinal 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].

%%todo: Examples and exercises (possibly as lenses) %%

%%todo: 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.%%