# 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} is 5. Cardinality of the empty set Ø is 0. A frequent notation for the cardinality of set A is |A|, so that

|{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 |E| = |N|. The cardinality of both is denoted (pronounced aleph-null or aleph-zero), where is the first letter of the Hebrew alphabet.

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 |A| + |B|. In this case, (3) converts to

 (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 f: A→B. Bernstein's theorem then asserts that if there exists an injection from A to B and another from B to A, then there is a 1-1 correspondence between A and B. (The proof of the theorem appears elsewhere.) We say that |A| < |B| iff |A| ≤ |B| and |A| ≠ |B|.

A subset S of a set A is categorized by a binary function f: A → {0, 1} such that S = {a∈A: f(a) = 1}. For this reason, the set of all subsets of A is denoted 2A.

### Theorem

For any A, |A| < |2A|.

### Proof

The proof is by the diagonal process invented by G. Cantor.

First of all, |A| ≤ |2A| 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 f: A → 2A. Function f relates to each element a of A a subset f(a) of A. There are two possibilities: either a ∈ f(a) or not. Let's define set S as a collection of the elements of a ∈ A that do not belong to their image f(a):

 (6) S = {a ∈ A: a ∉ f(a)}.

Since f is assumed to be 1-1, it is surjective: there is an s ∈ A such that S = f(s). This creates a problem.

Indeed, either s belongs to S or it does not. Let's check the first possibility first. It can't be that s ∈ S, because, by definition, S consists of those a for which a ∉ f(a). So that if s ∈ S then, too, s ∉ S. We see that it can't be that s ∈ S. But s ∉ S is also impossible, for if this were the case, s would be an element of S, by the same definition.

It follows that our assumption of the existence of a 1-1 correspondence between A and 2A leads to a contradiction. The conclusion follows: |A| < |2A|.

Starting with any set A we may construct a sequence of sets

 (7) A, 2A, 22A, 222A...

As a consequence of the theorem, the cardinalities of the sets in sequence (7) are all different. Furthermore,

 (8) |A| < |2A| < |22A| < |222A| < ...

The usual notation for the exponentiation of cardinalities is

 (9) 2|A| = |2A|.

The set of real numbers, the continuum has the cardinality (also called continuum)

 c = .

(This is because the real numbers in the interval [0, 1) when represented in the binary system by the sequences of 0s and 1s can be identified (with some precautions) with subsets of the natural numbers.) Cantor believed but could not prove that

 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.