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() = 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.
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
ℵ_{0} (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_{1}, a_{2}, a_{3}, ...}
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
; 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_{1}x_{2}x_{3}x_{4}....
On the diagonal we have a number D = 0.a_{1}b_{2}c_{3}d_{4}....
Make a new number D' = 0.a'_{1}b'_{2}c'_{3}d'_{4}.... 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 > ℵ_{0},
it is natural to ask whether there
are any cardinal numbers in between. This is the famous
Continuum Hypothesis:
is first cardinal number larger than ℵ_{0}.
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) |
Some more examples of sets and their cardinalities:
Set | Cardinality |
the integers Z | ℵ_{0} |
the algebraic numbers | ℵ_{0} |
the transcendental numbers | |
R^{n} for n = 1,2,3,... | |
the set of all real sequences {x_{1}, x_{2}, x_{3}, ...} | |
the Cantor set | |
the set of all functions f:N → N | |
the set of all continuous functions f:R → R | |
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