Cardinality

The cardinality of a set roughly refers to the number of elements in the set. For example card({1,3,5,7}) = 4 and card( $\varnothing$ ) = 0. The precise definition doesn't really assign a number to a set, but gives a way to compare cardinalities.

Definition: Two sets X and Y have the same cardinality (written as card(X) = card(Y)) if there is a bijection between X and Y.
Injection-Surjection-Bijection
The above picture illustrates what surjections, injections and bijections are. A map f:X → Y is surjective if for every y ∈ Y there is x ∈ X such that f(x) = y. A map g:X → Y is injective if x ≠ y implies g(x) ≠ g(y). Finally h is bijective if it is injective and surjective. We say that card(X) ≥ card(Y) if there is a surjection f: X → Y, and card(X) ≤ card(Y) if there is an injection g:X → Y. The following theorem gives an answer to a very natural question, but the proof is not straightforward, because in general f and g can be different maps.

Theorem (Schröder-Bernstein): If card(X) ≥ card(Y) and card(X) ≤ card(Y), then card(X) = card(Y).

The definition of cardinality allows us to compare sets also if they are infinite. The simplest infinite set is the set of natural numbers N = {1,2,3,4,5,....}. Any set with the same cardinality as N is called countable or denumerable, and we use the Hebrew letter ℵ₀ (Aleph null) to denote its cardinality.

Cardinality (and in fact set theory) was initiated by the 19^th century German mathematician Georg Cantor (1845-1915). His life's work didn't meet with as much recognition as in later decades. Especially Leopold Kronecker disliked him, and barred several career moves. In the end Cantor's struggle with mathematics, unhelpful colleagues and life as a whole broke his spirit and he died in a clinic in Halle. In later years, David Hilbert descirbed Cantor's work as

...the finest product of mathematical genius and one of the supreme achievements of purely intellectual human activity.

Let us also not forget Cantor's artistic talents, far right.

Proving that certain set A are countable can be done by finding a denumeration of A, that is, a way to number A as {a₁, a₂, a₃, ...} so that all elements of A get their own natural number as index, and no element is left out. Using this methods, it is easy to understand why the following theorem is true.

Theorem: Every infinite subset of the integers is countable.

In particular the following sets are countable, even though they are proper subsets of N: The odd numbers {1,3,5,7,9,....}, the prime numbers {2,3,5,7,11,13,...}, the squares {1,4,9,16,25,...}.

Some more countable sets and their (graphical) denumerations are given in the following theorems.

Theorem: If A is countable, then the Cartesian product A x A = { (a,b) : a and b ∈ A} is also countable.	Theorem: The set of rational numbers is countable.

There are infinite sets of higher cardinality than N. Such sets are called uncountable .

Theorem: The set of real numbers R is uncountable.

The cardinality of R is denoted as $\mathfrak{c}$ ; it stands for continuum.

Proof: This proof is known as Cantor's diagonal argument.

Assume by contradiction that R is countable. Then there is a denumeration of R, and in particular a denumeration of of the real numbers between 0 and 1. The picture above illustrates this denumeration: each real number x has its decimal expansion 0.x₁x₂x₃x₄.... On the diagonal we have a number D = 0.a₁b₂c₃d₄.... Make a new number D' = 0.a'₁b'₂c'₃d'₄.... by changing every digit of D that was not 5 into a 5, and every digit 5 into a 6. Clearly 0 < D' < 1. It is impossible that D' is on the list, because if D' is on the n^th row, then the n-th digit of D' is different from the n-th digit of the diagonal number. But it is the same digit! Hence we have a contradiction, and this completes the proof. QED

Now that we know that $\mathfrak{c}$ > ℵ₀, it is natural to ask whether there are any cardinal numbers in between. This is the famous

Continuum Hypothesis: $\mathfrak{c}$ is first cardinal number larger than ℵ₀.

Strangely enough, you cannot prove nor disprove this hypothesis. You need to treat it as a new axiom about numbers. Whether you accept the Continuum Hypothesis or not is up to you: for either case you can build a logical model that is just as consistent as the axiomatic system known as the Zermelo-Fraenkel set theory (ZF). Indeed, Kurt Gödel proved in 1939 that the Continuum Hypothesis cannot be disproved in (ZF), but Paul Cohen proved the opposite in 1963: the negation of the Continuum Hypothesis is also consistent with (ZF). Look here for a history of set theory.


Kurt Gödel (1906-1978)	Paul Cohen (1934-2007)	Ernst Zermelo (1871-1953)	Adolf Fraenkel (1891-1965)

Definition The power set of A is the collection of all subsets of A, including the empty set. It is denoted as P(A).
For example, if A = {1,2,3}, then the power set of A is { $\varnothing$ , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }. It has 8 elements and it is not a coincidence that 8 = 2³ = 2^card(A). Indeed, for every element of A we have the choice of including or excluding it from a subset of A, and any one of these 2^card(A) choices gives a different subset of A.
With this in mind, we have the following notation for cardinalities of power sets: card(P(A)) = 2^card(A) . For example, $\mathfrak{c}$ = 2^ℵ₀.

Theorem: The cardinality of A is always strictly less than the cardinality of its power set.

By taking the power set of the power set of the power set of the.... we can sets of arbitrarily high cardinality.

Proof: Clearly card(A) ≤ card(P(A)) because g(a) = {a} is an injection from A into P(A). Suppose by contradiction that A and P(A) have the same cardinality, and suppose that h:A → P(A) is a bijection. Let

B = {a ∈ A : a ∉ h(a)}

Then B ∈ P(A), and so there is b ∈ A with B = h(b). But there is no sensible answer to the question whether b belongs to B.
If b ∈ B, then by definition of B, b ∉ B.
If b ∉ B, then by definition of B, b should be in B.
This paradox shows that the bijection h does not exist, and therefore A and P(A) have different cardinalities. The only remaining possibility is card(A) < card(P(A)). QED

This proof may remind you a bit of the paradox of the barber of Sevilla, who shaves every man in Sevilla who doesn't shave himself. (Does this (male) barber shave himself?) Or the book that lists every book that doesn't mention itself. All these paradoxes boil down to the impossibility, in its most terse form, of the set {a : a ∉ a}. This is known as Russell's paradox.

Some more examples of sets and their cardinalities:

Set	Cardinality
the integers Z	ℵ₀
the algebraic numbers	ℵ₀
the transcendental numbers	$\mathfrak{c}$
Rⁿ for n = 1,2,3,...	$\mathfrak{c}$
the set of all real sequences {x₁, x₂, x₃, ...}	$\mathfrak{c}$
the Cantor set	$\mathfrak{c}$
the set of all functions f:N → N	$\mathfrak{c}$
the set of all continuous functions f:R → R	$\mathfrak{c}$
the set of all functions f:R → {0,1}	2
the set of all functions f:R → R	2

Further reading:

Paul Halmos, Naive set theory, Springer Verlag, Heidelberg, 1960.
Martin Aigler, Günter Ziegler, Proofs from THE BOOK, Springer Verlag, Heidelberg 2000.
Cardinal numbers
Ordinal numbers
Hilbert's Grand Hotel