5
$\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.

  • 11
    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.2012-04-12
  • 5
    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).2012-04-12
  • 0
    There is not even a surjective function from $\Bbb{N}$ into the set $X^{\omega}$ where $X=\{0,1\}$.2012-04-12
  • 0
    @ChrisCard That was indeed the case. Sorry for the dumb question.2012-04-12
  • 1
    @BenjaminLim I cannot say I understood that... but I better not ask, it will fry my poor neurons.2012-04-12
  • 1
    @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$.2012-04-12
  • 0
    @DejanGovc Ah, I see, meaning that the power set of ℕ is as infinitely divisible as ℝ is, right? So we can't even write a function that maps one-way?2012-04-12
  • 1
    @CamiloMartin: There is an injective map $\mathbb N\to\mathbb R$, but there is no injective map $\mathbb R\to\mathbb N$.2012-04-13
  • 0
    @DejanGovc Thanks, I'm slow but now I think I've got it! :)2012-04-13

3 Answers 3

23

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.

  • 0
    What can I say, stupid me. Your explanation makes it very clear now.2012-04-12
  • 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 completely 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