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.
Basics
Definition Cardinality is an inherent property of sets which defines their size, roughly meaning the number of individual objects they contain.: "CARDINALITY, cardinal number, of a set A - That property of A which is inherent in any set B equivalent to A. Here two sets are called equivalent (or equipotent or of the same cardinality) if it is possible to construct a one-to-one correspondence between them." Fundamentally however, it is different from the concepts of number or counting as the cardinalities of two sets can be compared without referring to their number of elements, or defining number at all. For example, in the image above, a set of apples is compared to a set of oranges such that every fruit is used exactly once which shows these two sets have the same cardinality, even if one does not know how many of each there are. Thus, cardinality is measured by putting sets in so-called one-to-one correspondence: each object in one set can be assigned a dedicated "pair" in the other, and no object from either set left unpaired. If it is possible, the sets are said to have the same cardinality, and if not, one set is said to be strictly larger or strictly smaller than the other.
Sets and functions not surjectivesurjectivenot injectivegeneral functionsurjective onlyinjectiveinjective onlybijective The basic concepts of cardinality are developed in terms of sets and functions, which are more abstract than their counterparts outside of mathematics. Informally, a set can be understood as any collection of objects, usually represented with curly braces. For example, specifies a set, called , which contains the numbers 1, 2, and 3. The symbol represents set membership, for example says "1 is a member of the set " which is true by the definition of above. Here is finite, but that is not a requirement in general. The only requirement for a set is that it is well-defined. That is, for any object, , one can determine whether belongs to that set , or does not belong to that set . One example of an infinite set is the set of all natural numbers .
A function, or correspondence, maps each member of one set to a unique member of another, often represented with an arrow diagram. For example, the adjacent table depicts several functions which map sets of natural numbers to sets of letters. If a function does not map two members to the same place, it is called injective. If a function covers every member in the output set, it is called surjective. If a function is both injective and surjective, it is called bijective or a one-to-one correspondence. Functions are not limited to those one can draw an arrow diagram for, so long as the function is well-defined. That is, for each possible input, the output is defined. For example, one may define a function on the natural numbers by multiplying by two:
Etymology and related terms The term cardinality originates from the post-classical Latin cardo ("to hinge"), which referred to something central or pivotal, both literally and metaphorically. This passed into medieval Latin and then into English, where cardinal came to describe things considered to be, in some sense, fundamental, such as, cardinal sins, cardinal directions, and (in linguistics) cardinal numbers.Oxford English Dictionary, "cardinal (adj.), Etymology," March 2025, https://doi.org/10.1093/OED/1490074521.Harper, Douglas, "Origin and history of cardinal", Online Etymology Dictionary, accessed April 20, 2025. The last of which referred to numbers used for counting (e.g., one, two, three),Oxford English Dictionary, "cardinal number (n.), sense 1," July 2023, https://doi.org/10.1093/OED/3193437451. as opposed to ordinal numbers, which express order (e.g., first, second, third),Oxford English Dictionary, "ordinal (n.2)," , https://doi.org/10.1093/OED/6032173309. and nominal numbers used for labeling without meaning (e.g., jersey numbers and serial numbers).
In mathematics, the notion of cardinality was first introduced by German mathematician Georg Cantor in the late 19th century, who used the term Mächtigkeit, which may be translated as "magnitude" or "power", though Cantor credited the term to a work by Jakob Steiner on projective geometry. Around 1930, the terms cardinality and cardinal number were adopted from the grammatical sense, and later translations would use these terms.Harper, Douglas, "Origin and history of cardinality", Online Etymology Dictionary, accessed April 20, 2025.Oxford English Dictionary, "cardinality (n.2), Etymology," March 2025, https://doi.org/10.1093/OED/5444748676.
Comparing sets
Equinumerosity
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 of even numbers has the same cardinality as the set 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 .
Equivalence
A fundamental result in developing a theory of cardinality is that equinumerosity forms an equivalence relationthat is, a relation satisfying the same three basic properties as equality: reflexivity, symmetry, and transitivity.
Reflexivity, the property that every set has the same cardinality as itself , follows from the identity function: for any set , the function that maps each element to itself is a bijection from to . Symmetry, the property that, if has the same cardinality as , then has the same cardinality as , holds because any bijection has an inverse function , which is also bijective. Transitivity, the property that if and have the same cardinality , and and have the same cardinality then so do and , follows from the composition of functions: given bijections and , their composition is a bijection from to (see image).
Since equinumerosity satisfies all three properties, it is an equivalence relation. This means that it groups sets into equivalence classesgroups of sets that are all equinumerous with one anotherwhere each group defines a possible size of a set. This motivates the notion of cardinal numbers, which are representatives that stand for the "size" of each group, developed in the section below.
Inequality
A set is not larger than a set if it can be mapped into without overlap. That is, the cardinality of is less than or equal to the cardinality of if there is an injective function from to , or equivalently, if there is a surjection from to (or is empty). This is written , or . and read as " is not greater than ," or " is dominated by ." If , but there is no injection from to , then is said to be strictly smaller than , written without the underline as . For example, if has four elements and has five, then the following are true , , and .
The basic properties of an inequality are reflexivity (for any , ), transitivity (if and , then ) and antisymmetry (if and , then ). Cardinal inequality as defined above is reflexive since the identity function is injective, and is transitive by function composition. Antisymmetrythe fact that, given injections in both directions, then one can find a bijectionis non-trivial, and is the content of the so-called Schröder–Bernstein theorem. One such proof can be summarized as follows, with the help of the adjacent illustration: