Cardinal Number - Formal Definition

Formal Definition

Formally, assuming the axiom of choice, the cardinality of a set X is the least ordinal α such that there is a bijection between X and α. This definition is known as the von Neumann cardinal assignment. If the axiom of choice is not assumed we need to do something different. The oldest definition of the cardinality of a set X (implicit in Cantor and explicit in Frege and Principia Mathematica) is as the class of all sets that are equinumerous with X. This does not work in ZFC or other related systems of axiomatic set theory because if X is non-empty, this collection is too large to be a set. In fact, for X ≠ ∅ there is an injection from the universe into by mapping a set m to {m} × X and so by limitation of size, is a proper class. The definition does work however in type theory and in New Foundations and related systems. However, if we restrict from this class to those equinumerous with X that have the least rank, then it will work (this is a trick due to Dana Scott: it works because the collection of objects with any given rank is a set).

Formally, the order among cardinal numbers is defined as follows: |X| ≤ |Y| means that there exists an injective function from X to Y. The Cantor–Bernstein–Schroeder theorem states that if |X| ≤ |Y| and |Y| ≤ |X| then |X| = |Y|. The axiom of choice is equivalent to the statement that given two sets X and Y, either |X| ≤ |Y| or |Y| ≤ |X|.

A set X is Dedekind-infinite if there exists a proper subset Y of X with |X| = |Y|, and Dedekind-finite if such a subset doesn't exist. The finite cardinals are just the natural numbers, i.e., a set X is finite if and only if |X| = |n| = n for some natural number n. Any other set is infinite. Assuming the axiom of choice, it can be proved that the Dedekind notions correspond to the standard ones. It can also be proved that the cardinal (aleph null or aleph-0, where aleph is the first letter in the Hebrew alphabet, represented ) of the set of natural numbers is the smallest infinite cardinal, i.e. that any infinite set has a subset of cardinality The next larger cardinal is denoted by and so on. For every ordinal α there is a cardinal number and this list exhausts all infinite cardinal numbers.