Comment by jonreem | Hacker News Reader

Comment by jonreem | Hacker News Reader

Parent Full thread

A set being "countably infinite" only means that you can write a function that maps each distinct entry in the set to exactly one natural number (0, 1, 2, etc.) without duplicates. That's it.

So for example, the set of natural numbers is countably infinite and we know this because we can write a function that maps each natural number to exactly one natural number: the id function.

We can extend this and say that the set of even natural numbers is countably infinite because it has a mapping function of x => x / 2.

The same is true for all integers (natural numbers + negative numbers): x => if (x < 0) { x * -1 * 2 } else if (x == 0) { 0 } else { x * 2 + 1 }, i.e. if it's negative map it to an even number and if it is positive map it to an odd number, if it's zero map it to itself.

You can even write a function that maps all rational numbers to the natural numbers, since each rational number can be written as a fraction of two integers. (Figuring out the function is a fun exercise but it is also easy to google)

However, you can't write a function that maps any real number to a natural number. The easiest to understand proof of this is Cantor's Diagonal Argument[0], which is a proof by contradiction that shows that any attempted function must exclude some real numbers. Therefore, the real numbers are not countably infinite, and we call them uncountably infinite.

EDIT: In response to your edit, Cantor's Diagonal Argument basically shows that for any given function (and you have to define the function completely ahead of time - that's key) I can give you a real number that is not included in the domain of your function.

[0]: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Why a pre-definable function matters here? We have allowed a real number (that cannot be exhaustively described) in, so why a real function (that you cannot exhaustively define) has to be excluded? Isn't it unfair that I am only allowed to use a finitely definable function while you can choose a non-pre-finitely-describable real number? Isn't that a loop proof -- that the set of real numbers is uncountable simply because it is defined to be uncountable, and it is larger infinity than that of natural numbers simply it is defined to be bigger (as what bigger means in the context of infinity is otherwise undefined).

You don't have to use a finitely definable function. In fact, Cantor's argument defines the function as an infinite list of real numbers.

Here is how you do it. Have a function p(r) which evaluates to the previous real number. Then your mapping function is:

    f(r) = if (r == 0) { 0 } { else f(p(r)) + 1 }

If your objection is "You can't determine what the previous real number is." Then my counter-objection is "Please prove that you can't." Which I don't think is possible without first assuming reals are uncountable.

Your definition of f is circular: to calculate f(r) we need to know p(r), which in turn depends on f(r).

Cantor's diagonal argument shows that any mapping from the natural numbers to the real numbers must necessarily miss some real numbers out. It takes some time to get your head around if you aren't used to mathematical proofs, but it's definitely worth looking it up and trying to work through it if you're interested in this subject.

p(r) is given a real number and retrieves its predecessor. Why is it circular?

Suppose there exists an r' such that for some real number r, p(r)=r', where p(r) gives the real number that precedes r. What does that mean? Does it mean there are no numbers between r and r'? Because that's what I think predecessor means, even though it's trivial to prove that there are numbers between r' and r. For example, (r'+r)/2, the average of r and r', is between the two numbers. And there are also numbers between r and (r'+r)/2, and between r' and (r'+r)/2. So there can't possibly be a real that is the predecessor to another real, because there are always more real numbers between any two reals.

What is your definition of "previous real number"? If you define p(r) such that p(r) < r and there does not exist any real number x such that p(r) < x < r, then it is easy to show that p(r) cannot exist using a proof by contradiction.

Given real number r, assume there exists a real number q such that q < r and there does not exist a real number x such that q < x < r. Let real number y = (q + r) / 2. It is trivial to show that q < y < r. Therefore we have a contradiction, and therefore there does not exist a real number q that meets our conditions for a "previous real number".

If you take issue with this, then I suggest you read up on the standard construction of the number systems from the naturals up to the reals. This is all very rigorously defined in terms of ZFC set theory.

Reply on news.ycombinator.com