Cardinal Numbers
The key to a definition of cardinal numbers is the notion of a 1-1 correspondence. Two sets are said to be of the same cardinality if there exists a 1-1 correspondence between the two. Two finite sets have the same cardinality only if they have the same number of elements. Their common number of elements serves to denote their cardinality. So the term finite cardinal number is a synonym for natural number. The cardinality of the set
|{1, 2, 3, 4, 5}| = 5
and
|Ø| = 0.
(No less frequent is another one A. I'll be using the vertical bars as more manageable in the HTML environment.)
For finite sets, the cardinality of a proper subset is strictly less than the cardinality of the set itself:
(1) | A ⊂ B and A ≠ B implies |A| < |B|. |
As we know, this is not true for infinite sets. If E is the set of even natural numbers and N the set of all natural numbers then
The fact that a proper subset of a set may have a cardinality equal to that of the set itself is often taken as the definition of infinite sets: a set is infinite if is contains a proper subset of the same cardinality.
For disjoint finite sets,
(2) | |A∪B| = |A| + |B|. |
For disjoint sets of which at least one is infinite,
(3) | |A∪B| = max{|A|, |B|}. |
The two cases can be combined if we define the addition of two cardinal numbers as the cardinality of the union of two disjoint sets with the given cardinalities. I.e., if we use (2) for any two sets A and B (whether finite or infinite), to define
(4) | |A| + |B| = max{|A|, |B|}, |
provided at least one of the sets A, B is infinite. Cardinalities corresponding to infinite sets are called transfinite.
For either finite or infinite sets, it is true that
(1') | A ⊂ B implies |A| ≤ |B|. |
For finite sets,
(5) | |A| ≤ |B| and |B| ≤ |A| implies |A| = |B|. |
With all the differences in behavior between finite and infinite sets, it may be surprising that (5) holds for transfinite cardinalities as well. (5) is the content if Cantor-Bernstein-Schroeder theoremSchröder-Bernstein theorem. The theorem comes under many alternative names, e.g. the attributions Cantor-Bernstein-Schroeder theorem, Cantor-Bernstein theorem, Schroeder-Bernstein Theorem, Bernstein's theorem, all usually refer to the same statement.
In order to prove the theorem we need to pay more attention to the "≤" relation as applied to the transfinite cardinals, something we glossed over in (3) and (4).
We say that |A| ≤ |B| if there exists an injection
A subset S of a set A is categorized by a binary function
Theorem
For any A, |A| < |2^{A}|.
Proof
The proof is by the diagonal process invented by G. Cantor.
First of all, |A| ≤ |2^{A}| because an element a of A can be identified with the 1-element set {a}. Suppose to the contrary that there is a 1-1 correspondence
(6) | S = {a ∈ A: a ∉ f(a)}. |
Since f is assumed to be 1-1, it is surjective: there is an
Indeed, either s belongs to S or it does not. Let's check the first possibility first. It can't be that
It follows that our assumption of the existence of a 1-1 correspondence between A and 2^{A} leads to a contradiction. The conclusion follows:
Starting with any set A we may construct a sequence of sets
(7) | A, 2^{A}, 2^{2A}, 2^{22A}... |
As a consequence of the theorem, the cardinalities of the sets in sequence (7) are all different. Furthermore,
(8) | |A| < |2^{A}| < |2^{2A}| < |2^{22A}| < ... |
The usual notation for the exponentiation of cardinalities is
(9) | 2^{|A|} = |2^{A}|. |
The set of real numbers, the continuum has the cardinality (also called continuum)
c = . |
(This is because the real numbers in the interval
c = , |
i.e., the "next" cardinal number after . The assertion became known as the Continuum Hypothesis (CH): there are no cardinal numbers between and c or, in other words,
(10) |
The investigation into CH has been crowned by two results, 25 years apart, that had profound repercussion on the whole notion of the axiomatization of mathematics.
Set Theory, as developed by G. Cantor, is often termed naive as it was based on the intuitive notion of sets and their properties. Everything was a set until it was realized, first by B. Russell, that such an unrestricted handling of sets leads to contradictions. For example, the idea of the "set of all sets" is contradictory. To avoid such constructs and keep Set Theory contradiction-free mathematician came up with several axiomatic systems, of which the one known as Zermelo-Fraenkel (ZF) became the most popular.
In 1939, Kurt Gödel proved that CH does not contradict to ZF and, therefore, could not be disproved based on ZF. In 1963, Paul Cohen proved a similar result for the negation of CH which showed that CH can't be derived from ZF either.
There are many more cardinals than is suggested by (7). There are some with so peculiar construction that they are termed inaccessible (not to the human mind of course). To grasp what are these one needs the notion of a different kind of infinities, viz., the ordinal numbers.
|Contact| |Front page| |Contents| |Up| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny