We shall say that the cardinality of is not greater than the cardinality of (denoted by ) if there exists a 1-1 function .
We say that the cardinality of is not less than the cardinality (denoted by ) if there exists an ,,onto” function .
E.g. , because is a function from onto .
The Theorem of Cantor-Bernstein, states that if and , then the sets and have the same cardinality (so if there exist , such that is 1–1 and is onto then there is a bijection ).
We shall write that , if , but and are not of the same cardinality. For example, we already know, that .
Sets of different cardinalities
We already know, that some sets are countable — of the same cardinality as . We will say that such sets have cardinality (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. . We shall say that a set af the same cardinality as the set of real numbers is of cardinality — (continuum). Generally Cantor Theorem states, that for any set , . We see immediately that it we can have an infinite sequence of sets of increasing cardinalities:
We also know that . Therefore, it makes sense to ask, whether there exists a set of cardinality in between and , or whether is the lowest possible cardinal number greater than ? In other words if we enumerate the lowest possible infinite cardinalities as: , then whether ? 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: and . It is relatively easy to prove that also the set of infinite binary sequences is also of cardinality continuum as is also the set of all infinite sequences of natural numbers . 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, .
Usually we will prove that a set is of cardinality continuum, using Cantor-Bernstein Theorem. In particular we have to find sets i , of cardinality continuum, such that we are able to show functions which prove that and .
E.g. let us prove that the set of all infinite sequences of even numbers is a set of cardinality continuum. Take the set of all sequences of natural numbers. Then , is obviously one-to-one, so . On the other hand, , let be a the function which in a given binary sequence changes all ones into twos. is again one-to-one, so . Therefore by Cantor-Bernstein Theorem .
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 , 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 , where is the set accommodated in the -th room. We construct new subset of natural numbers in the following way: if , then let , and if , then let . And similarly let if and only if , generally let if and only if (that is what is the motivation of the name of this method: we take or not number as an element of , depending on whether it is not or is element of ).
Notice, that , because only one of them contains . Similarly, because they differ on . Generally . Therefore 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.