Cardinal number: Difference between revisions

From Wikipedia
Jump to navigation Jump to search
Browse history interactively
VisualWikitext
imported>Jochen Burghardt
→top: then remove repeated link
 
imported>Beland
m MOS:RADICAL, MOS:YOU, more consistent whitespace for math (via WP:JWB)
 
Line 7: Line 7:
[[File:Aleph0.svg|thumb|right|150px|[[Aleph-null]], the smallest infinite cardinal]]
[[File:Aleph0.svg|thumb|right|150px|[[Aleph-null]], the smallest infinite cardinal]]


In [[mathematics]], a '''cardinal number''', or '''cardinal''' for short, is what is commonly called the number of elements of a [[set (mathematics)|set]]. In the case of a [[finite set]], its cardinal number, or cardinality is therefore a [[natural number]]. For dealing with the case of [[infinite set]]s, the [[transfinite number|infinite cardinal number]]s have been introduced, which are often denoted with the [[Hebrew alphabet|Hebrew letter]] <math>\aleph</math> ([[Aleph (Hebrew)|aleph]]) marked with subscript indicating their rank among the infinite cardinals.
In [[mathematics]], a '''cardinal number''', or '''cardinal''' for short, is a kind of [[number]] that measures the [[cardinality]] of a [[set (mathematics)|set]], i.e., how many elements there are in a set. The cardinal number associated with a set {{tmath|A}} is generally denoted by {{tmath|\vert A \vert}}, with a [[vertical bar]] on each side,<ref>{{Harvard citation no brackets|Hrbáček|Jech|2017|p=65}} {{br}}</ref> though it may also be denoted by  <span style="border-top: 3px double;"><math>A</math></span>, <math>\operatorname{card}(A),</math> or <math>\#A.</math>{{refn|1=<span style="border-top: 3px double;"><math>A</math></span>{{Sfn|Kuratowski|1968|p=174}}{{Sfn|Suppes|1972|p=109}} {{br}}
<math>\operatorname{card}(A)</math>{{Sfn|Bourbaki|1968|p=158}}{{Sfn|Enderton|1977|p=136}}{{br}}
<math>\#A</math>{{Sfn|Halmos|1998|p=53}}{{Sfn|Tao|2022|p=60}}}}


Cardinality is defined in terms of [[bijective function]]s. 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. In the case of finite sets, this agrees with the intuitive notion of number of elements. In the case of infinite sets, the behavior is more complex. 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 number]]s is greater than the cardinality of the set of natural numbers. It is also possible for a [[proper subset]] of an infinite set to have the same cardinality as the original set—something that cannot happen with proper subsets of finite sets.
Cardinality is defined in terms of [[bijective function]]s. 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 {{tmath|\{1,2,3\} }} and {{tmath|\{4,5,6\} }} both have the same cardinality 3, as evidenced by the bijection {{tmath|\{1 \mapsto 4, 2 \mapsto 5, 3 \mapsto 6\} }}.


There is a [[transfinite sequence]] of cardinal numbers:
The behavior of cardinalities of [[infinite sets]] is more complex. For example, there exists a bijection between the set of all [[natural number]]s {{tmath|\mathbb{N} }} and the set of all [[rational number]]s {{tmath|\mathbb{Q} }}, and thus {{tmath|1=\vert \mathbb{N} \vert = \vert \mathbb{Q} \vert}} even though {{tmath|\mathbb{N} }} is a [[proper subset]] of {{tmath|\mathbb{Q} }}—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 number]]s {{tmath|\mathbb{R} }}  is greater than the cardinality of {{tmath|\mathbb{N} }}.
:<math>0, 1, 2, 3, \ldots, n, \ldots ; \aleph_0, \aleph_1, \aleph_2, \ldots, \aleph_{\alpha}, \ldots.\ </math>
 
This sequence starts with the [[natural number]]s including zero (finite cardinals), which are followed by the [[aleph number]]s. The aleph numbers are indexed by [[ordinal number]]s. If the [[axiom of choice]] is true, this transfinite sequence includes every cardinal number. If the axiom of choice is not true (see {{slink|Axiom of choice#Independence}}), there are infinite cardinals that are not aleph numbers.
The cardinality of {{tmath|\mathbb{N} }} is usually denoted by {{tmath|\aleph_0}} ([[aleph-null]]), since it is the smallest [[aleph number]]. The properties of other aleph numbers and of [[Transfinite number|infinite cardinal number]]s in general depend on statements [[Independence (mathematical logic)|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 (category theory)|skeleton]] of the [[category of sets]].
[[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 (category theory)|skeleton]] of the [[category of sets]].


== History ==
== 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 set]]s and sequences, with the position aspect leading to [[ordinal number]]s, and the size aspect leading to cardinal numbers.


The notion of cardinality, as now understood, was formulated by [[Georg Cantor]], the originator of [[set theory]], in 1874–1884. Cardinality can be used to compare an aspect of finite sets. For example, the sets {1,2,3} and {4,5,6} are not ''equal'', but have the ''same cardinality'', namely three. This is established by the existence of a [[bijection]] (i.e., a one-to-one correspondence) between the two sets, such as the correspondence {1→4, 2→5, 3→6}.
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.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Cardinal Number|url=https://mathworld.wolfram.com/CardinalNumber.html|access-date=2020-09-06|website=mathworld.wolfram.com|language=en}}</ref> For example, the set {{tmath|\{1,2,3\} }} has three elements, so when one replaces its members following the mapping {{tmath|\{1 \mapsto 4, 2 \mapsto 5, 3 \mapsto 6\} }}, the resulting set {{tmath|\{4,5,6\} }} still has three elements. It is reasonable to further postulate that two sets {{tmath|X}} and {{tmath|Y}} have the same size if ''and only if'' such a mapping—a [[bijection]]—exists from {{tmath|X}} to {{tmath|Y}}. This is exactly how the formal concept of [[cardinality]] is defined.


Cantor applied his concept of bijection to infinite sets<ref>{{harvnb|Dauben|1990|loc=pg. 54}}</ref> (for example the set of natural numbers '''N''' = {0, 1, 2, 3, ...}). Thus, he called all sets having a bijection with '''N''' [[Countable set|''denumerable (countably infinite) sets'']], which all share the same cardinal number. This cardinal number is called <math>\aleph_0</math>, [[Aleph number|aleph-null]]. He called the cardinal numbers of infinite sets [[transfinite cardinal numbers]].
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.


Cantor proved that any [[Bounded set|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 pair]]s of natural numbers is denumerable; this implies that the set of all [[rational number]]s is also denumerable, since every rational can be represented by a pair of integers. He later proved that the set of all real [[algebraic number]]s 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''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a<sub>n</sub>''), ''a<sub>i</sub>'' ∈ '''Z''' together with a pair of rationals (''b''<sub>0</sub>, ''b''<sub>1</sub>) such that ''z'' is the unique root of the polynomial with coefficients (''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a<sub>n</sub>'') that lies in the interval (''b''<sub>0</sub>, ''b''<sub>1</sub>).
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 {{tmath|\{1,2,3,...\} }} and {{tmath|\{2,3,4,...\} }}, and thus they have the same cardinality {{tmath|\aleph_0}}, despite the second being a [[proper subset]] of the first. Therefore the intuition that the size of a proper subset of {{tmath|X}} is always strictly less than the size of {{tmath|X}} is usually{{efn|More precisely, this statement is valid exactly for [[Dedekind-finite set]]s {{tmath|X}}.}} only valid for finite sets. Conversely, this also shows that {{tmath|1=\aleph_0 + 1 = \aleph_0}} (the cardinality of {{tmath|\{2,3,4,...\} }} plus the cardinality of {{tmath|\{1\} }} is equal to the cardinality of {{tmath|\{1,2,3,...\} }}), and thus the "plus one" operation does not always construct a new cardinal number as it does for natural numbers.


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 [[Cantor's diagonal argument|diagonal argument]]. The new cardinal number of the set of real numbers is called the [[cardinality of the continuum]] and Cantor used the symbol <math>\mathfrak{c}</math> for it.
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 number]]s is equal to {{tmath|2^{\aleph_0} }}, and thus there are strictly more real numbers than natural numbers.


Cantor also developed a large portion of the general theory of cardinal numbers; he proved that there is a smallest transfinite cardinal number (<math>\aleph_0</math>, aleph-null), and that for every cardinal number there is a next-larger cardinal
== Cardinality function ==
The cardinality function is a [[cardinal function]] that takes in a set <math>A</math> and returns its cardinal number: {{tmath|A \mapsto \vert A \vert}}. 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.<ref>{{Harvard citation no brackets|Kleene|1952|p=9}}</ref> The only fundamental requirement on a cardinality function <math>A \mapsto |A|</math> is:<ref>{{Harvard citation no brackets|Enderton|1977|p=136}}</ref>
<math display="block">A \sim B \iff |A| = |B|.</math>
The assumption that there is ''some'' function that satisfies this requirement is sometimes called the ''axiom of cardinality''<ref>{{Harvard citation no brackets|Pinter|2014|loc=Page 2 of Chapter 8}} {{br}}</ref> or ''[[Hume's principle]]''.<ref>{{Cite book |last=Potter |first=Michael |url=https://www.google.com/books/edition/Set_Theory_and_its_Philosophy/FxRoPuPbGgUC |title=Set Theory and its Philosophy: A Critical Introduction |date=2004-01-15 |publisher=Clarendon Press |isbn=978-0-19-155643-2 |language=en}}</ref> It will be shown later that such a function can be constructed without the need to define it axiomatically.


:<math>(\aleph_1, \aleph_2, \aleph_3, \ldots).</math>
An alternative approach is to define an equality relation for cardinal numbers {{tmath|1==_c}} that may be different from the equality relation for sets, and use {{tmath|1==_c}} to develop the theory of cardinality. Specifically, Moschovakis defines a (weak) '''cardinal assignment''' as an operation {{tmath|A \mapsto \vert A \vert}} that satisfies {{tmath|A \sim \vert A \vert}} (with the motivation that the cardinality of {{tmath|A}} should be represented by an "abstract" object {{tmath|\vert A \vert}} that is equinumerous to {{tmath|A}}).{{efn|Moschovakis' original definition also requires that for each set of sets {{tmath|\mathcal{E} }}, {{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 {{tmath|1==_c}} is then the same as the equinumerosity relation {{tmath|\sim}} between sets. If a cardinal assignment ''also'' satisfies {{tmath|1=A \sim B \iff \vert A \vert = \vert B \vert}}, then it is a '''strong cardinal assignment'''.{{sfn|Moschovakis|2006|p=42}}


His [[continuum hypothesis]] is the proposition that the cardinality <math>\mathfrak{c}</math> of the set of real numbers is the same as <math>\aleph_1</math>. This hypothesis is independent of the standard axioms of mathematical set theory, that is, it can neither be proved nor disproved from them. This was shown in 1963 by [[Paul Cohen (mathematician)|Paul Cohen]], complementing earlier work by [[Kurt Gödel]] in 1940.
== 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 {{tmath|X}} with (the von Neumann representation of) the least [[ordinal number]] {{tmath|\alpha}} such that there is a bijection between {{tmath|X}} and {{tmath|\alpha}}. This ordinal number {{tmath|\alpha}} is also known as the '''initial ordinal''' of the cardinal number {{tmath|\vert X \vert}}.


== Motivation ==
When {{tmath|X}} is a finite set, all possible well-orderings of {{tmath|X}} 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.
In informal use, a cardinal number is what is normally referred to as a ''[[counting number]]'', provided that 0 is included: 0, 1, 2, .... They may be identified with the [[natural numbers]] beginning with 0. The counting numbers are exactly what can be defined formally as the [[finite set|finite]] cardinal numbers.  Infinite cardinals only occur in higher-level mathematics and [[logic]].
 
More formally, a non-zero 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.  For finite sets and sequences it is easy to see that these two notions coincide, since for every number describing a position in a sequence we can construct a set that has exactly the right size. For example, 3 describes the position of 'c' in the sequence <'a','b','c','d',...>, and we can construct the set {a,b,c}, which has 3 elements.
 
However, when dealing with [[infinite set]]s, it is essential to distinguish between the two, since the two notions are in fact different for infinite sets. Considering the position aspect leads to [[ordinal numbers]], while the size aspect is generalized by the cardinal numbers described here.
 
The intuition behind the formal definition of cardinal is the construction of a notion of the relative size or "bigness" of a set, without reference to the kind of members which it has.  For finite sets this is easy; one simply counts the number of elements a set has.  In order to compare the sizes of larger sets, it is necessary to appeal to more refined notions.


A set ''Y'' is at least as big as a set ''X'' if there is an [[injective function|injective]] [[map (mathematics)|mapping]] from the elements of ''X'' to the elements of ''Y''. An injective mapping identifies each element of the set ''X'' with a unique element of the set ''Y''. This is most easily understood by an example; suppose we have the sets ''X'' = {1,2,3} and ''Y'' = {a,b,c,d}, then using this notion of size, we would observe that there is a mapping:
On the other hand, many different infinite ordinal numbers can have the same cardinality. For example, the first infinite ordinal {{tmath|\omega}} has the same cardinality as {{tmath|\omega+1}}, {{tmath|\omega^2}}, {{tmath|\omega^\omega}}, [[Epsilon numbers (mathematics)|<math>\epsilon_{0}</math>]]..., all of which are [[Countable set|countable]] ordinals. Among these, only {{tmath|\omega}} itself is an initial ordinal.
: 1 → a
: 2 → b
: 3 → c
which is injective, and hence conclude that ''Y'' has cardinality greater than or equal to ''X''. The element d has no element mapping to it, but this is permitted as we only require an injective mapping, and not necessarily a [[bijective]] mapping. The advantage of this notion is that it can be extended to infinite sets.


We can then extend this to an equality-style relation. Two [[Set (mathematics)|sets]] ''X'' and ''Y'' are said to have the same ''cardinality'' if there exists a [[bijection]] between ''X'' and ''Y''. By the [[Cantor–Bernstein–Schroeder theorem|Schroeder–Bernstein theorem]], this is equivalent to there being ''both'' an injective mapping from ''X'' to ''Y'', ''and'' an injective mapping from ''Y'' to ''X''. We then write |''X''| = |''Y''|. The cardinal number of ''X'' itself is often defined as the least ordinal ''a'' with |''a''| = |''X''|.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Cardinal Number|url=https://mathworld.wolfram.com/CardinalNumber.html|access-date=2020-09-06|website=mathworld.wolfram.com|language=en}}</ref> This is called the [[von Neumann cardinal assignment]]; for this definition to make sense, it must be proved that every set has the same cardinality as ''some'' ordinal; this statement is the [[well-ordering principle]]. It is however possible to discuss the relative cardinality of sets without explicitly assigning names to objects.
The <math>\alpha</math>-th infinite initial ordinal is written <math>\omega_\alpha</math>. Its cardinality is written <math>\aleph_{\alpha}</math> (the <math>\alpha</math>-th [[aleph number]]). For example, {{tmath|\omega}} is also written as {{tmath|\omega_0}}, and its cardinality (the cardinality of any countable set) as {{tmath|\aleph_0}}. The von Neumann cardinal assignment identifies <math>\omega_{\alpha}</math> with <math>\aleph_{\alpha}</math>, but the notation <math>\aleph_{\alpha}</math> is used for writing cardinals, and <math>\omega_{\alpha}</math> for writing ordinals. This is important because [[cardinal number#Cardinal arithmetic|arithmetic on cardinals]] is different from [[ordinal arithmetic|arithmetic on ordinals]]. For example, <math>2^\omega=\omega<\omega^2</math> in ordinal arithmetic while <math>2^{\aleph_0}>\aleph_0=\aleph_0^2</math> in cardinal arithmetic, even though under the von Neumann cardinal assignment {{tmath|\aleph_0}} and {{tmath|\omega}} are represented by the same set.
 
The classic example used is that of the infinite hotel paradox, also called [[Hilbert's paradox of the Grand Hotel]].  Supposing there is an innkeeper at a hotel with an infinite number of rooms. The hotel is full, and then a new guest arrives.  It is possible to fit the extra guest in by asking the guest who was in room 1 to move to room 2, the guest in room 2 to move to room 3, and so on, leaving room 1 vacant.  We can explicitly write a segment of this mapping:
: 1 → 2
: 2 → 3
: 3 → 4
: ...
: ''n'' → ''n'' + 1
: ...
With this assignment, we can see that the set {1,2,3,...} has the same cardinality as the set {2,3,4,...}, since a bijection between the first and the second has been shown.  This motivates the definition of an infinite set being any set that has a proper subset of the same cardinality (i.e., a [[Dedekind-infinite set]]); in this case {2,3,4,...} is a proper subset of {1,2,3,...}.


When considering these large objects, one might also want to see if the notion of counting order coincides with that of cardinal defined above for these infinite sets.  It happens that it does not; by considering the above example we can see that if some object "one greater than infinity" exists, then it must have the same cardinality as the infinite set we started out with. It is possible to use a different formal notion for number, called [[Ordinal number|ordinals]], based on the ideas of counting and considering each number in turn, and we discover that the notions of cardinality and ordinality are divergent once we move out of the finite numbers.
Also, <math>\omega_{1}</math> is the smallest [[Uncountable set|uncountable]] ordinal (to see that it exists, consider the set of [[equivalence class]]es of well-orderings of the natural numbers; each such well-ordering defines a countable ordinal, and <math>\omega_{1}</math> is the order type of that set), <math>\omega_{2}</math> is the smallest ordinal whose cardinality is greater than <math>\aleph_{1}</math>, and so on, and <math>\omega_{\omega}</math> is the limit of <math>\omega_{n}</math> for natural numbers <math>n</math> (any limit of cardinals is a cardinal, so this limit is indeed the first cardinal after all the <math>\omega_{n}</math>).


It can be proved that the cardinality of the [[real number]]s is greater than that of the natural numbers just described. This can be visualized using [[Cantor's diagonal argument]]; classic questions of cardinality (for instance the [[continuum hypothesis]]) are concerned with discovering whether there is some cardinal between some pair of other infinite cardinals. In more recent times, mathematicians have been describing the properties of larger and larger cardinals.
Infinite initial ordinals are [[limit ordinal]]s. Using ordinal arithmetic, <math>\alpha<\omega_{\beta}</math> implies <math>\alpha+\omega_{\beta}=\omega_{\beta}</math>, and 1 ≤ ''α'' < ω<sub>''β''</sub> implies ''α''·ω<sub>''β''</sub> = ω<sub>''β''</sub>, and 2 ≤ ''α'' < ω<sub>''β''</sub> implies ''α''<sup>ω<sub>''β''</sub></sup> = ω<sub>''β''</sub>. Using the [[Veblen function|Veblen hierarchy]], ''β'' ≠ 0 and ''α'' < ω<sub>''β''</sub> imply <math>\varphi_{\alpha}(\omega_{\beta}) = \omega_{\beta} \,</math> and &Gamma;<sub>ω<sub>''β''</sub></sub> = ω<sub>''β''</sub>. Indeed, one can go far beyond this. So as an ordinal, an infinite initial ordinal is an extremely strong kind of limit.


Since cardinality is such a common concept in mathematics, a variety of names are in use. Sameness of cardinality 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''.
=== Scott cardinals ===
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 [''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 (set theory)|rank]], then it will work (this is a trick due to [[Dana Scott]]:<ref>{{cite journal|last1=Deiser|first1=Oliver|title=On the Development of the Notion of a Cardinal Number|journal=History and Philosophy of Logic|doi=10.1080/01445340903545904 |volume=31|issue=2|pages=123–143|date=May 2010|s2cid=171037224}}</ref> it works because the collection of objects with any given rank is a set).


== Formal definition ==
Some sources use a mixed definition between von Neumann cardinals and Scott cardinals. For example, Lévy<ref>{{Cite book |last=Lévy |first=Azriel |author-link=Azriel Lévy |url=https://archive.org/details/basicsettheory00levy_0/ |title=Basic Set Theory |publisher=[[Springer-Verlag]] |year=1979 |isbn=3-540-08417-7 |series=Perspectives in Mathematical Logic |location=Berlin |lccn=78-1917}}</ref> defines {{tmath|\vert X \vert}} as the von Neumann cardinal when {{tmath|X}} is well-orderable, and as the Scott cardinal otherwise.{{efn|Obviously each cardinal number uses only one of these two representations, since two equinumerous sets are either both well-orderable or both not. There is also no possibility of confusion because the Scott cardinal {{tmath|\kappa}} is always a non-empty set with all elements having the cardinality {{tmath|\kappa}}, and all non-zero ordinals contain {{tmath|\emptyset}} as an element, so the only Scott cardinal that happens to also be an ordinal is {{tmath|\{\emptyset\} }}, which represents 0 as a Scott cardinal and 1 as an ordinal, but since the empty set is well-orderable, under Lévy's convention 0 should use the von Neumann representation {{tmath|\emptyset}} anyway.}} 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.
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 [''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 (set theory)|rank]], then it will work (this is a trick due to [[Dana Scott]]:<ref>{{cite journal|last1=Deiser|first1=Oliver|title=On the Development of the Notion of a Cardinal Number|journal=History and Philosophy of Logic|doi=10.1080/01445340903545904 |volume=31|issue=2|pages=123–143|date=May 2010|s2cid=171037224}}</ref> 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, <math>2^\omega=\omega<\omega^2</math> in ordinal arithmetic while <math>2^{\aleph_0}>\aleph_0=\aleph_0^2</math> in cardinal arithmetic, although the von Neumann assignment puts <math>\aleph_0=\omega</math>. On the other hand, Scott's trick implies that the cardinal number 0 is <math>\{\emptyset\}</math>, 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.
== 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''|.<ref name="Enderton">Enderton, Herbert. "Elements of Set Theory", Academic Press Inc., 1977. {{ISBN|0-12-238440-7}}</ref><ref>{{citation | author=Friedrich M. Hartogs | author-link=Friedrich M. Hartogs | editor=Felix Klein | editor-link=Felix Klein | editor2=Walther von Dyck | editor2-link=Walther von Dyck | editor3=David Hilbert | editor3-link=David Hilbert | editor4=Otto Blumenthal | editor4-link=Otto Blumenthal | title=Über das Problem der Wohlordnung | journal=[[Math. Ann.]] | volume=Bd.&nbsp;76 | number=4 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1915 | pages=438–443 | issn=0025-5831 | url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0076&DMDID=DMDLOG_0037&L=1 | doi=10.1007/bf01458215 | s2cid=121598654 | access-date=2014-02-02 | archive-url=https://web.archive.org/web/20160416205255/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0076&DMDID=DMDLOG_0037&L=1 | archive-date=2016-04-16 | url-status=live }}</ref>


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''|.<ref name="Enderton">Enderton, Herbert. "Elements of Set Theory", Academic Press Inc., 1977. {{ISBN|0-12-238440-7}}</ref><ref>{{citation | author=Friedrich M. Hartogs | author-link=Friedrich M. Hartogs | editor=Felix Klein | editor-link=Felix Klein | editor2=Walther von Dyck | editor2-link=Walther von Dyck | editor3=David Hilbert | editor3-link=David Hilbert | editor4=Otto Blumenthal | editor4-link=Otto Blumenthal | title=Über das Problem der Wohlordnung | journal=Math. Ann. | volume=Bd.&nbsp;76 | number=4 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1915 | pages=438–443 | issn=0025-5831 | url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0076&DMDID=DMDLOG_0037&L=1 | doi=10.1007/bf01458215 | s2cid=121598654 | access-date=2014-02-02 | archive-url=https://web.archive.org/web/20160416205255/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0076&DMDID=DMDLOG_0037&L=1 | archive-date=2016-04-16 | url-status=live }}</ref>
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 set|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 set|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.


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 set|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 set|infinite]].
== Aleph numbers ==
{{main|Aleph number}}
The aleph numbers are the cardinalities of [[well-order]]able infinite sets. They are denoted with the [[Hebrew alphabet|Hebrew letter]] <math>\aleph</math> ([[Aleph (Hebrew)|aleph]]) marked with a subscript indicating their rank among aleph numbers. Since aleph numbers can be identified with their [[initial ordinal]]s, they form a [[transfinite sequence]]:
<math display="block">\aleph_0 = |\mathbb{N}|,\; \aleph_1,\; \aleph_2,\; \ldots,\; \aleph_{\alpha},\; \ldots.</math>
For every ordinal {{tmath|\alpha}}, there exists an aleph number {{tmath|\aleph_{\alpha} }}. 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.


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 <math>\aleph_0</math> ([[aleph null]] or aleph-0, where aleph is the first letter in the [[Hebrew alphabet]], represented <math>\aleph</math>) of the set of natural numbers is the smallest infinite cardinal (i.e., any infinite set has a subset of cardinality <math>\aleph_0</math>). The next larger cardinal is denoted by <math>\aleph_1</math>, and so on. For every ordinal α, there is a cardinal number <math>\aleph_{\alpha},</math> and this list exhausts all infinite cardinal numbers.
If the axiom of choice is not true (see {{slink|Axiom of choice#Independence}}), then there exist sets that are not well-orderable, and thus infinite cardinals that are not aleph numbers. Such a cardinal must be [[Comparability|incomparable]] to some aleph number by [[Hartogs number|Hartogs's theorem]], so in this case it is impossible to write all cardinal numbers in a [[totally ordered]] sequence.


== Cardinal arithmetic ==
== Cardinal arithmetic ==
Line 82: Line 82:
{{Further|Successor cardinal}}
{{Further|Successor cardinal}}


If the axiom of choice holds, then every cardinal κ has a successor, denoted κ<sup>+</sup>, where κ<sup>+</sup> > κ and there are no cardinals between κ and its successor.  (Without the axiom of choice, using [[Hartogs number|Hartogs' theorem]], it can be shown that for any cardinal number κ, there is a minimal cardinal κ<sup>+</sup> such that <!-- κ<sup>+</sup> ࣞ κ.<ref group=notes>The symbol is the [[Unicode]] symbol for not less than or equal to.</ref>--><math>\kappa^+\nleq\kappa. </math>)  For finite cardinals, the successor is simply κ + 1.  For infinite cardinals, the successor cardinal differs from the [[successor ordinal]].
If the axiom of choice holds, then every cardinal ''κ'' has a successor, denoted ''κ''<sup>+</sup>, where ''κ''<sup>+</sup> > ''κ'' and there are no cardinals between ''κ'' and its successor.  (Without the axiom of choice, using [[Hartogs number|Hartogs' theorem]], it can be shown that for any cardinal number ''κ'', there is a minimal cardinal ''κ''<sup>+</sup> such that <!-- ''κ''<sup>+</sup> ࣞ ''κ''.<ref group=notes>The symbol is the [[Unicode]] symbol for not less than or equal to.</ref>--><math>\kappa^+\nleq\kappa. </math>)  For finite cardinals, the successor is simply ''κ'' + 1.  For infinite cardinals, the successor cardinal differs from the [[successor ordinal]].


=== Cardinal addition ===
=== Cardinal addition ===
Line 136: Line 136:
where ''X<sup>Y</sup>'' is the set of all [[function (mathematics)|functions]] from ''Y'' to ''X''.<ref name=":0" /> It is easy to check that the right-hand side depends only on <math>{|X|}</math> and <math>{|Y|}</math>.
where ''X<sup>Y</sup>'' is the set of all [[function (mathematics)|functions]] from ''Y'' to ''X''.<ref name=":0" /> It is easy to check that the right-hand side depends only on <math>{|X|}</math> and <math>{|Y|}</math>.


:κ<sup>0</sup> = 1  (in particular 0<sup>0</sup> = 1), see [[empty function]].
:''κ''<sup>0</sup> = 1  (in particular 0<sup>0</sup> = 1), see [[empty function]].
:If ''μ'' ≥ 1, then 0<sup>''μ''</sup> = 0.
:If ''μ'' ≥ 1, then 0<sup>''μ''</sup> = 0.
:1<sup>''μ''</sup> = 1.
:1<sup>''μ''</sup> = 1.
Line 155: Line 155:


If 2 ≤ ''κ'' and 1 ≤ ''μ'' and at least one of them is infinite, then:
If 2 ≤ ''κ'' and 1 ≤ ''μ'' and at least one of them is infinite, then:
:Max (''κ'', 2<sup>''μ''</sup>) ≤ ''κ''<sup>''μ''</sup> ≤ Max (2<sup>''κ''</sup>, 2<sup>''μ''</sup>).
:max (''κ'', 2<sup>''μ''</sup>) ≤ ''κ''<sup>''μ''</sup> ≤ max (2<sup>''κ''</sup>, 2<sup>''μ''</sup>).


Using [[König's theorem (set theory)|König's theorem]], one can prove ''κ'' < ''κ''<sup>cf(''κ'')</sup> and ''κ'' < cf(2<sup>''κ''</sup>) for any infinite cardinal ''κ'', where cf(''κ'') is the [[cofinality]] of ''κ''.
Using [[Kőnig's theorem (set theory)|Kőnig's theorem]], one can prove ''κ'' < ''κ''<sup>cf(''κ'')</sup> and ''κ'' < cf(2<sup>''κ''</sup>) for any infinite cardinal ''κ'', where cf(''κ'') is the [[cofinality]] of ''κ''.


==== Roots ====
==== Roots ====
Line 173: Line 173:


Indeed, [[Easton's theorem]] shows that, for [[regular cardinal]]s <math>\kappa</math>, the only restrictions ZFC places on the cardinality of <math>2^\kappa</math> are that <math> \kappa < \operatorname{cf}(2^\kappa) </math>, and that the exponential function is non-decreasing.
Indeed, [[Easton's theorem]] shows that, for [[regular cardinal]]s <math>\kappa</math>, the only restrictions ZFC places on the cardinality of <math>2^\kappa</math> are that <math> \kappa < \operatorname{cf}(2^\kappa) </math>, and that the exponential function is non-decreasing.
== History ==
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<ref>{{harvnb|Dauben|1990|loc=pg. 54}}</ref> (for example the set of natural numbers '''N''' = {0, 1, 2, 3, ...}). Thus, he called all sets having a bijection with '''N''' [[Countable set|''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 [[Bounded set|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 pair]]s of natural numbers is denumerable; this implies that the set of all [[rational number]]s is also denumerable, since every rational can be represented by a pair of integers. He later proved that the set of all real [[algebraic number]]s 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''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a<sub>n</sub>''), ''a<sub>i</sub>'' ∈ '''Z''' together with a pair of rationals (''b''<sub>0</sub>, ''b''<sub>1</sub>) such that ''z'' is the unique root (if it exists) of the polynomial with coefficients (''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a<sub>n</sub>'') that lies in the interval (''b''<sub>0</sub>, ''b''<sub>1</sub>).
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 [[Cantor's diagonal argument|diagonal argument]]. The new cardinal number of the set of real numbers is called the [[cardinality of the continuum]] and Cantor used the symbol <math>\mathfrak{c}</math> 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 (<math>\aleph_0</math>, aleph-null), and that for every cardinal number there is a next-larger cardinal
:<math>(\aleph_1, \aleph_2, \aleph_3, \ldots).</math>
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 (mathematician)|Paul Cohen]] showed that it cannot be proved from ZFC either, establishing its [[independence (mathematical logic)|independence]].


== See also ==
== See also ==
Line 189: Line 203:
* [[Regular cardinal]]
* [[Regular cardinal]]
{{div col end}}
{{div col end}}
== Footnotes ==
{{notelist}}


== References ==
== References ==
'''Notes'''
'''Notes'''
{{Reflist}}
{{Reflist}}
'''Bibliography'''
'''Bibliography'''
*{{citation|last=Dauben|first=Joseph Warren|title=Georg Cantor: His Mathematics and Philosophy of the Infinite|publisher=Princeton University Press|place=Princeton|year=1990|isbn=0691-02447-2|url-access=registration|url=https://archive.org/details/georgcantorhisma0000daub}}
* {{Cite book |last=Bourbaki |first=Nicholas |author-link=Nicolas Bourbaki |url=https://archive.org/details/theoryofsets0000bour/ |title=Theory of Sets |date=1968 |publisher=[[Éditions Hermann]] |series=[[Éléments de mathématique]] |location=Paris |lccn=68-25177}}
*[[Hans Hahn (mathematician)|Hahn, Hans]], ''Infinity'', Part IX, Chapter 2, Volume 3 of ''The World of Mathematics''. New York: Simon and Schuster, 1956.
* {{citation |last=Dauben |first=Joseph Warren |author-link=Joseph Dauben |title=Georg Cantor: His Mathematics and Philosophy of the Infinite |year=1990 |url=https://archive.org/details/georgcantorhisma0000daub |place=Princeton |publisher=Princeton University Press |isbn=0691-02447-2 |url-access=registration}}
*[[Paul Halmos|Halmos, Paul]], ''[[Naive Set Theory (book)|Naive set theory]]''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. {{isbn|0-387-90092-6}} (Springer-Verlag edition).
* {{Cite book |last=Enderton |first=Herbert |author-link=Herbert Enderton |url=https://archive.org/details/elementsofsetthe0000ende/ |title=Elements of Set Theory |publisher=[[Academic Press]] |year=1977 |isbn=0-12-238440-7 |location=New York |lccn=76-27438}}
*{{Cite book|last=Schindler|first=Ralf-Dieter|doi=10.1007/978-3-319-06725-4|title=Set theory : exploring independence and truth|series=Universitext |date=2014|isbn=978-3-319-06725-4|location=Cham|publisher=[[Springer-Verlag]]}}
* [[Hans Hahn (mathematician)|Hahn, Hans]], ''Infinity'', Part IX, Chapter 2, Volume 3 of ''The World of Mathematics''. New York: Simon and Schuster, 1956.
* {{Cite book |last=Halmos |first=Paul R. |author-link=Paul Halmos |url=https://link.springer.com/book/10.1007/978-1-4757-1645-0 |title=Naive Set Theory |publisher=[[Springer Science+Business Media]] |year=1998 |isbn=978-0-387-90092-6 |series=[[Undergraduate Texts in Mathematics]] |location=New York |doi=10.1007/978-1-4757-1645-0 |issn=0172-6056 |orig-year=1974 |archive-url=https://web.archive.org/web/20230112000000/https://link.springer.com/book/10.1007/978-1-4757-1645-0 |archive-date=2023-01-12}} [https://archive.org/details/naive-set-theory-pdfdrive/ Alt URL]
* {{Cite book |last1=Hrbáček |first1=Karel |author-link1=Karel Hrbáček |url=https://www.routledge.com/p/book/9781315274096 |title=Introduction to Set Theory |last2=Jech |first2=Thomas |author-link2=Thomas Jech |date=2017 |publisher=[[CRC Press]] |isbn=978-0-82477915-3 |edition=3rd, Revised and Expanded |location=New York |doi=10.1201/9781315274096 |lccn=99-15458 |orig-year=1999}}
* {{Cite book |last=Kleene |first=Stephen Cole |author-link=Stephen Cole Kleene |url=http://archive.org/details/introductiontome0000step |title=Introduction To Metamathematics |date=1952 |publisher=[[D. Van Nostrand Company]] |location=New York}} <!-- ISBN 9780598446619 was associated with this title, but is not found in searches and is incompatible with the 1952 publishing date -->
* {{Cite book |last=Kuratowski |first=Kazimierz |author-link=Kazimierz Kuratowski |url=https://archive.org/details/settheory0000kura/ |title=Set Theory |publisher=[[North Holland Publishing]] |year=1968 |location=Amsterdam |lccn=67-21972}}
* {{Cite book |last=Moschovakis |first=Yiannis N. |author-link=Yiannis Moschovakis |title=Notes on Set Theory, 2nd Edition |date=2006 |publisher=Springer |publication-place=New York |isbn=978-0387287232 |orig-year=1994}}
* {{Cite book |last=Pinter |first=Charles C. |url=https://store.doverpublications.com/products/9780486795492 |title=A Book of Set Theory |date=2014 |publisher=[[Dover Publications]] |isbn=978-0-486-79549-2 |series=Dover Books on Mathematics |location=Mineola |issn=2693-051X |lccn=2013024319 |orig-year=1971 |archive-url=https://web.archive.org/web/20240804000000/https://store.doverpublications.com/products/9780486795492 |archive-date=2024-08-04}} [[iarchive:charles-c.-pinter-2014-a-book-of-set-theory/|Alt URL]]
* {{Cite book |last=Schindler |first=Ralf-Dieter |title=Set theory : exploring independence and truth |date=2014 |publisher=[[Springer-Verlag]] |isbn=978-3-319-06725-4 |series=Universitext |location=Cham |doi=10.1007/978-3-319-06725-4}}
* {{Cite book |last=Suppes |first=Patrick |author-link=Patrick Suppes |url=https://store.doverpublications.com/products/9780486616308 |title=Axiomatic Set Theory |date=1972 |publisher=[[Dover Publications]] |isbn=0-486-61630-4 |series=Dover Books on Mathematics |location=New York |issn=2693-051X |lccn=72-86226 |orig-year=1960 |archive-url=https://web.archive.org/web/20140806000000/https://store.doverpublications.com/products/9780486616308 |archive-date=2014-08-06}} [[iarchive:axiomaticsettheo00supp_0/|Alt URL]]
* {{Cite book |last=Tao |first=Terence |editor-first1=<!-- Deny Citation Bot--> |editor-last1=<!-- Deny Citation Bot--> |author-link=Terence Tao |url=https://link.springer.com/book/10.1007/978-981-19-7261-4 |title=Analysis I |publisher=[[Springer Science+Business Media]] |isbn=978-981-19-7261-4 |edition=4th |series=Texts and Readings in Mathematics |location=Singapore |publication-date=2022 |doi=10.1007/978-3-662-00274-2 |issn=2366-8717}}


==External links==
==External links==

Latest revision as of 18:25, 21 April 2026

This article is about the mathematical concept. For number words indicating quantity ("three" apples, "four" birds, etc.), see Cardinal numeral.
See also: Cardinality
File:Bijection.svg
A bijective function, 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.
File:Aleph0.svg
Aleph-null, 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 Template:Tmath is generally denoted by Template:Tmath, with a vertical bar on each side,[1] though it may also be denoted by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{card}(A),} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \#A.} [8]

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 Template:Tmath and Template:Tmath both have the same cardinality 3, as evidenced by the bijection Template:Tmath.

The behavior of cardinalities of infinite sets is more complex. For example, there exists a bijection between the set of all natural numbers Template:Tmath and the set of all rational numbers Template:Tmath, and thus Template:Tmath even though Template:Tmath is a proper subset of Template:Tmath—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 Template:Tmath is greater than the cardinality of Template:Tmath.

The cardinality of Template:Tmath is usually denoted by Template:Tmath (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.[9] For example, the set Template:Tmath has three elements, so when one replaces its members following the mapping Template:Tmath, the resulting set Template:Tmath still has three elements. It is reasonable to further postulate that two sets Template:Tmath and Template:Tmath have the same size if and only if such a mapping—a bijection—exists from Template:Tmath to Template:Tmath. 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 Template:Tmath and Template:Tmath, and thus they have the same cardinality Template:Tmath, despite the second being a proper subset of the first. Therefore the intuition that the size of a proper subset of Template:Tmath is always strictly less than the size of Template:Tmath is usually[lower-alpha 1] only valid for finite sets. Conversely, this also shows that Template:Tmath (the cardinality of Template:Tmath plus the cardinality of Template:Tmath is equal to the cardinality of Template:Tmath), 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 Template:Tmath, 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and returns its cardinal number: Template:Tmath. 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.[10] The only fundamental requirement on a cardinality function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \mapsto |A|} is:[11] Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \sim B \iff |A| = |B|.} The assumption that there is some function that satisfies this requirement is sometimes called the axiom of cardinality[12] or Hume's principle.[13] 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 Template:Tmath that may be different from the equality relation for sets, and use Template:Tmath to develop the theory of cardinality. Specifically, Moschovakis defines a (weak) cardinal assignment as an operation Template:Tmath that satisfies Template:Tmath (with the motivation that the cardinality of Template:Tmath should be represented by an "abstract" object Template:Tmath that is equinumerous to Template:Tmath).[lower-alpha 2] The relation Template:Tmath is then the same as the equinumerosity relation Template:Tmath between sets. If a cardinal assignment also satisfies Template:Tmath, then it is a strong cardinal assignment.[14]

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 Template:Tmath with (the von Neumann representation of) the least ordinal number Template:Tmath such that there is a bijection between Template:Tmath and Template:Tmath. This ordinal number Template:Tmath is also known as the initial ordinal of the cardinal number Template:Tmath.

When Template:Tmath is a finite set, all possible well-orderings of Template:Tmath 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 Template:Tmath has the same cardinality as Template:Tmath, Template:Tmath, Template:Tmath, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon_{0}} ..., all of which are countable ordinals. Among these, only Template:Tmath itself is an initial ordinal.

The Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} -th infinite initial ordinal is written Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_\alpha} . Its cardinality is written Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{\alpha}} (the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} -th aleph number). For example, Template:Tmath is also written as Template:Tmath, and its cardinality (the cardinality of any countable set) as Template:Tmath. The von Neumann cardinal assignment identifies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{\alpha}} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{\alpha}} , but the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{\alpha}} is used for writing cardinals, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{\alpha}} for writing ordinals. This is important because arithmetic on cardinals is different from arithmetic on ordinals. For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^\omega=\omega<\omega^2} in ordinal arithmetic while Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0}>\aleph_0=\aleph_0^2} in cardinal arithmetic, even though under the von Neumann cardinal assignment Template:Tmath and Template:Tmath are represented by the same set.

Also, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{1}} is the order type of that set), Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{2}} is the smallest ordinal whose cardinality is greater than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{1}} , and so on, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{\omega}} is the limit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{n}} for natural numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} (any limit of cardinals is a cardinal, so this limit is indeed the first cardinal after all the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega_{n}} ).

Infinite initial ordinals are limit ordinals. Using ordinal arithmetic, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha<\omega_{\beta}} implies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha+\omega_{\beta}=\omega_{\beta}} , and 1 ≤ α < ωβ implies α·ωβ = ωβ, and 2 ≤ α < ωβ implies αωβ = ωβ. Using the Veblen hierarchy, β ≠ 0 and α < ωβ imply Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

Scott cardinals

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 [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:[15] 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[16] defines Template:Tmath as the von Neumann cardinal when Template:Tmath is well-orderable, and as the Scott cardinal otherwise.[lower-alpha 3] 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|.[17][18]

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

Main article: Aleph number

The aleph numbers are the cardinalities of well-orderable infinite sets. They are denoted with the Hebrew letter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph} (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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0 = |\mathbb{N}|,\; \aleph_1,\; \aleph_2,\; \ldots,\; \aleph_{\alpha},\; \ldots.} For every ordinal Template:Tmath, there exists an aleph number Template:Tmath. 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 Axiom of choice § Independence), 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

Further information: Successor cardinal

If the axiom of choice holds, then every cardinal κ has a successor, denoted κ+, where κ+ > κ and there are no cardinals between κ and its successor. (Without the axiom of choice, using Hartogs' theorem, it can be shown that for any cardinal number κ, there is a minimal cardinal κ+ such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa^+\nleq\kappa. } ) For finite cardinals, the successor is simply κ + 1. For infinite cardinals, the successor cardinal differs from the successor ordinal.

Cardinal addition

If X and Y are disjoint, addition is given by the union of X and Y. If the two sets are not already disjoint, then they can be replaced by disjoint sets of the same cardinality (e.g., replace X by X×{0} and Y by Y×{1}).

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X| + |Y| = | X \cup Y|.} [19]

Zero is an additive identity κ + 0 = 0 + κ = κ.

Addition is associative (κ + μ) + ν = κ + (μ + ν).

Addition is commutative κ + μ = μ + κ.

Addition is non-decreasing in both arguments:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa + \mu = \max\{\kappa, \mu\}\,.}

Subtraction

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 μ < σ.

Cardinal multiplication

The product of cardinals comes from the Cartesian product.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X|\cdot|Y| = |X \times Y|} [19]

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa\cdot\mu = \max\{\kappa, \mu\}.}

Thus the product of two infinite cardinal numbers is equal to their sum.

Division

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 μ < π.

Cardinal exponentiation

Exponentiation is given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X|^{|Y|} = \left|X^Y\right|,}

where XY is the set of all functions from Y to X.[19] It is easy to check that the right-hand side depends only on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {|X|}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {|Y|}} .

κ0 = 1 (in particular 00 = 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 κ < cf(2κ) for any infinite cardinal κ, where cf(κ) is the cofinality of κ.

Roots

Assuming the axiom of choice and, given an infinite cardinal κ and a finite cardinal μ greater than 0, the cardinal ν satisfying Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu^\mu = \kappa} will be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} .

Logarithms

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.[20][21][22]

The continuum hypothesis

The continuum hypothesis (CH) states that there are no cardinals strictly between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0}.} The latter cardinal number is also often denoted by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{c}} ; it is the cardinality of the continuum (the set of real numbers). In this case Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0} = \aleph_1.}

Similarly, the generalized continuum hypothesis (GCH) states that for every infinite cardinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} , there are no cardinals strictly between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} , the only restrictions ZFC places on the cardinality of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^\kappa} are that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa < \operatorname{cf}(2^\kappa) } , and that the exponential function is non-decreasing.

History

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[23] (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 (a0, a1, ..., an), ai ∈ Z together with a pair of rationals (b0, b1) such that z is the unique root (if it exists) of the polynomial with coefficients (a0, a1, ..., an) that lies in the interval (b0, b1).

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0} , aleph-null), and that for every cardinal number there is a next-larger cardinal

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\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.

See also

Footnotes

  1. ↑ More precisely, this statement is valid exactly for Dedekind-finite sets Template:Tmath.
  2. ↑ Moschovakis' original definition also requires that for each set of sets Template:Tmath, Template:Tmath is a set, but this is satisfied for free when the axiom schema of replacement is assumed.
  3. ↑ Obviously each cardinal number uses only one of these two representations, since two equinumerous sets are either both well-orderable or both not. There is also no possibility of confusion because the Scott cardinal Template:Tmath is always a non-empty set with all elements having the cardinality Template:Tmath, and all non-zero ordinals contain Template:Tmath as an element, so the only Scott cardinal that happens to also be an ordinal is Template:Tmath, which represents 0 as a Scott cardinal and 1 as an ordinal, but since the empty set is well-orderable, under Lévy's convention 0 should use the von Neumann representation Template:Tmath anyway.

References

Notes

  1. ↑ Hrbáček & Jech 2017, p. 65
  2. ↑ Kuratowski 1968, p. 174.
  3. ↑ Suppes 1972, p. 109.
  4. ↑ Bourbaki 1968, p. 158.
  5. ↑ Enderton 1977, p. 136.
  6. ↑ Halmos 1998, p. 53.
  7. ↑ Tao 2022, p. 60.
  8. ↑ Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} [2][3]
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{card}(A)} [4][5]

    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \#A} [6][7]

  9. ↑ Weisstein, Eric W. "Cardinal Number". mathworld.wolfram.com. Retrieved 2020-09-06.
  10. ↑ Kleene 1952, p. 9
  11. ↑ Enderton 1977, p. 136
  12. ↑ Pinter 2014, Page 2 of Chapter 8
  13. ↑ Potter, Michael (2004-01-15). Set Theory and its Philosophy: A Critical Introduction. Clarendon Press. ISBN 978-0-19-155643-2.
  14. ↑ Moschovakis 2006, p. 42.
  15. ↑ Deiser, Oliver (May 2010). "On the Development of the Notion of a Cardinal Number". History and Philosophy of Logic. 31 (2): 123–143. doi:10.1080/01445340903545904. S2CID 171037224.
  16. ↑ Lévy, Azriel (1979). Basic Set Theory. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-08417-7. LCCN 78-1917.
  17. ↑ Enderton, Herbert. "Elements of Set Theory", Academic Press Inc., 1977. ISBN 0-12-238440-7
  18. ↑ Friedrich M. Hartogs (1915), Felix Klein; Walther von Dyck; David Hilbert; Otto Blumenthal (eds.), "Über das Problem der Wohlordnung", Math. Ann., Leipzig: B. G. Teubner, Bd. 76 (4): 438–443, doi:10.1007/bf01458215, ISSN 0025-5831, S2CID 121598654, archived from the original on 2016-04-16, retrieved 2014-02-02
  19. ↑ 19.0 19.1 19.2 Schindler 2014, pg. 34
  20. ↑ Robert A. McCoy and Ibula Ntantu, Topological Properties of Spaces of Continuous Functions, Lecture Notes in Mathematics 1315, Springer-Verlag.
  21. ↑ Eduard Čech, Topological Spaces, revised by Zdenek Frolík and Miroslav Katetov, John Wiley & Sons, 1966.
  22. ↑ D. A. Vladimirov, Boolean Algebras in Analysis, Mathematics and Its Applications, Kluwer Academic Publishers.
  23. ↑ Dauben 1990, pg. 54

Bibliography

Template:Number systems Template:Mathematical logic Template:Set theory

Retrieved from "https://wiki.tachyony.co.uk/w/index.php?title=Cardinal_number&oldid=56432"