4. Comparing cardinalities of sets

Part 1: problems, solutions.
Part 2.: problems, solutions.

Images and preimages

Given a function f\colon X\to Y, and A\subseteq X — a subset of domain, then the set of all possible values given by f on arguments from A, will be called the image A under f and is denoted by f[A]. So:

    \[f[A]=\{y\in Y\colon \exists_{a\in A} f(a)=y.\}\]

Given a subset of the set of values B\subseteq Y, the sets of all arguments such that their values are in B, is called the preimage of B under f and we denote it as f^{-1}[B]. So:

    \[f^{-1}[B]=\{x\in X\colon f(x)\in B\}.\]

Examples

Let f\colon\mathbb{N}\to\mathbb{N}, f(n)=2n. Then f[\mathbb{N}] is the set of all even numbers. If A is the set of even numbers, then f[A] is the set of all natural numbers divisible by 4. If B is the set of odd numbers, then f^{-1}[B]=\varnothing. On the other hand, f^{-1}[\{4n\colon n\in\mathbb{N}\}] is the set of even numbers.

Let now g\colon \mathbb{R}\to\mathbb{R}, g(x)=x^2. Then g[(-3,2)]=[0,9). On the other hand, g^{-1}[(-\infty,0)]=\varnothing, and g^{-1}[(-2,9)]=[0,3).

Let now h\colon \mathbb{R}^2\to\mathbb{R}, h(x,y)=xy. Then g[(-3,2)\times (-1,2]]=g[(-3,0)\times (-1,0)]\cup g[(-3,0)\times [0,2]]\cup g[[0,2)\times (-1,0)]\cup g[[0,2)\times [0,2]]=(0,3)\cup (-6,0]\cup (-2,0]\cup [0,4)=(-6,4). And g^{-1}[(-\infty,0)]=\{\left<x,y\right>\in\mathbb{R}^2\colon (x<0\land y>0)\lor (x>0\land y<0)\}.

Let finally F\colon \mathbb{R}\to\mathbb{R}^2, F(x)=\left<2x,x\right>. Therefore, F[\mathbb{R}]=\right\{\left<a,b\right>\in\mathbb{R}^2\colon b=\frac{a}{2}\left\}, so it is the line y=\frac{x}{2}. On the other hand, F^{-1}[(1,\infty)\times (1,\infty)]=\left(\frac{1}{2},\infty\right)\cap (1,\infty)=(1,\infty).

Hilbert’s hotel

Imagine a hotel with some number, e.g. five, single rooms. Assume that all the rooms are occupied. So if a new guest arrives, receptionist has to tell him that no room is available.

But what will happen if the hotel is infinite? Infinitely many rooms numbered 0, 1, 2, etc. single rooms (we will call such a hotel Hilbert’s hotel) and all those rooms are taken, and a new guest appears. Should the receptionist tell him that there are no free rooms? Wise receptionist do not have to. But if not he has to disturb all the guests: he can ask all the guests to step out to the corridor and move to the room with a number greater by one. From 0 to 1, from 1 to 2, from 2 to 3, and so on. All the guests will get a new room and the room 0 will stay free and can be given to the new guest! So Hilbert’s hotel can actually accommodate one more guest then the number of guest that can fill the whole hotel.

And what will happen if to an empty Hibert’s hotel arrive an infinite group of men and and infinite group of women? If the receptionist accommodates the women first, they will take all the rooms, and there will be no rooms for men. Wise receptionist will accommodate women and men alternately. Women to the rooms with even numbers and men to the rooms with odd numbers and therefore all people will fit in. Therefore Hilbert’s hotel can accommodate twice as many people as can fill the whole Hilbert’s hotel!

Sets of the same cardinality

How to check that two sets have the same number of elements? E.g. a set of some women and a set of some men. We can count elements in each of the sets. But there is also a second method. It suffices to match elements of both sets into pairs. If it is possible, the two sets have the same number of elements. This is a very nice method, since it can be also applied to infinite sets. In the language we have developed, matching elements into pairs, means finding a bijection (function onto and 1-1) between those sets.

We will say that sets A and B are of the same cardinality, if there exists a bijection between them. This fact will be denoted by |A|=|B|.

Examples

The above considerings about Hilbert’s hotel, were actually considering whether the set of rooms and the set of guests are of the same cardinality. In the first case we have actually considered the following bijection between the sets of guests (actually \mathbb{N}\cup \{-1\} — the additional guest will be denoted here as -1) and the set of rooms (enumerated with elements of \mathbb{N}): f(x)=x+1.

In the second case (with women and men) we can think about a bijection between integer numbers \mathbb{Z} (non-negative numbers are men, and negative — women) with set \mathbb{N} (rooms). This bijection is defined as follows:

    \[g(z)=\begin{cases} -2z & \text{for }z<0\\ 2z+1 & \text{for }z\geq 0 \end{cases}\]

One more example. Let us find a bijection between [0,1] and [0,1). It is not very straightforward, we will need a set A=\{\frac{1}{n}\colon n\in\mathbb{N}, n>0\}, which will help us construct an appropriate bijection:

    \[h(x)=\begin{cases} \frac{1}{n+1} & \text{for } x=\frac{1}{n},n\in\mathbb{N}, n>0$\\ x & \text{for } x\in [0,1]\setminus A \end{cases}\]

Are all infinite sets of the same cardinality?

So maybe all infinite sets are of the same cardinality and we do things without any sense? No! Not all infinite sets have the same cardinality. For example \mathbb{N} and \mathbb{R}. Let us give some arguments why real numbers, even only those in the interval [0,1], cannot be accommodated in Hilbert’s hotel, in other words there does not exist a bijection f\colon \N\to [0,1].

Assume otherwise, that such a bijection exists, so every point on the interval can be accommodated into Hilbert’s hotel, so [0,1]=\{x_0, x_1, x_2,\ldots\}, where f(n)=x_n. Now let us divide [0,1] into three intervals [0,\frac{1}{3}], [\frac{1}{3},\frac{2}{3}], [\frac{2}{3},1]. Choose this interval out of the three, which does not include x_0. We divide the chosen interval into three parts and we choose the one that does not include x_1. Again, we divide the chosen interval into three parts and choose those which does not include x_2 and so on. In the effect we will find a point which in not equal to x_0, not equal to x_1, not equal to x_2, and so on. Therefore it is not accommodated in Hilbert’s hotel, which is a contradiction, because we have assumed that all the points are accommodated.

Countable sets

A set of the same cardinality as the set of natural numbers will be called countable (so a set is countable if its elements can be accommodated in Hilbert’s hotel). You can think about countable sets as of class of the ,,smallest” infinite sets. In particular, every infinite subset of a countable set is countable (it is easy to see that every subset of a set which can be accommodated in Hilbert’s hotel can be accommodated in Hilbert’s hotel).

Therefore we say that a set is at most countable if it is finite or countable.

Examples of countable sets

We have already proved that the set of integer numbers \mathbb{Z} is countable.

Notice that, although it may be surprising in the beginning, that the set \mathbb{N}\times\mathbb{N} of pairs of natural numbers is countable. Indeed, we can enumerate them with natural numbers (or in other words we can accommodate them in Hilbert’s hotel), enumerating the subsequent pairs in order of the sum of their elements: \left<0,0\right>, \left<1,0\right>, \left<0,1\right>, \left<2,0\right>, \left<1,1\right>, \left<0,2\right>, \left<3,0\right>, \left<2,1\right>, \ldots.

Secondly, notice that the set of all finite sequences of zeros and ones: \{0,1\}^{*} is also countable. We can enumerate its elements taking them in order of their length.

Similarly the set of all finite subsets of the set of natural numbers \mathcal{P}_{fin}(\mathbb{N}) is countable — we can enumerate them taking them in order of maximal element.

So:

    \[|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=|\mathbb{N}\times\mathbb{N}|=|\{0,1\}^{*}|=|\mathcal{P}_{fin}(\mathbb{N})|.\]

Properties of countable sets

From the above you can see that:

  • infinite subset of a countable set is countable
  • product of two countable sets is countable
  • product of finite number of countable sets is countable
  • countable sum of countable sets is countable

We can use the above facts to prove that a given set is countable.

Functions and countability

The following theorems are relatively intuitive:

  • If f\colon A\to B is onto and A is countable, then also B is at most countable.
  • If f\colon A\to B is 1-1 and B is countable, then also A is at most countable.

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.

This is actually equivalent to existence of an ,,onto” function f\colon B\to A.

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 cardinality

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 of 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 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.

And 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 has actually 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 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, an 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.