Cardinal number

, f: X → Y, from set X to set Y demonstrates that the sets have the same cardinality, in this case equal to the cardinal number 4. , the smallest infinite cardinal In mathematics, a cardinal number, or cardinal for short, is a kind of…

Uses your system voice; voice and rate in settings.

≈ 13 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

f: X → Y, from set X to set Y demonstrates that the sets have the same cardinality, in this case equal to the cardinal number 4. , the smallest infinite cardinal 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 A , \operatorname{card}(A), or \#A. 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. A \sim B \iff |A| = |B|.

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 ).{{efn|Moschovakis' original definition also requires that for each set of sets , {{tmath|\{\vert X \vert \mid X \in \mathcal{E}\} }} is a set, but this is satisfied for free when the axiom schema of replacement is assumed.}} 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. The \alpha -th infinite initial ordinal is written \omega_\alpha . Its cardinality is written \aleph_{\alpha} (the \alpha -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 \omega_{\alpha} with \aleph_{\alpha} , but the notation \aleph_{\alpha} is used for writing cardinals, and \omega_{\alpha} for writing ordinals. This is important because arithmetic on cardinals is different from arithmetic on ordinals.

For example, 2^\omega=\omega in ordinal arithmetic while 2^{\aleph_0}>\aleph_0=\aleph_0^2 in cardinal arithmetic, even though under the von Neumann cardinal assignment and are represented by the same set. Also, \omega_{1} 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 \omega_{1} is the order type of that set), \omega_{2} is the smallest ordinal whose cardinality is greater than \aleph_{1} , and so on, and \omega_{\omega} is the limit of \omega_{n} for natural numbers n (any limit of cardinals is a cardinal, so this limit is indeed the first cardinal after all the \omega_{n} ).

Infinite initial ordinals are limit ordinals. Using ordinal arithmetic, \alpha implies \alpha+\omega_{\beta}=\omega_{\beta} , and 1 ≤ α β implies α·ω β = ω β , and 2 ≤ α β implies α ω β = ω β . Using the Veblen hierarchy, β ≠ 0 and α β imply \varphi_{\alpha}(\omega_{\beta}) = \omega_{\beta} \, and Γ ω β = ω β .

Indeed, one can go far beyond this. So as an ordinal, an infinite initial ordinal is an extremely strong kind of limit. 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 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_0 = |\mathbb{N}|,\; \aleph_1,\; \aleph_2,\; \ldots,\; \aleph_{\alpha},\; \ldots. 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. |X| + |Y| = | X \cup Y|. Zero is an additive identity κ + 0 = 0 + κ = κ. Addition is associative (κ + μ) + ν = κ + (μ + ν).

Addition is commutative κ + μ = μ + κ. Addition is non-decreasing in both arguments: (\kappa \le \mu) \rightarrow ((\kappa + \nu \le \mu + \nu) \mbox{ and } (\nu + \kappa \le \nu + \mu)). Assuming the axiom of choice, addition of infinite cardinal numbers is easy.

If either κ or μ is infinite, then \kappa + \mu = \max\{\kappa, \mu\}\,. Assuming the axiom of choice and, given an infinite cardinal σ and a cardinal μ, there exists a cardinal κ such that μ + κ = σ if and only if μ ≤ σ. It will be unique (and equal to σ) if and only if μ |X|\cdot|Y| = |X \times Y| Zero is a multiplicative absorbing element: κ·0 = 0·κ = 0.

There are no nontrivial zero divisors: κ·μ = 0 → (κ = 0 or μ = 0). One is a multiplicative identity: κ·1 = 1·κ = κ. Multiplication is associative: (κ·μ)·ν = κ·(μ·ν).

Multiplication is commutative: κ·μ = μ·κ. Multiplication is non-decreasing in both arguments: κ ≤ μ → (κ·ν ≤ μ·ν and ν·κ ≤ ν·μ). Multiplication distributes over addition: κ·(μ + ν) = κ·μ + κ·ν and (μ + ν)·κ = μ·κ + ν·κ.

Assuming the axiom of choice, multiplication of infinite cardinal numbers is also easy. If either κ or μ is infinite and both are non-zero, then \kappa\cdot\mu = \max\{\kappa, \mu\}. Thus the product of two infinite cardinal numbers is equal to their sum.

Assuming the axiom of choice and given an infinite cardinal π and a non-zero cardinal μ, there exists a cardinal κ such that μ · κ = π if and only if μ ≤ π. It will be unique (and equal to π) if and only if μ |X|^ = \left|X^Y\right|, where X Y is the set of all functions from Y to X. It is easy to check that the right-hand side depends only on and . κ 0 = 1 (in particular 0 0 = 1), see empty function.

If μ ≥ 1, then 0 μ = 0. 1 μ = 1. κ 1 = κ. κ μ + ν = κ μ ·κ ν . κ μ · ν = (κ μ ) ν . (κ·μ) ν = κ ν ·μ ν .

Exponentiation is non-decreasing in both arguments: (1 ≤ ν and κ ≤ μ) → (ν κ ≤ ν μ ) and (κ ≤ μ) → (κ ν ≤ μ ν ). 2 |X| is the cardinality of the power set of the set X and Cantor's diagonal argument shows that 2 |X| > |X| for any set X. This proves that no largest cardinal exists (because for any cardinal κ, we can always find a larger cardinal 2 κ ).

In fact, the class of cardinals is a proper class. (This proof fails in some set theories, notably New Foundations.) All the remaining propositions in this section assume the axiom of choice: If κ and μ are both finite and greater than 1, and ν is infinite, then κ ν = μ ν .

If κ is infinite and μ is finite and non-zero, then κ μ = κ. If 2 ≤ κ and 1 ≤ μ and at least one of them is infinite, then: max (κ, 2 μ ) ≤ κ μ ≤ max (2 κ , 2 μ ). Using Kőnig's theorem, one can prove κ cf(κ) and κ κ ) for any infinite cardinal κ, where cf(κ) is the cofinality of κ.

Assuming the axiom of choice and, given an infinite cardinal κ and a finite cardinal μ greater than 0, the cardinal ν satisfying \nu^\mu = \kappa will be \kappa . Assuming the axiom of choice and, given an infinite cardinal κ and a finite cardinal μ greater than 1, there may or may not be a cardinal λ satisfying \mu^\lambda = \kappa .

However, if such a cardinal exists, it is infinite and less than κ, and any finite cardinality ν greater than 1 will also satisfy \nu^\lambda = \kappa . The logarithm of an infinite cardinal number κ is defined as the least cardinal number μ such that κ ≤ 2 μ .

Logarithms of infinite cardinals are useful in some fields of mathematics, for example in the study of cardinal invariants of topological spaces, though they lack some of the properties that logarithms of positive real numbers possess. The continuum hypothesis (CH) states that there are no cardinals strictly between \aleph_0 and 2^{\aleph_0}.

The latter cardinal number is also often denoted by \mathfrak{c} ; it is the cardinality of the continuum (the set of real numbers). In this case 2^{\aleph_0} = \aleph_1. Similarly, the generalized continuum hypothesis (GCH) states that for every infinite cardinal \kappa , there are no cardinals strictly between \kappa and 2^\kappa .

Both the continuum hypothesis and the generalized continuum hypothesis have been proved to be independent of the usual axioms of set theory, the Zermelo–Fraenkel axioms together with the axiom of choice (ZFC). Indeed, Easton's theorem shows that, for regular cardinals \kappa , the only restrictions ZFC places on the cardinality of 2^\kappa are that \kappa , and that the exponential function is non-decreasing.

The notion of cardinality, as now understood, was formulated by Georg Cantor, the originator of set theory, in 1874–1884. Cantor noted that there is a bijection between two finite sets if and only if they have the same number of elements, and applied this concept of bijection to infinite sets (for example the set of natural numbers N = {0, 1, 2, 3, ...}).

Thus, he called all sets having a bijection with N denumerable (countably infinite) sets, which all share the same cardinal number. He called the cardinal numbers of infinite sets transfinite cardinal numbers. Cantor proved that any unbounded subset of N has the same cardinality as N, even though this might appear to run contrary to intuition.

He also proved that the set of all ordered pairs of natural numbers is denumerable; this implies that the set of all rational numbers is also denumerable, since every rational can be represented by a pair of integers. He later proved that the set of all real algebraic numbers is also denumerable.

Each real algebraic number z may be encoded as a finite sequence of integers, which are the coefficients in the polynomial equation of which it is a solution, i.e. the ordered n-tuple (a 0 , a 1 , ..., a n ), a i ∈ Z together with a pair of rationals (b 0 , b 1 ) such that z is the unique root (if it exists) of the polynomial with coefficients (a 0 , a 1 , ..., a n ) that lies in the interval (b 0 , b 1 ). In his 1874 paper "On a Property of the Collection of All Real Algebraic Numbers", Cantor proved that there exist higher-order cardinal numbers, by showing that the set of real numbers has cardinality greater than that of N. His proof used an argument with nested intervals, but in an 1891 paper, he proved the same result using his ingenious and much simpler diagonal argument.

The new cardinal number of the set of real numbers is called the cardinality of the continuum and Cantor used the symbol \mathfrak{c} for it. Cantor also developed a large portion of the general theory of cardinal numbers; he proved that (assuming the axiom of choice) there is a smallest transfinite cardinal number ( \aleph_0 , aleph-null), and that for every cardinal number there is a next-larger cardinal (\aleph_1, \aleph_2, \aleph_3, \ldots).

Cantor formulated the continuum hypothesis in 1878. In 1940, Kurt Gödel showed that the continuum hypothesis cannot be disproved from ZFC, and in 1963, Paul Cohen showed that it cannot be proved from ZFC either, establishing its independence.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365179595 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001365179595 · captured 2026-07-20 · ledger · version history

Cite this page as: encyclopegia.org, “Cardinal number”, snapshot enwiki-001365179595. https://encyclopegia.org/a/cardinal-number

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.