Cardinal number
Formal definition

Formally, assuming the axiom of choice, the cardinality of a set X is the least ordinal number α 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, then a different approach is needed. 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 the axiom of 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).

Von Neumann cardinal assignment implies that the cardinal number of a finite set is the common ordinal number of all possible well-orderings of that set, and cardinal and ordinal arithmetic (addition, multiplication, power, proper subtraction) then give the same answers for finite numbers. However, they differ for infinite numbers. For example, 2 ω = ω < ω 2 {\displaystyle 2^{\omega }=\omega <\omega ^{2}} in ordinal arithmetic while 2 ℵ 0 > ℵ 0 = ℵ 0 2 {\displaystyle 2^{\aleph _{0}}>\aleph _{0}=\aleph _{0}^{2}} in cardinal arithmetic, although the von Neumann assignment puts ℵ 0 = ω {\displaystyle \aleph _{0}=\omega }. On the other hand, Scott's trick implies that the cardinal number 0 is { ∅ } {\displaystyle \{\emptyset \}}, which is also the ordinal number 1, and this may be confusing. A possible compromise (to take advantage of the alignment in finite arithmetic while avoiding reliance on the axiom of choice and confusion in infinite arithmetic) is to apply von Neumann assignment to the cardinal numbers of finite sets (those which can be well ordered and are not equipotent to proper subsets) and to use Scott's trick for the cardinal numbers of other sets.

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 does not exist. The finite cardinals are just the natural numbers, in the sense that 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 ℵ 0 {\displaystyle \aleph _{0}} (aleph null or aleph-0, where aleph is the first letter in the Hebrew alphabet, represented ℵ {\displaystyle \aleph }) of the set of natural numbers is the smallest infinite cardinal (i.e., any infinite set has a subset of cardinality ℵ 0 {\displaystyle \aleph _{0}}). The next larger cardinal is denoted by ℵ 1 {\displaystyle \aleph _{1}}, and so on. For every ordinal α, there is a cardinal number ℵ α, {\displaystyle \aleph _{\alpha },} and this list exhausts all infinite cardinal numbers.
detectable_content:postscript, detectable_format:title