Cardinality

In mathematics, cardinality is an inherent property of sets, roughly meaning the number of individual objects they contain, which may be infinite.

Uses your system voice; voice and rate in settings.

≈ 19 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.

In mathematics, cardinality is an inherent property of sets, roughly meaning the number of individual objects they contain, which may be infinite. The concept is understood through one-to-one correspondences between sets. That is, if their objects can be paired such that each object has a pair, and no object is paired more than once.

Two sets are said to be equinumerous or have the same cardinality if there exists a one-to-one correspondence between them. Otherwise, under the axiom of choice, one of the two sets must be equinumerous with a strict subset of the other and is said to be strictly smaller than it; the other set is strictly larger.

Using this concept, it is possible to show there are different sizes of infinity. A set is countably infinite if it can be placed in one-to-one correspondence with the set of natural numbers . For example, the set of even numbers and the set of rational numbers are countable.

Uncountable sets are those strictly larger than the set of natural numbers. The set of all real numbers and the powerset of the set of natural numbers are proven to be uncountable by so-called diagonal arguments. Cantor's theorem generalizes these arguments to show there is an infinite hierarchy of infinities.

For finite sets, cardinality recovers the usual concept of size as "number of elements." However, it is more often difficult to ascribe "sizes" to infinite sets. A system of cardinal numbers can be developed to extend the role of natural numbers in answering "how many".

Most commonly, the Aleph numbers are used, since their definition naturally extends the process of counting, and it can be shown that every infinite set has cardinality equivalent to some Aleph. The set of natural numbers has cardinality .

The question of whether the real numbers have cardinality is known as the continuum hypothesis, which has been shown to be both unprovable and undisprovable in standard set theories such as Zermelo–Fraenkel set theory. Alternative set theories and additional axioms give rise to different properties and have often strange or unintuitive consequences.

However, every theory of cardinality using standard logical foundations of mathematics admits Skolem's paradox. The basic concepts of cardinality go back as early as the 6th century BCE, and there are several close encounters with it throughout history, however, the results were generally dismissed as paradoxical.

It is considered to have been first introduced formally to mathematics by Georg Cantor at the turn of the 20th century. Cantor's theory of cardinality was then formalized, popularized, and explored by many influential mathematicians of the time, and has since become a fundamental concept of mathematics.

Comparing sets

s. Although E is a proper subset of N, both sets have the same cardinality.|class=skin-invert-image An intuitive relationship between two sets having the "same size" is that their objects can be paired one-to-one. That is, if each object in one set can be assigned a dedicated "pair" in the other, and no object from either set left unpaired, there are the same number of objects in each set.

A one-to-one pairing between two sets defines a bijective function between them by mapping each object to its pair. Similarly, a bijection between two sets defines a pairing of their elements by pairing each object with the one it maps to. Therefore, these notions of "pairing" and "bijection" are, at least intuitively, equivalent.

Thus, the following definition is given: Two sets are said to have the same cardinality or be equinumerous if their members can be paired one-to-one. That is, if there exists a function between them which is bijective. This is often written as , or .

Alternatively, these sets may be said to be equivalent, similar, equipotent, or equipollent. For example, the set {{tmath|1=E = \{0, 2, 4, 6, \text{...}\} }} of even numbers has the same cardinality as the set {{tmath|1=\N = \{0, 1, 2, 3, \text{...}\} }} of natural numbers, since the function is a bijection from to .

The property for finite sets that "the whole is greater than the part" is no longer true for infinite sets, and the existence of surjections or injections that do not work does not prove that there is no bijection. For example, the function from to , defined by multiplying by 4, , is injective, but not surjective (since 2, for instance, is not mapped to).

Further, the function from to , defined by rounding down to the nearest even number, (cf. floor function), is surjective, but not injective, (since 0 and 1 for instance both map to 0). Neither nor can challenge , which was established by the existence of . .

Each guest goes to the room with a number that is double their room number, leaving the odd-numbered rooms vacant.|class=skin-invert-image Hilbert's paradox of the Grand Hotel is a popular thought experiment devised by the German mathematician David Hilbert to illustrate a counterintuitive property of countably infinite sets, allowing them to have the same cardinality as a proper subset of themselves. The scenario begins by imagining a hotel with an infinite number of rooms, one for each natural number, all of which are occupied.

But then a new guest walks in asking for a room. The hotel accommodates by moving the occupant of room 1 to room 2, the occupant of room 2 to room 3, room 3 to room 4, and in general, room n to room n+1. Then every guest still has a room, but room 1 is open for the new guest.

Then, the scenario continues by imagining an infinitely long bus of new guests seeking a room. The hotel accommodates by moving the person in room 1 to room 2, room 2 to room 4, and in general, room n to room 2n. Thus, all the even-numbered rooms are occupied, but all the odd-numbered rooms are vacant, leaving room for the infinite bus of new guests.

The scenario continues further by assuming an infinite number of these infinite buses arrive at the hotel, and showing that the hotel is still able to accommodate. Finally, an infinite bus which has a seat for every real number arrives, and the hotel is no longer able to accommodate. | quote = {{tmath|1=\begin{align} 1 \to & \; 0.{ \color{red} \textbf{6} }18033... \\ 2 \to & \; 0.1{ \color{red}\textbf{2} }3456... \\ 3 \to & \; 0.60{ \color{red}\textbf{7} }927... \\ 4 \to & \; 0.222{ \color{red}\textbf{2} }22... \\ \vdots \\ & \; 0.{ \color{red}\textbf{2323}22}... \end{align} }} | border = 0px | fontsize = 120% | bgcolor = #00000000 }} It begins by assuming, by contradiction, that there is some one-to-one mapping between the natural numbers and the set of real numbers between 0 and 1 (the interval ).

Then, take the decimal representation of each real number, for example, with a leading zero followed by any sequence of digits. The number 1 is included in this set since Considering these real numbers in a list, it is always possible to create a new number such that the first digit of the new number is different from that of the first number in the list, the second digit is different from the second number in the list, and so on.

The new number must also have a unique decimal representation, that is, it cannot end in repeating nines or repeating zeros. For example, if the digit is not 2, make the digit of the new number 2, and if it was 2, make it 3. Then, this new number will be different from each of the numbers in the list by at least one digit, and therefore must not be in the list.

This shows that the real numbers cannot be put into a one-to-one correspondence with the naturals, and thus must be strictly larger. : For every function f from to , the set disagrees with every set in the range of , hence cannot be surjective. The picture shows an example and the corresponding ; : , : .|class=skin-invert-image Another classical example of an uncountable set, established using a related reasoning, is the power set of the natural numbers, denoted .

This is the set of all subsets of , including the empty set and itself. The method is much closer to Cantor's original diagonal argument. Again, assume by contradiction that there exists a one-to-one correspondence between and , so that every subset of is assigned to some natural number.

These subsets are then placed in a list, in the order defined by (see image). Now, one may define a subset of which is not in the list by taking the negation of the "diagonal" of this list as follows: If , then , that is, if 1 is in the first subset of the list, then 1 is not in the subset .

Further, if , then , that is if the number 2 is not in the second subset of the list, then 2 is in the subset . Then in general, for each natural number , if and only if , meaning is put in the subset only if the nth subset in the list does not contain the number .

Then, for each natural number , , meaning, is not the nth subset in the list, for any number , and so it cannot appear anywhere in the list defined by . Since was chosen arbitrarily, this shows that every function from to must be missing at least one element, therefore no such bijection can exist, and so must be not be countable.

These two sets, and can be shown to have the same cardinality (by, for example, assigning each subset to a decimal expansion) called the cardinality of the continuum. Cantor's theorem generalizes the second theorem above, showing that every set is strictly smaller than its powerset.

In broad strokes, the proof goes as follows: Given a set , assume by contradiction that there is a bijection from to . Then, the subset given by taking the negation of the "diagonal", formally, , cannot be in the list. Therefore, every function is missing at least one element, and so .

Further, since is itself a set, the argument can be repeated to show . Taking , this shows that is even larger than , which was already shown to be uncountable. Repeating this argument shows that there are infinitely many "sizes" of infinity.

Cardinal numbers

In the above sections, "the cardinality of a set" was described relationally. In other words, one set could be compared to another, intuitively comparing their "size". Cardinal numbers are a means of measuring this "size" more explicitly.

For finite sets, this is simply the natural number found by counting the elements. This number is called the cardinal number of that set, or simply the cardinality of that set. The cardinal number of a set is generally denoted by , with a vertical bar on each side, though it may also be denoted by , , or .

For infinite sets, "cardinal number" is somewhat more difficult to define formally. However, cardinal numbers are not usually thought of in terms of their formal definition, but immaterially in terms of their arithmetic/algebraic properties.

The assumption that there is some cardinality function which satisfies (in prose, "two sets are equinumerous exactly when they map to the same cardinal number"), sometimes called the axiom of cardinality or Hume's principle, is sufficient for deriving most properties of cardinal numbers. Commonly in mathematics, if a relation satisfies the properties of an equivalence relation, the objects used to materialize this relation are equivalence classes, each of which group objects equivalent to one another.

These equivalence classes are called the Frege Russell cardinal numbers. However, these equivalence classes are too large to form sets (apart from the cardinal number whose only element is the empty set), since, for example, the cardinal number would be the set of all sets with one element, then , and would therefore contain itself, violating regularity.

Thus, due to John von Neumann, it is more common to assign representatives of these classes. , from the set to the set Y demonstrates that Y has cardinality 4.|class=skin-invert-image Given a basic sense of natural numbers, a set is said to have cardinality if it can be put in one-to-one correspondence with the set , analogous to counting its elements. For example, the set has a natural correspondence with the set , and therefore is said to have cardinality 4.

Other terminologies include "Its cardinality is 4" or "Its cardinal number is 4". In formal contexts, the natural numbers can be understood as some construction of objects satisfying the Peano axioms a list of properties, such that any system satisfying these properties is, in a certain sense, just like the natural numbers. Showing that such a correspondence exists is not always trivial.

Combinatorics is the area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. The notion cardinality of finite sets is closely tied to many basic combinatorial principles, and provides a set-theoretic foundation to recover them.

It can be shown by induction on the possible sizes of sets that finite cardinality corresponds uniquely with natural numbers (cf. ). This is related to several other concepts, verifying Hume's principle and the basis of bijective proofs, and is equivalent to a certain formulation of the pigeonhole principle, that a finite set cannot be put in one to one correspondence with a proper subset of itself. The addition principle asserts that given disjoint sets and , , intuitively meaning that the sum of the parts is equal to the whole.

The multiplication principle asserts that given two sets and , , intuitively meaning that there are ways to pair objects from these sets. Both of these can be proven by a bijective proof, together with induction. The more general result is the inclusion–exclusion principle, which defines how to count the number of elements in overlapping sets.

Naturally, a set is defined to be finite if it is empty or can be put in correspondence with the set , for some natural number . However, there exist other definitions of "finite" which do not rely on a definition of "number."

For example, a set is called Dedekind-finite if it cannot be put in one-to-one correspondence with a proper subset of itself, though this definition requires the axiom of choice to be equivalent to the original definition. The set of all cardinal numbers refers to a hypothetical set which contains all cardinal numbers.

Such a set cannot exist, which has been considered paradoxical, and related to the Burali-Forti paradox. Using the definition of cardinal numbers as representatives of their cardinalities. It begins by assuming there is some set {{tmath|1=S := \{ X \, \vert X \text{ is a cardinal number}\} }}.

Then, if there is some largest cardinal , then the powerset is strictly greater, and thus not in . Conversely, if there is no largest element, then the union contains the elements of all elements of , and is therefore greater than or equal to each element. Since there is no largest element in , for any element , there is another element such that and .

Thus, for any , , and so . Thus, the collection of all cardinal numbers is too large to form a set, and is a proper class.

Georg Cantor denoted the collection of all cardinal numbers (tav, the last letter of the Hebrew alphabet), and considered it to be an "inconsistent multiplicity". , containing all points in its continuum|314x314px|class=skin-invert-image The real numbers formalize the intuitive notion of the continuum: the unbroken, gapless set of points on the number line. There are numerous ways to construct and analyze the continuum in set theory, for example, sets of Cauchy sequences of rational numbers, or Dedekind cuts.

However, a somewhat informal definition as the set of infinite sequences of digits, e.g. , with the usual arithmetic and order is a popular and sufficient choice for basic arguments involving the continuum. The cardinality of this set, denoted " " (a lowercase fraktur script "c"), turns out to be remarkably stable under various transformations.

For example, all intervals on the real line e.g. , and , have the same cardinality as the entire set . First, is a bijection from to . The fact that two intervals of unequal length can be mapped one-to-one has been known, even if considered paradoxical, for thousands of years (cf. ). Further, the tangent function is a bijection from the interval to the whole real line.

A more surprising example is the Cantor set, which is defined as follows: take the interval and remove the middle third , then remove the middle third of each of the two remaining segments, and continue removing middle thirds (see image). The Cantor set is the collection of points that survive this process.

The remaining points are exactly those whose decimal expansion can be written in ternary without a 1. Reinterpreting these decimal expansions as binary (e.g. by replacing the 2s with 1s) gives a bijection between the Cantor set and the interval .

The Cantor set has a measure or "length" of zero, and yet is still equinumerous to the whole real line. construction, whose limit is a space-filling curve|class=skin-invert-image In the other direction, into higher dimensions, one can find a bijective map between a one-dimensional line and a two-dimensional square. Given a point in the unit square in (two-dimensional space) , one can interleave their digits to get the unique number in the unit interval .

Space-filling curves offer a more visual proof, giving a continuous map from the unit interval onto the unit square. Classical examples include the Peano curve and Hilbert curve. Although these maps are not bijective, they are indeed sufficient to show with the converse being immediate.

Both of these methods can be reused at each dimension to show that and thus for any dimension . Further, the infinite cartesian product can also be shown to be equinumerous to by cardinal arithmetic: . Thus, the real numbers, all finite-dimensional real spaces, and the countable cartesian product have the same cardinality.

As shown in , the set of real numbers is strictly larger than the set of natural numbers. Specifically, . The Continuum Hypothesis (CH) asserts that the real numbers have the next largest cardinality after the natural numbers, that is .

As shown by Gödel and Cohen, the continuum hypothesis is independent of ZFC, a standard axiomatization of set theory; that is, it is impossible to prove the continuum hypothesis or its negation from ZFC—provided that ZFC is consistent, meaning it produces no contradictions. ZFC imposes relatively little restriction on the cardinality of .

Easton's theorem shows that ZFC only requires two conditions: that , and a limit on its cofinality (roughly, how difficult it is to approach from below) implying that , though this is not an upper bound as it does not disallow the possibility that . The Generalized Continuum Hypothesis (GCH) extends this to all infinite cardinals, stating that for every ordinal .

Research on CH and GCH continues independent of ZFC, especially in descriptive set theory and through the exploration of large cardinal axioms. Without GCH, the cardinality of cannot be written in terms of specific alephs.

The Beth numbers ( , the second letter of the Hebrew alphabet) provide a concise notation for powersets of the real numbers starting from , then , and , and in general and if is a limit ordinal.

History

Cantor introduced the notion cardinal numbers together with ordinal numbers, which he viewed as abstractions of sets. For a given set , he wrote to mean the abstraction of that set from its elements, while maintaining their order, and cardinal numbers were a double abstraction, written .

Specifically, his definition was "the general concept which, with the aid of our intelligence, results from a set when we abstract from the nature of its various elements and from the order of their being given." This definition was considered to be imprecise, unclear, and purely psychological, and it would be some time before the concept was put on more rigorous footing.

He also introduced the Aleph sequence for infinite cardinal numbers. These notations appeared in correspondence and were formalized in his later writings, particularly the series Beiträge zur Begründung der transfiniten Mengenlehre (1895 1897). In these works, Cantor developed an arithmetic of cardinal numbers, defining addition, multiplication, and exponentiation of cardinal numbers.

This led to the formulation of the Continuum Hypothesis: whether . Cantor was unable to resolve CH and left it as an open problem.

See also

Infinitary combinatorics Multiplicity (mathematics) Natural density Numerosity (mathematics) Subcountability

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

Words in each sectionCardinal numbersCardinal numbersCardinal numbers: 1,526 words1,526Comparing setsComparing setsComparing sets: 1,279 words1,279HistoryHistoryHistory: 185 words185See alsoSee alsoSee also: 30 words30
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001375224217 · captured 2026-09-16 · ledger · version history

Cite this page as: encyclopegia.org, “Cardinality”, snapshot enwiki-001375224217. https://encyclopegia.org/a/cardinality

Sources cited in this revision

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