Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 example show that:

$|\mathbb{N}|= | \mathbb{N} \cup \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} \cup \lbrace \sqrt{2},\sqrt{3} \rbrace |$?


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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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)$.

share|cite|improve this answer
This is indeed what I meant (I've corrected the post). Thanks ! – Jecimi Oct 13 '13 at 19:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.