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$ – Brian M. Scott Apr 12 '12 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 '12 at 7:14
  • 1
    $\begingroup$ @BenjaminLim I cannot say I understood that... but I better not ask, it will fry my poor neurons. $\endgroup$ – Camilo Martin Apr 12 '12 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 '12 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 '12 at 16:15

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$ – Camilo Martin Apr 12 '12 at 7:49
  • 1
    $\begingroup$ If natural numbers are infinite, would it ever run out mapping the real numbers? $\endgroup$ – user33786 Feb 7 '14 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$ – Camilo Martin Apr 12 '12 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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