6
$\begingroup$

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;     else         return x * 2 - 1; }  function naturalToReal(x) {     if(x == 0)         return 0;     if(x % 2 == 0)         return x / 2 * -1;     else         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.

  • 0
    @DejanGovc Thanks, I'm slow but now I think I've got it! :)2012-04-13

3 Answers 3

24

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.

  • 1
    If natural numbers are `infinite`, would it ever run out mapping the real numbers?2014-02-07
4

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

  • 0
    I completel$y$ forgot about these, sorry.2012-04-12
4

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.

  • 0
    Thanks, the power set was new to me. I'm kind of rediscovering math after hating it at school :)2012-04-12