# Does Cantor's Diagonal Lemma Contradict the Usual Method of Defining a Bijection Between Two Intervals?

I've seen a lot of questions like the following:

Show there is a bijection from $(0,1]$ to $(0,1)$.

The bijections I've been using in my answers to this question have involved numerating the sequence of real numbers between zero and one:

$(r_\alpha)_{\alpha \in \mathbb{N}}$

Then I use the Hilbert Hotel method of simply shifting the initial values in that sequence by the number of end points opening or closing on the interval:

If the current input to the bijection equals one, shift the entire sequence $(r_\alpha)_{\alpha \in \mathbb{N}}$ right one index and make the current input the first object in the sequence $(r_\alpha)_{\alpha \in \mathbb{N}}$.

Similarly as in this proof.

The issue I'm having with this proof is Cantor's Diagonal Lemma. My understanding is that Cantor's Diagonal Lemma proves that the real numbers in any interval cannot be mapped to $\mathbb{N}$. If this is correct, then we cannot define the sequence of reals between $(0,1)$ as $(r_\alpha)_{\alpha \in \mathbb{N}}$.

Is there some flaw in my understanding above? It seems to me that Cantor's Diagonal Lemma makes it so that Hilbert's Hotel can't accommodate another, single guest if the hotel is already full.

• Possible duplicate of How to define a bijection between $(0,1)$ and $(0,1]$? – Apostolos Apr 14 '17 at 23:43
• I'm not looking for a definition of how to define a bijection between two intervals. I'm asking if Cantor's Diagonal Lemma contradicts the usual method of defining such a bijection. – StudentsTea Apr 14 '17 at 23:48
• "I'm asking if Cantor's Diagonal Lemma contradicts the usual method of defining such a bijection" It does not. "this question have involved numerating the sequence of real numbers between zero and one" Not in a million years... "Cantor's Diagonal Lemma proves that the real numbers in any interval cannot be mapped to $\mathbb{N}$" Well, they could, but not injectively. "If this is correct, then we cannot define the sequence of reals between $(0,1)$ as $(r_\alpha)_{\alpha \in \mathbb{N}}$" Huh? Sure we cannot and as a matter of fact nobody does that here. – Did Apr 15 '17 at 21:58

## 1 Answer

Cantor's theorem proves that there does not exist a sequence $(r_n)_{n\in\mathbb{N}}$ such that it enumerates all the reals, but the Hotel with as many rooms as the real numbers between $0$ and $1$ we can still accommodate one extra guest because the hotel has at least countable many rooms. To give a concrete example, if we have rooms with with numbers $r\in(0,1)$ then we have rooms $$\frac{1}{2},\ \frac{1}{3},\ \frac{1}{4},\ \ldots,\ \frac{1}{n},\ \ldots$$ so the manager of the hotel can move the guest in room $\frac{1}{2}$ to room $\frac{1}{3}$, he guest in room $\frac{1}{3}$ to room $\frac{1}{4}$ and so on, and thus room $\frac{1}{2}$ will be left empty for the new guest.

In fact since we have $\mathbb{R}$ many rooms, even if the hotel is full we can accommodate $\mathbb{R}$ many people, by sending the guest of room $r$ to room $\frac{r}{2}$ and then accommodate the guest that was staying in room $0$ (that is one extra guest) as I described in the paragraph above.

• @StudentsTea No, the answer there does exactly what I do in my example, though instead of picking a specific sequence (I picked $(\frac{1}{n+1})_{n\in\mathbb{N}}$) they pick an arbitrary sequence. The point is that there exists a countable sequence in the reals, rather than all the reals can be put in a sequence. – Apostolos Apr 15 '17 at 0:08
• @StudentsTea Cantor's theorem says that there does not exist a way to enumerate all the real numbers. Not that we cannot find an infinite countable sequence of real numbers. So for example, whichever sequence of reals you create Cantor's theorem tells me that there exists real numbers not in that sequence. – Apostolos Apr 15 '17 at 0:09
• @StudentsTea Where's the problem in that? We enumerate a countable subset $X$ of $(0,1)$, and we define a bijection $(0,1] \to (0,1)$ using that subset. Everything in $Y := (0,1)\setminus X$ remains unmoved. Cantor's argument just shows that $Y$ is not empty, whichever countable subset $X$ we choose. – Daniel Fischer Apr 15 '17 at 22:36
• @StudentsTea Yes, we cannot enumerate all the reals, but this does not mean that we cannot enumerate some of the reals. In the example in my answer, we don't enumerate all the reals. For example $\frac{2}{3}$ is not in my sequence. This doesn't matter. As long as we have a sequence of some reals then we can make space for 1 more guest. See also Daniel's great comment. – Apostolos Apr 16 '17 at 1:52
• @StudentsTea There exist transfinite sequences. You could say that a sequence is related with the notion of a well-order which generalise the order of natural numbers. A well total order on a set $X$ is an order such that every subset of $X$ has a least element in the order. Using the axiom of choice we can show that every set can be well-ordered and hence written as a transfinite sequence. But without the axiom of choice we cannot show that there exists a transfinite sequence of all the reals. Here are some wiki articles: tinyurl.com/cjn85bc and tinyurl.com/ocn742a – Apostolos Apr 18 '17 at 21:36