Cardinality of sets: measuring the size of finite and infinite collections

Comparing sizes of sets

Two sets are said to have the same (or equal) cardinality precisely when there exists a one-to-one correspondence between their members. In other words, a pairing that matches each element of one set to exactly one element of the other (and vice versa) shows the sets share the same cardinality.

To express that the cardinality of A is less than or equal to that of B, one can provide an injective function from A into B. If such an injection exists, every element of A maps to a distinct element of B, so no two elements of A share an image in B. The reverse statement—an injective map from B into A—similarly implies the cardinality of B is at most that of A.

Finite and infinite cardinalities

If a set has a finite number of elements, its cardinality is a natural number (0, 1, 2, …). Infinite sets do not have a natural-number size; instead, their cardinalities are compared using correspondences such as injections, surjections, and bijections. Some infinite sets can be matched one-to-one with the integers and are called countably infinite, while others cannot and are called uncountable; these notions allow a finer classification of infinite sizes.

Cardinality versus other notions of size

Cardinality is one formal way to assign a size to a set by counting or by establishing correspondences. Other mathematical concepts, for example measures in analysis, quantify different aspects of "size" (like length, area, or probability) and serve different purposes than cardinality.