9. Sets of cardinality continuum, comparing cardinality

Comparing cardinality

We shall say that the cardinality of A is not greater than the cardinality of B (denoted by |A|\leq |B|) if there exists a 1-1 function f\colon A\to B.

We say that the cardinality of A is not less than the cardinality B (denoted by |A|\geq |B|) if there exists an ,,onto” function f\colon A\to B.

E.g. |\mathbb{R}|\geq |\mathbb{Z}|, because f(x)=\lfloor x\rfloor is a function from \mathbb{R} onto \mathbb{Z}.

The Theorem of Cantor-Bernstein, states that if |A|\leq |B| and |A|\geq |B|, then the sets A and B have the same cardinality (so if there exist f,g\colon A\to B, such that f is 1–1 and g is onto then there is a bijection h\colon A\to B).

We shall write that |A|<|B|, if |A|\leq |B|, but A and B are not of the same cardinality. For example, we already know, that |\mathbb{Z}|<|\mathbb{R}|.

Sets of different cardinalities

We already know, that some sets are countable — of the same cardinality as \mathbb{N}. We will say that such sets have cardinality \aleph_0 (aleph zero) — understanding this as the lowest possible infinite cardinal number. We know that not all sets are countable and there exist “bigger” sets, e.g. \mathbb{R}. We shall say that a set af the same cardinality as the set of real numbers is of cardinality \mathfrak{c} — (continuum). Generally Cantor Theorem states, that for any set A, |A|<|\mathcal{P}(A)|. We see immediately that it we can have an infinite sequence of sets of increasing cardinalities:

    \[|\mathbb{N}|< |\mathcal{P}(\mathbb{N})|<|\mathcal{P}\left(\mathcal{P}(\mathbb{N})\right)|<|\mathcal{P}\left(\mathcal{P}\left(\mathcal{P}(\mathbb{N})\right)\right)|<\ldots\]

We also know that |\mathcal{P}(\mathbb{N})|=\mathfrak{c}. Therefore, it makes sense to ask, whether there exists a set of cardinality in between \aleph_0 and \mathfrak{c}, or whether \mathfrak{c} is the lowest possible cardinal number greater than \aleph_0? In other words if we enumerate the lowest possible infinite cardinalities as: \aleph_0,\aleph_1, \aleph_2, \ldots, then whether \aleph_1=\mathfrak{c}? This question is called the Continuum Hypothesis and was enlisted by David Hilbert on the Congress of Mathematicians in Paris in 1900 r as the first of 20 most important open problems which have to be solved during next 100 years.

An it has been solved in the 60-ties. But the answer may seem very unconventional. Combining results of Kurt Goedel and Paul Cohen we know that: assuming that the axioms of mathematics are consistent it is not possible to prove the Continuum Hypothesis and it is not possible to prove its negation! It actually has been proven that it is impossible to prove. It turned out that it is possible that a sentence is independent from the axioms.

By the way, notice the assumption of consistency of the axioms. Is such consistency not obvious? Actually it is not. Kurt Goedel proved that it also cannot be proven! We will never know, that the axioms are for sure consistent. But this does not diminish our faith in mathematics. 🙂

Sets of cardinality continuum

Returning to the ground, we have already mentioned some sets of cardinality continuum, in particular: \mathbb{R} and \mathcal{P}(\mathbb{N}). It is relatively easy to prove that also the set of infinite binary sequences \{0,1\}^{\mathbb{N}} is also of cardinality continuum as is also the set of all infinite sequences of natural numbers \mathbb{N}^{\mathbb{N}}. Also the product of two sets (or even countably many) sets of cardinality continuum is of cardinality continuum.

I hope it is not necessary to mention that there are sets of cardinality greater than continuum. E.g. by Cantor Theorem, |\mathcal{P}(\mathbb{R})|>|\mathbb{R}|.

Usually we will prove that a set X is of cardinality continuum, using Cantor-Bernstein Theorem. In particular we have to find sets A i B, of cardinality continuum, such that we are able to show functions which prove that |A|\leq |X| and |X|\leq |B|.

E.g. let us prove that the set P^{\mathbb{N}} of all infinite sequences of even numbers P is a set of cardinality continuum. Take the set of all sequences of natural numbers. Then f\colon P^{\mathbb{N}}\to \mathbb{N}^{\mathbb{N}}, f((x_n))=(x_n) is obviously one-to-one, so |P^{\mathbb{N}}|\leq |\mathbb{N}^{\mathbb{N}}|=\mathfrak{c}. On the other hand, g\colon \{0,1\}^{\mathbb{N}}\to P^{\mathbb{N}}, let be a the function which in a given binary sequence changes all ones into twos. g is again one-to-one, so \mathfrak{c}=|\{0,1\}^{\mathbb{N}}|\leq| P^{\mathbb{N}}|. Therefore by Cantor-Bernstein Theorem |P^{\mathbb{N}}|=\mathfrak{c}.

Diagonal method

Diagonal method is a method of proving theorems quite popular in mathematics. For example, we can use it to prove Cantor Theorem for the set of natural numbers, in other words, that |\mathcal{P}(\mathbb{N})|>|\mathbb{N}|, the set of all subsets of the set of natural numbers cannot be accommodated in Hilbert’s hotel.

Assume otherwise, that it is possible. Let \mathcal{P}(\mathbb{N})=\{A_0, A_1, A_2, A_3,\ldots\}, where A_n is the set accommodated in the n-th room. We construct new subset B of natural numbers in the following way: if 0\in A_0, then let 0\notin B, and if 0\notin A_0, then let 0\in B. And similarly let 1\in B if and only if 1\notin A_1, generally let n\in B if and only if n\notin B_n (that is what is the motivation of the name of this method: we take or not number n as an element of B, depending on whether it is not or is element of A_n).

Notice, that B\neq A_0, because only one of them contains 0. Similarly, B\neq A_1 because they differ on 1. Generally B\neq A_n. Therefore B is a subset of the set of natural numbers, which is not accommodated in any room. We have reached a contradiction, because we assumed that every subset is accommodated.