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 bg(C), then there is an a ∈ C with b = g(a). Hence bh(a) by the definition of h. If b is not in g(C), define a = f(b). By definition of C0, a cannot be in C0. Since g[Cn] is a subset of g[C], it follows that b is not in any g[Cn], hence a = f(b) is not in any Cn+1 = f(g(Cn) 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 aC leads to a contradiction. Since c ∈ C, there exists an integer n ≥ 0 such that c ∈ Cn. Hence f(g(c)) is in Cn+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.

About these ads