# Proove formally that |N| = | N union a finite set |.

I'd like to show that the cardinality of $\mathbb{N}$ is the same as the cardinality of $\mathbb{N}$ union some other finite set (disjoint from $\mathbb{N}$) For e.g show that :

$|\mathbb{N}|= | \mathbb{N} \bigcup \lbrace \sqrt{2},\sqrt{3} \rbrace |$

To prove these two terms have the same cardinality, we must find a bijection from one term to the other.

I think we can prove it using the Hilbert's Grand Hotel paradox, i.e making two new "free places" for the two values $\sqrt{2},\sqrt{3}$ by adding 2 to the other elements. The bijection would be $\theta(x)$ such that :

$\theta(x) = \cases{ 2+f(x) & for$x\ge2 $\\ \sqrt{2} & for$x=0 $\\ \sqrt{3} & for$x=1 $\\ }$

with $f(x)= x$ for $x\in\mathbb{N}$

Is $\theta(x)$ well defined ? How to show formally that $\theta(x)$ is a bijection ? And does it prove formally that $|\mathbb{N}|= | \mathbb{N} \bigcup \lbrace \sqrt{2},\sqrt{3} \rbrace |$ ?

Thanks

Edit : As Asaf Karagila pointed out, the right definition for $\theta(x)$ is

$\theta(x) = \cases{ x-2 & for$x\ge2 $\\ \sqrt{2} & for$x=0 $\\ \sqrt{3} & for$x=1 $\\ }$

for $x\in\mathbb{N}$

To show it is a bijection see the explanation of the accepted answer.

-
If $f(x)=x$, then why not just write $x$ instead of $f(x)$? And where does the $f(0)=\sqrt2$ come from? – Carsten S Oct 13 '13 at 19:19
Oh, I forget: Your basic idea is the right one. – Carsten S Oct 13 '13 at 19:20
Sorry, you're right, I've made mistakes. I corrected the post to what I meant. – Jecimi Oct 13 '13 at 19:26
Now you have $(\theta(0),\theta(1),\theta(2),\theta(3),\ldots)=(\sqrt 2,\sqrt 3,4,5,\ldots)$, probably not what you want. (Now I see, an answer has already addressed this.) – Carsten S Oct 13 '13 at 20:12
Yes indeed,this is what Asaf Karagila pointed out. This where my reasoning was false. – Jecimi Oct 13 '13 at 20:40

Yes, you need to argue why this is a well-defined function, and that it is a bijection; or at least an injection (in which case you will have to use the Cantor-Bernstein theorem).

To claim that it is well-defined you have to show that given $x$ there is only one "output" that the definition you have given can end up with; that this output is in the wanted codomain; and that every natural number appears in the domain of the function. But indeed either $x=0$ or $x=1$ or $x\geq 2$. And clearly $\theta(x)$ is in $\Bbb N\cup\{\sqrt2,\sqrt3\}$.

To show that it is a bijection you need to verify that the function is both injective and surjective. So you need to show that if $x\neq y$ then $\theta(x)\neq\theta(y)$. You have some cases to check, if $x=0$ and $y=1$; if $x,y\geq2$ and so on.

To show that it is surjective you need to show that given $y\in\Bbb N\cup\{\sqrt2,\sqrt3\}$ you can find $x\in\Bbb N$ such that $\theta(x)=y$. Here you have a slight problem, that you need to take $x-2$ rather than $2+x$. But apart of this, it should be fine.

And finally, how does that show the wanted conclusion holds? Well, $|A|=|B|$ if there is a bijection $f\colon A\to B$. Since you have written down such a bijection, it finishes the proof.

-
Thanks for your detailed explanation, and indeed it is x-2 rather than x+2. – Jecimi Oct 13 '13 at 19:38

Your usage of an auxiliary function $f$ is bizarre and unnecessary. You contradict yourself as well - you say $f(0)=\sqrt2$ and then $(\forall x\in\Bbb N) f(x)=x$. I think what you meant was simply:

$$\begin{cases} \theta(0)=\sqrt2\\\\ \theta(1)=\sqrt3\\\\ \theta(x)=x+2&\text{for x\geq2} \end{cases}$$

This is certainly well defined, which just means that for any $x$, there's only one possible value for $\theta(x)$.

-
This is indeed what I meant (I've corrected the post). Thanks ! – Jecimi Oct 13 '13 at 19:33