I'm not a math guy and probably this is a stupid question.

However, I was browsing Wikipedia out of curiosity and I could not understand this one statement:

[...] not all infinite sets have the same cardinality. For example, Georg Cantor (who introduced this branch of mathematics) demonstrated that the real numbers cannot be put into one-to-one correspondence with the natural numbers (non-negative integers), and therefore that the set of real numbers has a greater cardinality than the set of natural numbers.

Now, shortly before this a formula was used to map even integers to odd integers:

n → 2n + 1

Granted we have infinite natural and real numbers, we can devise a formula to map them like so:

0  →  0
1  →  1
2  → -1
3  →  2
4  → -2
5  →  3
6  → -3
7  →  4
8  → -4
9  →  5
10 → -5

As I'm a math analphabet, this is javascript:

​function realToNatural(x) {
    if(x == 0)
        return 0;
    if(x < 0)
        return x * -2;
        return x * 2 - 1;

function naturalToReal(x) {
    if(x == 0)
        return 0;
    if(x % 2 == 0)
        return x / 2 * -1;
        return (x + 1) / 2;

Now, I'm sure there is a hole in my argument, but what is it?

A couple of additional thoughts:

The article mentions the cardinality of the set of odd integers being equal to the one of even integers, and as well equal to the cardinality of all integers, so my confusion is: if this applies to odd and even numbers (being both a "full" infinity instead of "half" infinity) versus the set of both, so it would to natural numbers versus real ones.

Also it states that I just need a function in the form of f : S to make a set countable.

  • 11
    $\begingroup$ You have a bijection between the natural numbers and the integers, not between the natural numbers and the real numbers. The real numbers include $\frac12,\pi,\sqrt2$, etc. $\endgroup$ Apr 12, 2012 at 7:11
  • 5
    $\begingroup$ I think you are misunderstanding what a real number is. Your mapping is to the integers Z (the positive and negative whole numbers + 0). A real number is (roughly) any number that can be written as a decimal with possibly infinite digits after the decimal point (the actual definition is more technical). $\endgroup$
    – Chris Card
    Apr 12, 2012 at 7:14
  • 1
    $\begingroup$ @BenjaminLim I cannot say I understood that... but I better not ask, it will fry my poor neurons. $\endgroup$ Apr 12, 2012 at 8:00
  • 1
    $\begingroup$ @CamiloMartin: What Benjamin Lim wrote, is basically just the set of all subsets of $\mathbb N$, a.k.a. the power set of $\mathbb N$. This set has the same cardinality as $\mathbb R$, which means strictly bigger than that of $\mathbb N$. $\endgroup$
    – Dejan Govc
    Apr 12, 2012 at 11:38
  • 1
    $\begingroup$ @CamiloMartin: There is an injective map $\mathbb N\to\mathbb R$, but there is no injective map $\mathbb R\to\mathbb N$. $\endgroup$
    – Dejan Govc
    Apr 13, 2012 at 16:15

3 Answers 3


You have a bijection between the natural numbers and the integers, not between the natural numbers and the real numbers. The real numbers include $\frac12,\pi,\sqrt2$, etc. The first of these, $\frac12$, is a rational number; the last two are not.

There are bijections between $\Bbb Q$, the set of rational numbers, and $\Bbb N$, the set of natural numbers, but $\Bbb R$, the set of real numbers, is too big: one can prove that any function mapping $\Bbb N$ to $\Bbb R$ will miss some real numbers, and any function mapping $\Bbb R$ to $\Bbb N$ will hit some natural number infinitely many times.

  • $\begingroup$ What can I say, stupid me. Your explanation makes it very clear now. $\endgroup$ Apr 12, 2012 at 7:49
  • 2
    $\begingroup$ If natural numbers are infinite, would it ever run out mapping the real numbers? $\endgroup$
    – user33786
    Feb 7, 2014 at 13:20

How does your method deal with irrational numbers, ie $\sqrt{2}$ or $\pi$ or $e$? Your realToNatural function doesn't send these to integers.

  • $\begingroup$ I completely forgot about these, sorry. $\endgroup$ Apr 12, 2012 at 7:52

As Brian and KReiser pointed out, you wrote down a bijection between natural numbers and integers. The real numbers are a lot more tricky.

It is however relatively easy to see that there is no bijection from the natural numbers (or any set, for that matter) to their power set. For further reading, I refer to Cantor's theorem. ;)

Moreover, a set $S$ is countable if there exists an injective function $f : S \rightarrow \mathbb{N}$. An arbitrary function does not suffice.

  • 1
    $\begingroup$ Thanks, the power set was new to me. I'm kind of rediscovering math after hating it at school :) $\endgroup$ Apr 12, 2012 at 7:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .