# How can adding new numbers overflow $\mathbb{N}$ in Cantor's diagonal argument?

I've been thinking and asking around about this for a while. So I think Cantor's diagonal argument basically said that you can find one new number for every attempted bijection from $\mathbb{N}$ to $\mathbb{R}$. But at the same time, Hilbert's Hotel idea said that we can always accommodate new room even when the hotel of infinite room is full. So I was wondering why can't we do the same thing for the bijection from $\mathbb{N}$ to $\mathbb{R}$, adding one new equivalence for the new evil number found by Cantor's diagonal argument?

Some people I asked said that: since I already assume $|\mathbb{N}| = |\mathbb{R}|$, when I arrive at a contradction, I shall stop there and say $|\mathbb{N}| \ne |\mathbb{R}|$. But my argument is that we don't do that when we analyze Liar's Paradox do we? When we assume the sentence is true and then arrive at the contradiction, we don't stop and say that it's false. We start from that conclusion again and arrive at yet another contradiction and found that it's true, right?

Some people also said that Hilber's Hotel idea is naught but a fable that can't be formulate into mathematical argument. So here's one my attempt on that. I start with Cantor's argument (assume $|\mathbb{N}| = |\mathbb{R}|$ and then show $|\mathbb{N}| \ne |\mathbb{R}|$), and from then I show that $|\mathbb{N}| = |\mathbb{R}|$ again. Well, it's not really Hilbert's Hotel, but the idea is the same: that $\mathbb{N}$ can accommodate countably many more "new evil numbers" will result in $|\mathbb{N}|=|\mathbb{R}|$. The idea is simple but I think we can only find the mistake when we formularize it. But I have yet found an unpatchable mistake, so I hope someone can plow through all the jargon and find out where I'm wrong. Also I'm only a student majoring in a nearby field (Physics), so yeah, I don't have a lot of experience or many experience people around; thus mistakes are inevitable. Thank you for your time!

Theorem 1: $|\mathbb{N}| \neq |\mathbb{R}|$ (It's just Cantor's argument)

Proof:

Let $O = \left\{ 1,3,5,7,... \right\}$ be the set of odd integers. Assume $|O| = |\mathbb{R}|$, and let $f$ be an arbitrary bijection from $O$ to $\mathbb{R}$. We create an enumeration of elements from $O$ to $\mathbb{R}$ (I took this from Wikipedia):

$f(1)\ =( \underline{1},1,1,1,1,1,1 , \dots )\\ f(3)\ = ( 0,\underline{0},0,0,0,0,0 , \dots ) \\ f(5)\ = ( 1,0,\underline{1},0,1,0,1 , \dots )\\ f(7)\ = ( 0,1,0,\underline{1},0,1,0 , \dots )\\ f(9)\ = (1,1,0,1,\underline{0},1,0 , \dots )\\ f(11)=(0,0,1,0,1,\underline{0},1, \dots)\\ f(13) = (1,0,0,1,0,1,\underline{0}, \dots) \\ \dots$

Let the function $g: \mathbb{R}^{|\mathbb{N}|} \rightarrow \mathbb{R}$: $g(...)= \begin{cases} g_0=g(f(1),f(3),f(5),...)= \text{interweave orderly all the complements} \\ \text{ of the } (\frac{i-1}{2}+1)^{th} \text{ digit of f(i)}\\ g_n=g(f(1),f(3),f(5),..., g_0, g_1, g_2, ..., g_{n-1})= \text{above, but if the } \\ \text{argument is not } f(i) \text{ then take } \text{the complements of the } i^{th} \text{ digit of the } i^{th} \\ \text{argument and put it on the } i^{th} \text{ position} \end{cases}$

So $g_0$ is the evil "new number" created from the enumeration of $f(i)$, and $g_1$ is the evil number created from the enumeration of $f(i)$ merge with $g_0$ at the end, and $g_2$ is the evil number created from the enumeration of $f(i)$ merge with $g_0$ and $g_1$ at the end, so on so forth. I think (I'm not sure) this generalize Cantor's idea: "if you give me any listing, I can give you a new number off the list."

We found that $g_0$ is different than all $f(i)\ \forall \ i \in \mathbb{N}$ while $g_0 \in \mathbb{R}$, thus $\nexists f^{-1}(g_0)$ and $f$ can't be a bijection from $O \rightarrow \mathbb{R}$. This conclude Cantor's proof. $\square$

Theorem 2: Let $G=\left\{g_0, g_1, g_2, \dots \right\}$ be the codomain of the $g$ function as described above. Then $|\mathbb{N}|=|\mathbb{R}|$

Proof:

Assume $f$ bijects $O \rightarrow \mathbb{R} \text{ \ } G$ (it's not $f$ from theorem 1, but it still creates the same $g$). Let $E = \left\{ 0,2,4,6,8,... \right\}$ be the set of even integers. Define a function $h:E \rightarrow G$ so that:

$h(0) = g(f(1),f(3),f(5),...)=g_0 \\ h(2) = g(f(1),f(3),f(5),..., \ g(f(1),f(3),f(5),...))=g_1\\ h(4) = g(f(1),f(3),f(5),...,\ g(f(1),f(3),f(5),...)\ ,g(f(1),f(3),f(5),..., \ g(f(1),f(3),f(5),...)))=g_2\\ \dots$

For clarity replace $f(1),f(3),f(5),... = e$ (for evil). We have:

$h(0) = g(e) = g_0\\ h(2) = g(e, \ g(e))=g_1\\ h(4) = g(e,\ g(e)\ ,g(e, \ g(e)))=g_2\\ \dots$

Through construction of $g$, $h(n)$ is different than everything in the bracket of its $g(...)$. Thus

$h(0) \neq f(1),f(3),f(5),... \\ h(2) \neq f(1),f(3),f(5),..., \ g_0= h(0) \\ h(4) \neq f(1),f(3),f(5),..., \ g_0 = h(0), \ g_1=h(2)\\ \dots$

That means $h$ is injective. $h$ is obviously surjective ($h(2k)=g_k$, or we can put them in a array, similar to how we prove $|\mathbb{Q}|=|\mathbb{N}|$. $h$ is therfore bijective from $E \rightarrow G$.

Finally, define a function $T:\mathbb{N} \rightarrow \mathbb{R}$: $T(n)= \begin{cases} f(n)\ \text{if n odds} \\ h(n)\ \text{if n even} \end{cases}$

1. $O \cap E = \emptyset, (\mathbb{R} \text{ \ } G) \cap G = \emptyset$.
2. $f$ bijects $O \rightarrow \mathbb{R} \text{ \ } G$, while $h$ bijects $E \rightarrow G$.

Thus $T = f \cup h$ is a bijection from $O \cup E \rightarrow (\mathbb{R} \text{ \ } G) \cup G$, or $\mathbb{N} \rightarrow \mathbb{R}$. $\square$

Well, technically it's not a proof that $|\mathbb{N}|=|\mathbb{R}|$; rather one with a condition. But the construction of $g$ does not require $f$ to bijects $|\mathbb{N}| \rightarrow |\mathbb{R}|$ or anything from theorem 1 specifically, so it creates a workaround for $|\mathbb{N}|=|\mathbb{R}|$ from Cantor's argument. I think that means if I start with the correct assumption (with $f$ bijects $O \rightarrow \mathbb{R} \text{ \ } G$ rather than $f$ bijects $O \rightarrow \mathbb{R}$, I can arrive at 2 contradicting conclusion. Maybe. I'm not sure.

Thank you again!

• I suspect that if you tried replacing every use of $\ldots$ in your construction with more precise notation, you would find a problem somewhere - as it is, I'm not sure this site will be much use reviewing your idea, since I'm finding it very difficult to figure out what formal operations you're actually doing due to the notation not being that clear. – Milo Brandt Aug 25 '18 at 3:13
• I'm sorry for the confusing notation since I'm not experienced at math... But the $\dots$ are just some sort of iteration, like for example $f(1), f(3), f(5), \dots$ is $f(1), f(3), f(5), f(7), f(9), f(11), \dots$, or $g_0, g_1, g_2, \dots g_{n-1}$ just write from $g_0$ to $g_{n-1}$. – Kim Dong Aug 25 '18 at 3:51

## 1 Answer

Your argument is simply a proof that no bijection $f:O\to\mathbb{R}\setminus G$ exists. Indeed, if it did exist, then you would, as you say, reach a contradiction. So, this is a proof by contradiction that such an $f$ cannot exist.

Contrary to what you say in your second paragraph, a proof by contradiction is the end of the story. Once you've proved something by contradiction, it's proved. That's it. It's just as much proved as if you proved it any other way. As for what's going on in the Liar's Paradox, I recommend you take a look at my answer here. In the Liar's Paradox, we don't keep going after finding that the statement is false because we are not yet certain of that conclusion. The conclusion that the statement is false is 100% correct. The fact that we can also reach a contradiction by assuming that the statement is false is what makes it a paradox. This doesn't mean that our procedure to conclude that the statement was false was wrong or incomplete. (Instead, it just means that we have reached a contradiction, which breaks everything, but that's a separate issue.)

• Yeah, I think this concludes it. I fail to make $g$ well-defined from $f$ bijects $\mathbb{N} \rightarrow \mathbb{R}$. $f$ bijects $\mathbb{N} \rightarrow \mathbb{R} - G$ is just an ad hoc, and it wouldn't work the same... – Kim Dong Aug 25 '18 at 4:14