In 1891, Cantor proved, using the now-famous diagonal argument, that the real numbers are uncountable, i.e. they cannot be put in one-to-one correspondance with the natural numbers. Furthermore, we know that the open interval (0,1) and the real line have the same cardinality (if we define f : (0,1) -> by

we have a bijection). Since [0,1]\(0,1)={0,1}, it is legitimate to think that the closed and open unit intervals have the same cardinality as well. But can we find a bijection from to [0,1]? In this post, I answer this question by constructing a function with the desired properties. (In the following, card(X) is the cardinality of the set X.)

1. Existential question

First of all, it will be helpful to know if such a bijection exists before trying to construct one. We state the following lemma without proof :

Lemma 1.1

Let X,Y be sets. If there is an injection f : X -> Y, then card(X) Y.

We then note that there exists a “canonical” injection f of [0,1] in , namely f(x)=x. Moreover, if we define g : -> [0,1] by , we can see that g is in fact injective. Using the previous lemma, the function f tells us that card([0,1]) card(), whereas the function g tells us that card() card([0,1]). To conclude that both sets have the same cardinality, we need the following theorem.

Theorem 1.2 (Bernstein-Schröder)

Let X,Y be sets. If there exist injections i : X -> Y and j : Y -> X, then there is a bijection f : X -> Y.

The previous theorem thus confirms that there exists a bijection from to [0,1].

2. Construction of the bijection

Recall the two injections we defined earlier:

.

We define the following sets and . Finally, we define another set, namely . Now, we define the following function :

We claim that this function is a bijection from the real line to the closed unit interval.

- Consider any
*b*∈*[0,1]*. If*b*∈*g(**C*), then there is an*a*∈*C*with*b*=*g*(*a*). Hence*b*=*h*(*a*) by the definition of*h*. If*b*is not in*g(**C)*, define*a*=*f*(*b*). By definition of*C*_{0},*a*cannot be in*C*_{0}. Since*g*[*C*_{n}] is a subset of*g*[*C*], it follows that*b*is not in any*g*[*C*_{n}], hence*a*=*f*(*b*) is not in any*C*_{n+1}=*f(**g(**C*_{n}) by the recursive definition of these sets. Therefore,*a*is not in*C*. Then*b*=f*a*) =*h*(*a*) by the definition of*h*. - Since
*g*is injective on , which contains*C*, and f is injective on*f*(), which contains the complement of*C*, it suffices to show that the assumption*g*(*c*) = f(*a*) for*c*∈*C*and*a*∈ \*C*leads to a contradiction. Since*c*∈*C*, there exists an integer*n*≥ 0 such that*c*∈*C*_{n}. Hence*f*(*g*(*c*)) is in*C*_{n+1}and therefore in*C*, too. However,*f*(*g*(*c*)) =*f*(*f*(*a*)) =*a*is not in*C*— contradiction.

Since h is both surjective and injective, we conclude that it is a bijection; therefore, and [0,1] have the same cardinality.

3. Conclusion

This function is not really practical for computation, i.e. there is no efficient way to know if a given x is in C or not. But can we get a “nicer” formula? It is highly improbable. For example, if h were a continuous function (in the usual analytical sense), then it would mean that the real line is compact, which is absurd. Anyway, cheers.

## Leave a comment

Comments feed for this article