In mathematics, a cardinal number, or cardinal for short, is a kind of number that measures the cardinality of a set, i.e., how many elements there are in a set. The cardinal number associated with a set is generally denoted by , with a vertical bar on each side, though it may also be denoted by , or
Cardinality is defined in terms of bijective functions. Two sets have the same cardinality if, and only if, there is a one-to-one correspondence (bijection) between the elements of the two sets. The cardinality of a finite set can be identified with a natural number, which can be found simply by counting its elements. For example, the sets and both have the same cardinality 3, as evidenced by the bijection .
The behavior of cardinalities of infinite sets is more complex. For example, there exists a bijection between the set of all natural numbers and the set of all rational numbers , and thus even though is a proper subset of —something that cannot happen with proper subsets of finite sets. However, a fundamental theorem due to Georg Cantor shows that it is possible for two infinite sets to have different cardinalities, and in particular the cardinality of the set of real numbers is greater than the cardinality of .
The cardinality of is usually denoted by (aleph-null), since it is the smallest aleph number. The properties of other aleph numbers and of infinite cardinal numbers in general depend on statements independent of Zermelo–Fraenkel set theory, such as the axiom of choice and the continuum hypothesis. For example, all infinite cardinal numbers are aleph numbers if and only if the axiom of choice is true.
Cardinality is studied for its own sake as part of set theory. It is also a tool used in branches of mathematics including model theory, combinatorics, abstract algebra and mathematical analysis. In category theory, the cardinal numbers form a skeleton of the category of sets.
Motivation A natural number can be used for two purposes: to describe the size of a set, or to describe the position of an element in a sequence. These two notions diverge when generalized to infinite sets and sequences, with the position aspect leading to ordinal numbers, and the size aspect leading to cardinal numbers.
When considering the size of a set, the identities of individual members should be abstracted away; changing these individual members should not affect the size of the set, as long as they remain distinct from each other. For example, the set has three elements, so when one replaces its members following the mapping , the resulting set still has three elements. It is reasonable to further postulate that two sets and have the same size if and only if such a mapping—a bijection—exists from to . This is exactly how the formal concept of cardinality is defined.
Sameness of cardinality is an equivalence relation. It is sometimes referred to as equipotence, equipollence, or equinumerosity. It is thus said that two sets with the same cardinality are, respectively, equipotent, equipollent, or equinumerous. Every equivalence class of sets under equinumerosity corresponds to a cardinal number.
For finite sets, cardinal numbers defined this way agree with the intuitive notion of numbers of elements (as a natural number), but infinite sets exhibit more complex behaviors. A classic example is Hilbert's paradox of the Grand Hotel, which uses the following mapping: 1 ↦ 2 2 ↦ 3 3 ↦ 4 ... n ↦ n + 1 ... This is a bijection between the sets and , and thus they have the same cardinality , despite the second being a proper subset of the first. Therefore the intuition that the size of a proper subset of is always strictly less than the size of is usually only valid for finite sets. Conversely, this also shows that (the cardinality of plus the cardinality of is equal to the cardinality of ), and thus the "plus one" operation does not always construct a new cardinal number as it does for natural numbers.
However, Cantor's diagonal argument shows that the power set operation always results in a strictly greater cardinality, allowing one to construct a larger cardinal number from any infinite cardinal number. For example, it can be shown that the cardinality of the set of real numbers is equal to , and thus there are strictly more real numbers than natural numbers.
Cardinality function The cardinality function is a cardinal function that takes in a set and returns its cardinal number: . However, it is somewhat difficult to define "cardinal number" formally, especially for infinite sets. Therefore, cardinal numbers are not usually thought of in terms of their formal definition, but immaterially in terms of their arithmetic/algebraic properties. The only fundamental requirement on a cardinality function is:
The assumption that there is some function that satisfies this requirement is sometimes called the axiom of cardinality or Hume's principle. It will be shown later that such a function can be constructed without the need to define it axiomatically.
An alternative approach is to define an equality relation for cardinal numbers that may be different from the equality relation for sets, and use to develop the theory of cardinality. Specifically, Moschovakis defines a (weak) cardinal assignment as an operation that satisfies (with the motivation that the cardinality of should be represented by an "abstract" object that is equinumerous to ). The relation is then the same as the equinumerosity relation between sets. If a cardinal assignment also satisfies , then it is a strong cardinal assignment.
Constructive definition Von Neumann cardinal assignment The most commonly used (strong) cardinal assignment, which relies on the axiom of choice, is the von Neumann cardinal assignment, which represents the cardinality of a set with (the von Neumann representation of) the least ordinal number such that there is a bijection between and . This ordinal number is also known as the initial ordinal of the cardinal number .
When is a finite set, all possible well-orderings of has the same order type; conversely, all finite ordinals have different cardinalities, and thus all finite ordinals are initial ordinals. Under their respective von Neumann representations, both finite ordinals and finite cardinals are identified with von Neumann natural numbers, and cardinal and ordinal arithmetic (addition, multiplication, power, proper subtraction) give the same answers for finite numbers.
On the other hand, many different infinite ordinal numbers can have the same cardinality. For example, the first infinite ordinal has the same cardinality as , , , ..., all of which are countable ordinals. Among these, only itself is an initial ordinal.
The -th infinite initial ordinal is written . Its cardinality is written (the -th aleph number). For example, is also written as , and its cardinality (the cardinality of any countable set) as . The von Neumann cardinal assignment identifies with , but the notation is used for writing cardinals, and for writing ordinals. This is important because arithmetic on cardinals is different from arithmetic on ordinals. For example, in ordinal arithmetic while in cardinal arithmetic, even though under the von Neumann cardinal assignment and are represented by the same set.
Also, is the smallest uncountable ordinal (to see that it exists, consider the set of equivalence classes of well-orderings of the natural numbers; each such well-ordering defines a countable ordinal, and is the order type of that set), is the smallest ordinal whose cardinality is greater than , and so on, and is the limit of for natural numbers (any limit of cardinals is a cardinal, so this limit is indeed the first cardinal after all the ).
Infinite initial ordinals are limit ordinals. Using ordinal arithmetic, implies , and 1 ≤ α < ωβ implies α·ωβ = ωβ, and 2 ≤ α < ωβ implies αωβ = ωβ. Using the Veblen hierarchy, β ≠ 0 and α < ωβ imply and Γωβ = ωβ. Indeed, one can go far beyond this. So as an ordinal, an infinite initial ordinal is an extremely strong kind of limit.
Scott cardinals If the axiom of choice is not assumed, then a different approach is needed. The oldest explicit definition of the cardinality of a set X (in Frege and Principia Mathematica) is as the class [X] 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 [X] by mapping a set m to {m} × X, and so by the axiom of limitation of size, [X] 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).
Some sources use a mixed definition between von Neumann cardinals and Scott cardinals. For example, Lévy defines as the von Neumann cardinal when is well-orderable, and as the Scott cardinal otherwise. This convention retains the convenience provided by the von Neumann representation for studying well ordered cardinals, which is still a significant part of cardinal study even when the axiom of choice is not assumed.
Cardinal comparison 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|.Enderton, Herbert. "Elements of Set Theory", Academic Press Inc., 1977.
A set X is called 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, by definition, a set X is finite if and only if |X| = |n| = n for some natural number n. Any other set is infinite. It can be proven (without the axiom of choice) that any Dedekind-infinite set is infinite. Assuming the axiom of choice, it can be proved that the Dedekind notions correspond to the standard ones.
Aleph numbers
The aleph numbers are the cardinalities of well-orderable infinite sets. They are denoted with the Hebrew letter (aleph) marked with a subscript indicating their rank among aleph numbers. Since aleph numbers can be identified with their initial ordinals, they form a transfinite sequence:
For every ordinal , there exists an aleph number . If the axiom of choice is true, then all sets are well-orderable (by the well-ordering theorem), and thus all infinite cardinal numbers are aleph numbers, i.e., this transfinite sequence is in fact the list of all infinite cardinal numbers.
If the axiom of choice is not true (see ), then there exist sets that are not well-orderable, and thus infinite cardinals that are not aleph numbers. Such a cardinal must be incomparable to some aleph number by Hartogs's theorem, so in this case it is impossible to write all cardinal numbers in a totally ordered sequence.
Cardinal arithmetic We can define arithmetic operations on cardinal numbers that generalize the ordinary operations for natural numbers. It can be shown that for finite cardinals, these operations coincide with the usual operations for natural numbers. Furthermore, these operations share many properties with ordinary arithmetic.
Successor cardinal