Cardinality

Cardinality

Cardinality is the mathematical concept that measures the size of sets. For finite sets, cardinality is simply the number of elements. For infinite sets, cardinality reveals surprising and counterintuitive distinctions between different sizes of infinity.

The theory of cardinality, developed by Georg Cantor in the late 19th century, revolutionized mathematics and established set theory as a foundation for modern mathematics.

Finite Cardinality

The cardinality of a finite set A is the number of distinct elements in A, denoted |A| or card(A).

For example, if A = {1, 2, 3, 4, 5}, then |A| = 5.

The empty set has cardinality zero: |{}| = 0.

The cardinality of a finite set A is the number of distinct elements in A, denoted |A| or card(A).

For example, if A={1,2,3,4,5}, then |A|=5.

The empty set has cardinality zero: |{}|=0.

Comparing Cardinalities: Bijections

Two sets A and B have the same cardinality if there exists a bijection (one-to-one correspondence) between them. This means every element of A is paired with exactly one element of B, and vice versa.

We write |A|=|B| or A∼B (A) is equinumerous with (B) when such a bijection exists.

This definition extends naturally to infinite sets, where counting elements directly is not possible.

Countably Infinite Sets

A set is countably infinite if it has the same cardinality as the natural numbers ℕ={0,1,2,3,…}. This cardinality is denoted aleph-null (aleph-nought):

|ℕ|=(ℵ_0)

A set is countable if it is either finite or countably infinite.

Examples of Countably Infinite Sets

The integers ℤ are countably infinite. A bijection with ℕ is:
0↦0,1↦1,−1↦2,2↦3,−2↦4,…

The rational numbers ℚ are countably infinite. Cantor's diagonal argument constructs a bijection by listing rationals in a grid and traversing diagonally.

The set of algebraic numbers (roots of polynomials with integer coefficients) is countably infinite.

Any infinite subset of a countable set is countable.

Uncountable Sets

Cantors revolutionary discovery was that some infinite sets are strictly larger than the natural numbers. Such sets are called uncountable.

Cantors Diagonal Argument

Theorem: The real numbers ℝ are uncountable.

Proof: Suppose, for contradiction, that the reals in [0,1] are countable. List them as decimals:

(r_1)=0.*(d_11)((d_12)((d_13)))…

(r_2)=0.*(d_21)((d_22)((d_23)))…

(r_3)=0.*(d_31)((d_32)((d_33)))…

Construct a new number r whose n-th digit differs from (d_n*n). Then r differs from every (r_n) in the list, contradicting our assumption that we listed all reals in [0,1].

The cardinality of the reals is called the cardinality of the continuum:

|ℝ|=c=2

Cantors Theorem

Cantor's theorem states that for any set A, the power set 𝒫*(A) (the set of all subsets of A) has strictly greater cardinality:

|A|<|𝒫*(A)|=2

This means there is no largest cardinality. Given any set, we can construct a strictly larger one by taking its power set. This produces an infinite hierarchy of infinities.

Cardinal Arithmetic

Operations on sets induce operations on cardinalities:

Cardinal addition: |A|+|B|=|A∪B| when A and B are disjoint.

Cardinal multiplication: |A|⋅|B|=|A×B| (Cartesian product).

Cardinal exponentiation: |A||B|=|functions from B to (A|.

Properties of Infinite Cardinals

For infinite cardinals, arithmetic behaves differently from finite numbers:

(ℵ_0)+(ℵ_0)=(ℵ_0)

(ℵ_0)⋅(ℵ_0)=(ℵ_0)

c+c=c

c⋅c=c

Adding or multiplying an infinite cardinal by itself (or any smaller cardinal) gives the same cardinal. But exponentiation always increases: 2>(ℵ_0).

The Continuum Hypothesis

The Continuum Hypothesis (CH) states that there is no set whose cardinality is strictly between that of the integers and the reals:

(ℵ_1)=2=c

where (ℵ_1) is defined as the smallest uncountable cardinal.

Remarkably, Gödel (1940) and Cohen (1963) showed that CH is independent of the standard axioms of set theory (ZFC): it can be neither proved nor disproved from these axioms.

Cardinality Comparisons

We write |A| at most |B| if there exists an injection from A to B (A embeds into B).

We write |A|<|B| if |A| at most |B| but |A| is not equal to |B|.

Schroder-Bernstein Theorem

If |A| at most |B| and |B| at most |A|, then |A|=|B|. This theorem allows us to prove two sets have equal cardinality by finding injections in both directions.

Applications

Cardinality arguments appear throughout mathematics. In analysis, the uncountability of the reals implies that almost all real numbers are transcendental (since algebraic numbers are countable).

In computability theory, the uncountability of real numbers compared to the countability of computable numbers shows that most reals are not computable.

Key Results Summary

The integers, rationals, and algebraic numbers are all countable with cardinality (ℵ_0).

The reals, irrationals, transcendentals, and any interval of reals all have cardinality continuum.

The set of all functions from ℕ to ℕ has cardinality continuum.

The power set of the reals, 𝒫*(ℝ), has cardinality 2, strictly larger than the continuum.

Historical Significance

Cantors work on cardinality was initially controversial. His proof that the reals are uncountable showed for the first time that not all infinities are equal. This discovery transformed mathematical thinking about infinity and set theory.

David Hilbert called Cantors work a paradise from which mathematicians would never be driven. Despite early opposition, Cantors ideas became foundational to modern mathematics.

Cardinality remains central to set theory, logic, and the foundations of mathematics, providing a rigorous way to compare the sizes of infinite collections.

Ordinal Numbers

Related to cardinality is the concept of ordinal numbers, which describe the order type of well-ordered sets. While cardinal numbers measure how many elements are in a set, ordinal numbers capture the structure of how elements are arranged.

The study of ordinals and cardinals together forms the foundation of transfinite mathematics and continues to be an active area of research in set theory.