Cardinality
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.
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.
Two sets are said to be equinumerous or have the same cardinality if there exists a one-to-one correspondence between them. Otherwise, one is said to be strictly larger or strictly smaller than the other. 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—for example, the set of all real numbers or the powerset of the set of natural numbers.
For finite sets, cardinality coincides with the natural number found by counting their elements. However, it is more often difficult to ascribe "sizes" to infinite sets. Thus, a system of cardinal numbers can be developed to extend the role of natural numbers in answering "how many". The [|cardinal number] corresponding to a set is written as between two vertical bars. Most commonly, the Aleph numbers are used, since it can be shown 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 unprovable 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, which roughly asserts that basic properties of cardinality are not absolute, but relative to the model in which the cardinality is measured.
Introduction
Definition
Cardinality is an inherent property of sets which defines their size, roughly corresponding to the number of individual objects they contain. 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 doesn't know how many of each there are. Thus, cardinality is measured by putting sets in one-to-one correspondence. 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.Georg Cantor, the originator of the concept, defined cardinality as "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. Thus, cardinal numbers, a means of measuring cardinality, became the main way of presenting the concept. The distinction between the two is roughly analogous to the difference between an object's mass and its mass in kilograms.
Note on notation and terminology
The basic concepts of cardinality are developed in terms of sets and functions, which are somewhat 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 members of one set to the members 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, one can determine the output. For example, one may define a function from the natural numbers to the natural numbers by multiplying by two:
Etymology and related terms
The term cardinality originates from the post-classical Latin cardo, 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 cardinal numbers. The last of which referred to numbers used for counting, as opposed to ordinal numbers, which express order, and nominal numbers used for labeling without meaning.In mathematics, the notion of cardinality was first introduced by Georg Cantor in the late 19th century, wherein he 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. The terms cardinality and cardinal number were eventually adopted from the grammatical sense, and later translations would use these terms.
Comparing sets
Equinumerosity
The intuitive property of two sets having the "same size" is that their objects can be paired one-to-one. 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 intuitively equivalent. In fact, it is often the case that functions are defined literally as this set of pairings. Thus, the following definition is given:Two sets and 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 which is bijective. This is written as and eventually once has been defined. Alternatively, these sets, and 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 intuitive 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 don't work does not prove that there is no bijection. For example, the function from to, defined by is injective, but not surjective, and from to, defined by is surjective, but not injective,. Neither nor can challenge which was established by the existence of.
Equivalence
A fundamental result necessary in developing a theory of cardinality is relating it to an equivalence relation. A binary relation is an equivalence relation if it satisfies the three basic properties of equality: reflexivity, symmetry, and transitivity.- Reflexivity: For any set,
- * Given any set there is a bijection from to itself by the identity function, therefore equinumerosity is reflexive.
- Symmetry: If then
- * Given any sets and such that there is a bijection from to then there is an inverse function from to which is also bijective, therefore equinumerosity is symmetric.
- Transitivity: If and then
- * Given any sets and such that there is a bijection from to and from to then their composition is a bijection from to and so cardinality is transitive.
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 '. This is written and eventually 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 or For example, if has four elements and has five, then the following are true andThe basic properties of an inequality are reflexivity, transitivity and antisymmetry . Cardinal inequality as defined above is reflexive since the identity function is injective, and is transitive by function composition. Antisymmetry is established by the Schröder–Bernstein theorem.
The above shows that cardinal inequality is a partial order. A total order has the additional property that, for any and, either or This can be established by the well-ordering theorem. Every well-ordered set is isomorphic to a unique ordinal number, called the order type of the set. Then, by comparing their order types, one can show that or. This result is equivalent to the axiom of choice.