4 ms·

Thanks for the response, a few of my friends in Facebook told me the same thing, the constructed number is infinite, so it is not a member of the set and my arg

Thanks for the response, a few of my friends in Facebook told me the same thing, the constructed number is infinite, so it is not a member of the set and my argument is invalid. Do you have any insight as to why my attempt to show that the reals are countable by placing them in a binary tree is also wrong? We know the rationals are countable by putting them in a grid and mapping them to the natural numbers, how is this fundamentally different from putting the reals in a binary tree?

colanderman 13y ago
You sound like a computer scientist, so think of it this way. When would your breadth-first search terminate, given an irrational number to locate? Can you even bound it? The answer is no, because there are an infinite number of digits in any irrational number. The breadth-first search would not terminate; the result would diverge toward infinity. With the rationals in a grid, even ignoring that I can trivially arithmetically compute the corresponding natural (interleave the (finite!) digits of the numerator and denominator), I can give a bound on a similar search (say Z-order): O(n²). I think the fundamental idea you are missing is that a natural number must have a finite number of digits. (This stems from the construction of naturals as finite objects.) Reals are not subject to this limitation, as evidenced by the existence of the irrationals. [Actually, that last paragraph begs another question: what are the theoretical implications of the fact that any specific real must have a finite representation of some form? Does the reason we can reason about reals which we can't specifically identify with a finite construction have anything to do with the axiom of choice?]
- freefrancisco 13y ago
  This actually helps a lot with the intuition, thanks! So in a sense every irrational number is an infinite number because there is no way to actually represent it in a finite way.
  - colanderman 13y ago
    Almost! See pesenti's link about definable numbers: most irrationals have no finite representation, although almost all the ones we are familiar with (e.g. sqrt(2), π, e) do: they can be represented as mathematical formulæ. (And indeed, note that such "definable" reals are countable!) So in my example above, π would not work if, say, your tree was a parse tree of mathematical formulæ: one could locate the formula for π in finite time. Unfortunately I cannot give an example of a single number which does not have such a finite parse tree, as, by its very nature, I cannot write down a finite description of it!
  - jfarmer 13y ago
    Not quite. I can represent pi in a finite way, like so: π. That's about as finite as it gets! However, if you fix a finite alphabet beforehand, you will never be able to describe all real numbers using strings constructed from this alphabet. You can always add a new symbol to your alphabet to represent some new irrational number, but no matter how many symbols you add you'll never be able to reach "every" irrational number. Put another way, for a given alphabet there's no way to represent every irrational number in a finite way. However, you could have an irrational number that can be finitely represented in one alphabet, but unable to be finitely represented in another.
- pesenti 13y ago
  what are the theoretical implications of the fact that any specific real must have a finite representation of some form? See http://en.wikipedia.org/wiki/Definable_number http://en.wikipedia.org/wiki/Definable_number
  - colanderman 13y ago
    Great, thanks! It's helpful to know that such definable numbers are in fact a superset of computable numbers [1]; I was naïvely assuming these notions to be equivalent. [1] http://en.wikipedia.org/wiki/Computable_number http://en.wikipedia.org/wiki/Computable_number

colanderman 13y ago

You sound like a computer scientist, so think of it this way. When would your breadth-first search terminate, given an irrational number to locate? Can you even bound it? The answer is no, because there are an infinite number of digits in any irrational number. The breadth-first search would not terminate; the result would diverge toward infinity. With the rationals in a grid, even ignoring that I can trivially arithmetically compute the corresponding natural (interleave the (finite!) digits of the numerator and denominator), I can give a bound on a similar search (say Z-order): O(n²). I think the fundamental idea you are missing is that a natural number must have a finite number of digits. (This stems from the construction of naturals as finite objects.) Reals are not subject to this limitation, as evidenced by the existence of the irrationals. [Actually, that last paragraph begs another question: what are the theoretical implications of the fact that any specific real must have a finite representation of some form? Does the reason we can reason about reals which we can't specifically identify with a finite construction have anything to do with the axiom of choice?]

freefrancisco 13y ago
This actually helps a lot with the intuition, thanks! So in a sense every irrational number is an infinite number because there is no way to actually represent it in a finite way.
- colanderman 13y ago
  Almost! See pesenti's link about definable numbers: most irrationals have no finite representation, although almost all the ones we are familiar with (e.g. sqrt(2), π, e) do: they can be represented as mathematical formulæ. (And indeed, note that such "definable" reals are countable!) So in my example above, π would not work if, say, your tree was a parse tree of mathematical formulæ: one could locate the formula for π in finite time. Unfortunately I cannot give an example of a single number which does not have such a finite parse tree, as, by its very nature, I cannot write down a finite description of it!
- jfarmer 13y ago
  Not quite. I can represent pi in a finite way, like so: π. That's about as finite as it gets! However, if you fix a finite alphabet beforehand, you will never be able to describe all real numbers using strings constructed from this alphabet. You can always add a new symbol to your alphabet to represent some new irrational number, but no matter how many symbols you add you'll never be able to reach "every" irrational number. Put another way, for a given alphabet there's no way to represent every irrational number in a finite way. However, you could have an irrational number that can be finitely represented in one alphabet, but unable to be finitely represented in another.
pesenti 13y ago
what are the theoretical implications of the fact that any specific real must have a finite representation of some form? See http://en.wikipedia.org/wiki/Definable_number http://en.wikipedia.org/wiki/Definable_number
- colanderman 13y ago
  Great, thanks! It's helpful to know that such definable numbers are in fact a superset of computable numbers [1]; I was naïvely assuming these notions to be equivalent. [1] http://en.wikipedia.org/wiki/Computable_number http://en.wikipedia.org/wiki/Computable_number