Questions tagged [cardinals]

Cardinality is a notion of size for sets, usually denoted by $|A|$ as the "cardinality of $A$". With finite sets the cardinality is simply the number of elements which are members of a set.

Dealing with infinite sets we can measure them in different ways. Cardinal numbers are very natural in the sense that they do not require extra structure (such as relations and operations defined on the set to be preserved).

In formal terms, suppose $f\colon A\to B$ (i.e. $f$ is a function whose domain is $A$ and its range is a subset of $B$).

We say that $f$ is injective if $f(a)=f(b)$ implies $a=b$; we say $f$ is surjective if its range is all $B$, namely for any $b\in B$ there is $a\in A$ such that $f(a)=b$.

If $f$ is both surjective and injective we say that $f$ is a bijection from $A$ to $B$. The inverse of a bijection is also a bijection.

Now we can define an equivalence relation on sets, $A\sim B$ if and only if there is some $f\colon A\to B$ which is a bijection.

Assuming the Axiom of Choice, we have that every set can be well ordered, and therefore there is a least ordinal which is equivalent to $A$, so we can assign it as a canonical representative for the equivalence class, usually denoted by $\aleph_\alpha$ where $\alpha$ is an ordinal, or as general Greek letters such as $\kappa,\lambda$.

Before defining the $\aleph$ numbers we need to define initial ordinals. Let $\alpha$ be an ordinal, if there is no $\beta<\alpha$ and $f\colon\alpha\to\beta$ which is a bijection, then $\alpha$ is called an initial ordinal.

The $\aleph$ numbers are defined by transfinite induction as:

1. $\aleph_0 = |\omega| = \omega$ (note that $\omega$ is an initial ordinal),
2. $\aleph_{\alpha+1} = \aleph_\alpha^+$ (where the $\cdot^+$ means the smallest initial ordinal above the one defined for $\aleph_\alpha$)
3. If $\beta$ is a limit ordinal, then $\displaystyle\aleph_\beta = \bigcup_{\delta<\beta}\aleph_\delta$ (It is easy to verify that the union of initial ordinals is an initial ordinal).

The confinality of an $\aleph$ number is the minimal cardinality of a set which is unbounded in the initial ordinal matching the $\aleph$ number.

A cardinal is called regular if its cofinality is itself, otherwise it is called singular.

Example: $\aleph_0$ is regular, because for a set to be unbounded below $\omega$ it cannot be finite.

$\aleph_1$ is also regular, every ordinal below $\omega_1$ is countable, and the union of countably many countable ordinals is just countable - which is still below $\aleph_1$.

Example: $\aleph_\omega$ is singular, recall $\displaystyle\aleph_\omega=\bigcup_{n<\omega}\aleph_n$. Therefore the set $\{\omega_n\mid n<\omega\}$ (the collection of initial ordinals whose cardinality is less than $\aleph_\omega$) is unbounded, and its cardinality is merely countable.

The question whether or not there exists $\aleph_\delta$ such that $\delta$ is a limit ordinal, but $\aleph_\delta$ is regular is unprovable in ZFC. It is known that it is consistent that there are none, but unknown that it is inconsistent that there are. Cardinals with this property are called Large cardinals and are used for consistency proofs.

In the absence of choice we can no longer have canonical representatives for the equivalence classes, and things become tricky. The class of cardinals can still be defined, however in a slightly different way - usually Scott's trick.

However, to show how things can break down it is consistent with ZF that there is no choice function on the equivalence classes (i.e. you cannot have canonical representatives).