Cardinal numbers

From Cantor's Attic
Jump to: navigation, search


Cardinality is a measure of the size of a set. Two sets have the same cardinality---they are said to be equinumerous---when there is a one-to-one correspondence between their elements. The cardinality assignment problem is the problem of assigning to each equinumerosity class a cardinal number to represent it. In ZFC, this problem can be solved via the well-ordering principle, which asserts that every set can be well-ordered and therefore admits a bijection with a unique smallest ordinal, an initial ordinal. By this means, in ZFC we are able to assing to every set $X$ a canonical representative of its equinumerosity class, the smallest ordinal bijective with $X$.

We therefore adopt the definition that $\kappa$ is a cardinal if it is an initial ordinal, an ordinal that is not equinumerous with any smaller ordinal.

Finite and infinite cardinals

The set $\omega$ of natural numbers is the smallest inductive set, that is, the smallest set for which $0\in\omega$ and whenever $n\in\omega$ then also $n+1\in\omega$, where $n+1=n\cup\{n\}$ is the successor ordinal of $n$. A set is finite if it is equinumerous with a natural number, and otherwise it is is infinite. In ZFC, the finite sets are the same as the Dedekind finite sets, but in ZF, these concepts may differ. In ZFC, $\aleph$ is a unique order-isomorphism between the ordinals and the cardinal numbers with respect to membership.

Countable and uncoutable cardinals

A set is countable when it is equinumerous with a subset of $\omega$. This includes all finite sets, including the empty set, and the infinite countable sets are said to be countably infinite. An uncountable set is a set that is not countable. The existence of uncountable sets is a consequence of Cantor's observationt that the set of reals is uncountable.

Successor cardinals

Hartog established that for every set $X$, there is a smallest ordinal that does not have an injection into $X$, and this ordinal is now known as the Hartog number of $X$. When $\kappa$ is a cardinal, then the successor cardinal of $\kappa$, denoted $\kappa^+$, is the Hartog number of $\kappa$, the smallest ordinal of strictly larger cardinality than $\kappa$. The existence of successor cardinals can be proved in ZF without the axiom of choice. Iteratively taking the successor cardinal leads to the aleph hierarchy.

Regular and singular cardinals

A cardinal $\kappa$ is regular when $\kappa$ not the union of fewer than $\kappa$ many sets of size each less than $\kappa$. Otherwise, when $\kappa$ is the union of fewer than $\kappa$ many sets of size less than $\kappa$, then $\kappa$ is said to be singular.

The axiom of choice implies that every successor cardinal $\kappa^+$ is regular, but it is known to be consistent with ZF that successor cardinals may be singular.

The cofinality of an infinite cardinal $\kappa$, denoted $\text{cof}(\kappa)$, is the smallest size family of sets, each smaller than $\kappa$, whose union is all of $\kappa$. Thus, $\kappa$ is regular if and only if $\text{cof}(\kappa)=\kappa$, and singular if and only if $\text{cof}(\kappa)\lt\kappa$.

Cardinals in ZF

See general cardinal for an account of the cardinality concept arising without the axiom of choice.

When the axiom of choice is not available, the concept of cardinality is somewhat more subtle, and there is in general no fully satisfactory solution of the cardinal assignment problem. Rather, in ZF one works directly with the equinumerosity relation.

In ZF, the axiom of choice is equivalent to the assertion that the cardinals are linearly ordered. This is because for every set $X$, there is a smallest ordinal $\alpha$ that does not inject into $X$, the Hartog number of $X$, and conversely, if $X$ injects into $\alpha$, then $X$ would be well-orderable.

Dedekind finite sets

The Dedekind finite sets are those not equinumerous with any proper subset. Although in ZFC this is an equivalent characterization of the finite sets, in ZF the two concepts of finite differ: every finite set is Dedekind finite, but it is consistent with ZF that there are infinite Dedekind finite sets. An amorphous set is an infinite set, all of whose subsets are either finite or co-finite.