Cardinality

In mathematics, cardinality is the size of a set, denoted $|A|$ or $\operatorname{card}(A)$. For a finite set, it is the number of distinct elements. For infinite sets, size is defined through one-to-one correspondence rather than ordinary counting. Two sets have equal cardinality exactly when a bijection exists between them. Cardinality is a central concept of set theory, allowing infinite collections to be compared and revealing that infinity has more than one possible size. (plato.stanford.edu)

Definition and comparison

A bijection $f:A\to B$ pairs every element of $A$ with exactly one element of $B$, with neither repetitions nor omissions. Sets admitting such a correspondence are called equinumerous or equipotent. This notion defines an equivalence relation: every set is equinumerous with itself, and equinumerosity is symmetric and transitive. The empty set has cardinality $0$; a set equinumerous with $\{0,\ldots,n-1\}$ has cardinality $n$. The identities of its elements do not affect its size. (plato.stanford.edu)

Comparison uses an injective function:

Thus, a subset cannot have greater cardinality than its containing set. Strict inequality means that such an injection exists but no bijection does. The Schröder–Bernstein theorem states that injections in both directions imply equal cardinality. It often establishes equality without requiring an explicit bijection. The theorem does not require the axiom of choice. (cs.cornell.edu)

Finite and countably infinite sets

A countably infinite set has the same cardinality as the natural numbers, written $\aleph_0$, pronounced “aleph-null.” Its elements can be listed as $a_0,a_1,a_2,\ldots$, with each appearing exactly once. “Countable” commonly includes finite sets as well, although terminology varies between texts. (cs.cornell.edu)

The integers are countably infinite: one listing is

The rational numbers are also countable. Fractions can be arranged by numerator and denominator and traversed systematically, omitting duplicate representations. Their density on the number line therefore does not make them uncountable. (plato.stanford.edu)

An infinite set can have the same cardinality as a proper subset. For example, $n\mapsto2n$ is a bijection from the natural numbers to the nonnegative even integers. This differs from finite counting, where removing an element always decreases cardinality. In set theory with choice, every infinite set is equinumerous with some proper subset of itself; without choice, that characterization is not equivalent to infinity in general. (cs.cornell.edu)

Uncountability and the continuum

The set of real numbers is uncountable. Cantor’s diagonal argument establishes this by showing that any proposed enumeration can be used to construct a real number absent from the list. Its cardinality is called the cardinality of the continuum, denoted $\mathfrak c$, and satisfies

It equals the cardinality of all subsets of the natural numbers. (plato.stanford.edu)

More generally, Cantor’s theorem states that every set has strictly smaller cardinality than its power set:

If a surjection $f:A\to\mathcal P(A)$ existed, the subset $D=\{a\in A:a\notin f(a)\}$ would differ from every $f(a)$, a contradiction. Repeated power-set formation consequently produces successively larger cardinalities; there is no largest cardinal. (plato.stanford.edu)

Cardinal numbers and ordering

In Zermelo–Fraenkel set theory with the axiom of choice, abbreviated ZFC, every set can be well-ordered. Its cardinality can therefore be represented by the least ordinal number equinumerous with it, called an initial ordinal. Infinite cardinals form the aleph hierarchy

where $\aleph_1$ is the least uncountable cardinal and each successor aleph is the least cardinal greater than its predecessor. (bpb-us-e2.wpmucdn.com)

Cardinality records size, whereas ordinals record order type. The orders represented by $\omega$ and $\omega+1$, for example, differ because the latter has a final element, yet both have cardinality $\aleph_0$. Without choice, bijections and injections still define size comparisons, but some sets cannot be well-ordered, and not all cardinalities need be comparable. (plato.stanford.edu)

Cardinal arithmetic

Cardinal addition counts a disjoint union; multiplication counts a Cartesian product. Exponentiation $\kappa^\lambda$ counts all functions from a set of cardinality $\lambda$ to one of cardinality $\kappa$. These operations agree with ordinary arithmetic for finite cardinalities. For infinite cardinals, assuming choice,

when both are infinite. In particular, $\aleph_0+\aleph_0=\aleph_0^2=\aleph_0$. Cardinal arithmetic must be distinguished from ordinal arithmetic, whose operations also reflect ordering. (plato.stanford.edu)

Exponentiation is less completely determined. Although Cantor’s theorem gives $2^\kappa>\kappa$, it does not specify which larger cardinal $2^\kappa$ is. The continuum hypothesis asserts $2^{\aleph_0}=\aleph_1$, equivalently that no cardinality lies strictly between those of the natural and real numbers. Gödel’s 1938 consistency result and Cohen’s 1963 independence result show that, if ZFC is consistent, it proves neither this hypothesis nor its negation. The generalized continuum hypothesis extends the assertion to every infinite cardinal: $2^\kappa=\kappa^+$, where $\kappa^+$ is the next larger cardinal. (plato.stanford.edu)