6 ms·

Was Cantor Wrong? Are the real numbers countable?

8 points by freefrancisco 13y ago

pesenti 13y ago
Your argument is indeed completely wrong. Let me construct a new positive even number as follows. Take the first positive even number, then add the second positive even number, then add the third positive even number, etc. The set of even number is infinite. And this is a divergent sum, it's infinite, not an even number.
- freefrancisco 13y ago
  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
dmfdmf 13y ago
Cantor is wrong, yes, but you won't prove that to contemporary mathematicians who believe his ideas because this is an epistemological issue and can't be resolve with mathematical arguments. This is really an age-old philosophic dispute that the mystics won decades ago. As David Hubert described it "No one shall expel us from the Paradise that Cantor has created." It is the "paradise" of deuces wild for the mathematicians and it rests on an equivocation of the meaning of "infinity". Cantor's idea of a "completed infinity" is a self contradiction if you grasp what the concept of infinity actually means and keep it tied to reality. It is the error of treating infinity as a real thing and not an abstraction. A similar error, for similar reasons, is made in the history of the philosophy by the mystics of nihil who wanted to treat nothingness as on par with existence via the Reification of Zero.
- mdxn 13y ago
  Can you be more specific about the nature of the logic you are using when concluding that a "completed infinity" is a self-contradiction? Are you sure that you aren't naively equivocating abstract notions of infinity with cardinal numbers?
  - dmfdmf 13y ago
    I am coming at this from a philosophic perspective so I don't know how much I can explain the mathematics. I am following Aristotle who held that infinity cannot actually exist; it is a potential, an abstraction. For something to actually exist it must be specific, it must be definite (which is a metaphysical principle) and for something to be "infinite" means a quantity, amount, characteristic, etc. that is not specified by definition. The genus of infinity is "process", some kind of identifiable change, such as adding one to a number to get the next number in a sequence, that is open-ended. Infinity identifies the open-endedness of the process but any real process (such as you counting "to infinity") must terminate as some point and must have a definite state at any given moment (such as being at 2,345,652 at such and such date and time). In sum, a completed infinity would mean an open-ended process that has stopped which contradicts the meaning of infinity, at least on my terms. Moreover, in my view Cantor makes exactly the same conceptual mistake as a child that uses the phrase "counting to infinity". NB: To be fair, infinity is a valid mathematical concept but it has to be used very carefully to avoid sliding into non-sense. Some of Cantor's work may actually be valid, I do not know. But given my views I suspect that his basic error is trying to "count the unspecified", i.e. the infinite. This whole approach appears to be invalid since the concept "counting" necessarily presupposes that what you are counting has a specific identity. Unfortunately, to separate the wheat from the chaff means some future mathematician will need to become an epistemologist to sort it all out as the problem is in philosophy not mathematics.
thenerdfiles 13y ago
The new string has to be placed in the assumed list of Reals. If you place it anywhere, you have to recast the Reals. It's not just that it's new by algorithm, but it does not have a deterministic place within the assumed list of Reals. It's a new "Cantor's Paradise" every time you place that new number. And it does not come into existence by the same procedure used to START generating the list. It's a metanumber -- exception to rule. This is why one has to have a metaphysics of number before one accepts the proof. Why Hilbert et al accept the proof on aesthetic grounds, and a whole class of mathematics on aesthetic grounds. The appropriate response is: That's just another real number. Naturals, etc START somewhere but you are not forced to reindex with each new number.
- thenerdfiles 13y ago
  It's not necessary to believe in all those classes of infinities to see the sui generis nature of the mathematical gesture used to generate the Metanumber. Between any two mathematicians, likely the two will pluck very different Rules from their imaginations or backgrounds to produce some other real number. What is interesting is that we have a new real but also a new list. The lists are contiguous games, not a continuous "paradise." Number is the market wherein we SHARE rules. If we give up rule-sharing, the market itself has no value nor do the numbers (and then all order is defeated).
- thenerdfiles 13y ago
  What is cool to consider is that some algorithms for Metanumber might yield ASCII art. In some cases, we might see glyphs. We first have to agree on where to start the reals, which is simple agreement, but the Metanumber strategy could stir up aesthetic commitments since reals do not include an encoding to direct the list itself. Naturals are encoded to place other naturals.
mdxn 13y ago
In your set of positive even numbers example, you are only showing that a specific enumeration scheme does not generate the set of even numbers. A diagonalization argument requires that you show that no such enumeration scheme can exist (not just a particular chosen one). In the typical proof of diagonalization, it does not presuppose any particular scheme of listing the numbers. It just assumes that some arbitrary one exists, then derives a contradiction. For your binary tree construction, a trancedental real number can be represented by a path of infinite length down the tree. Your argument is that since a breadth first traversal will eventualy exhaust that whole path, that the real number described by it will have been encountered. There are two ways to interpret what you are doing wrong: - If we are indexing/pairing these nodes by time steps (an index), your construction is using a countably infinite time step to express the numbers described by an entire path (which defeats the point of being countable). - For countable sets, you have to give me an index of finite size. If I give you a real number, you need to return a natural number (or equivalent) that indicates where it is. To test this, give me the index of pi in your claimed "countable" enumeration. The reason you wont be able to somewhat follows from Cantor's diagonalization scheme. You might want to do some Googling before spending the time to write up an entire blog post about it (god forbid posting it to HN). The mistake you made is very common and has been discussed to death. You would have caught it.
- freefrancisco 13y ago
  Thanks for your reply, the index of finite size is the part where I was confused. I have actually done some googling about this before, and never caught it, because I wasn't exactly sure where I was uneasy. This has bothered me for a while, but reading that post in HN prompted me to think about it more, and I started writing my thoughts in a communicable manner in order to organize my own thinking. I figured publishing it and submitting it to HN would be a very effective way to get immediate feedback. In HN if you are wrong people will gladly let you know quickly. Also putting it in HN helps prompt people to post and argue about it and other ideas that are related, so it's an interesting and fun discussion.
banku_brougham 13y ago
Why do programmers assume they are mathematicians? There is a huge difference between those disciplines. Trying to uphold the HN principles here, with a civil but pointed question. Computer science is deep, so is physics, and mathematics as well but they are distinct and quite different. Steven Hawking fumbled the proof of the infinitude of primes in his excellent survey of mathematical history "God Created the Integers," as usual for physicists he saw his way to the proof without traversing each step. Infinity is a difficult but knowable concept. Calculus is a good teacher of this, and Euclid is a good teacher of proof. That's what's missing I say: the standard of proof. For physicists and computer scientists that standard depends on the outcome of physical events, but mathematics requires a purity that doesn't exist in the physical world.

8 points by freefrancisco 13y ago

Your argument is indeed completely wrong. Let me construct a new positive even number as follows. Take the first positive even number, then add the second positive even number, then add the third positive even number, etc. The set of even number is infinite. And this is a divergent sum, it's infinite, not an even number.

freefrancisco 13y ago
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

dmfdmf 13y ago

Cantor is wrong, yes, but you won't prove that to contemporary mathematicians who believe his ideas because this is an epistemological issue and can't be resolve with mathematical arguments. This is really an age-old philosophic dispute that the mystics won decades ago. As David Hubert described it "No one shall expel us from the Paradise that Cantor has created." It is the "paradise" of deuces wild for the mathematicians and it rests on an equivocation of the meaning of "infinity". Cantor's idea of a "completed infinity" is a self contradiction if you grasp what the concept of infinity actually means and keep it tied to reality. It is the error of treating infinity as a real thing and not an abstraction. A similar error, for similar reasons, is made in the history of the philosophy by the mystics of nihil who wanted to treat nothingness as on par with existence via the Reification of Zero.

mdxn 13y ago
Can you be more specific about the nature of the logic you are using when concluding that a "completed infinity" is a self-contradiction? Are you sure that you aren't naively equivocating abstract notions of infinity with cardinal numbers?
- dmfdmf 13y ago
  I am coming at this from a philosophic perspective so I don't know how much I can explain the mathematics. I am following Aristotle who held that infinity cannot actually exist; it is a potential, an abstraction. For something to actually exist it must be specific, it must be definite (which is a metaphysical principle) and for something to be "infinite" means a quantity, amount, characteristic, etc. that is not specified by definition. The genus of infinity is "process", some kind of identifiable change, such as adding one to a number to get the next number in a sequence, that is open-ended. Infinity identifies the open-endedness of the process but any real process (such as you counting "to infinity") must terminate as some point and must have a definite state at any given moment (such as being at 2,345,652 at such and such date and time). In sum, a completed infinity would mean an open-ended process that has stopped which contradicts the meaning of infinity, at least on my terms. Moreover, in my view Cantor makes exactly the same conceptual mistake as a child that uses the phrase "counting to infinity". NB: To be fair, infinity is a valid mathematical concept but it has to be used very carefully to avoid sliding into non-sense. Some of Cantor's work may actually be valid, I do not know. But given my views I suspect that his basic error is trying to "count the unspecified", i.e. the infinite. This whole approach appears to be invalid since the concept "counting" necessarily presupposes that what you are counting has a specific identity. Unfortunately, to separate the wheat from the chaff means some future mathematician will need to become an epistemologist to sort it all out as the problem is in philosophy not mathematics.

thenerdfiles 13y ago

The new string has to be placed in the assumed list of Reals. If you place it anywhere, you have to recast the Reals. It's not just that it's new by algorithm, but it does not have a deterministic place within the assumed list of Reals. It's a new "Cantor's Paradise" every time you place that new number. And it does not come into existence by the same procedure used to START generating the list. It's a metanumber -- exception to rule. This is why one has to have a metaphysics of number before one accepts the proof. Why Hilbert et al accept the proof on aesthetic grounds, and a whole class of mathematics on aesthetic grounds. The appropriate response is: That's just another real number. Naturals, etc START somewhere but you are not forced to reindex with each new number.

thenerdfiles 13y ago
It's not necessary to believe in all those classes of infinities to see the sui generis nature of the mathematical gesture used to generate the Metanumber. Between any two mathematicians, likely the two will pluck very different Rules from their imaginations or backgrounds to produce some other real number. What is interesting is that we have a new real but also a new list. The lists are contiguous games, not a continuous "paradise." Number is the market wherein we SHARE rules. If we give up rule-sharing, the market itself has no value nor do the numbers (and then all order is defeated).
thenerdfiles 13y ago
What is cool to consider is that some algorithms for Metanumber might yield ASCII art. In some cases, we might see glyphs. We first have to agree on where to start the reals, which is simple agreement, but the Metanumber strategy could stir up aesthetic commitments since reals do not include an encoding to direct the list itself. Naturals are encoded to place other naturals.

mdxn 13y ago

In your set of positive even numbers example, you are only showing that a specific enumeration scheme does not generate the set of even numbers. A diagonalization argument requires that you show that no such enumeration scheme can exist (not just a particular chosen one). In the typical proof of diagonalization, it does not presuppose any particular scheme of listing the numbers. It just assumes that some arbitrary one exists, then derives a contradiction. For your binary tree construction, a trancedental real number can be represented by a path of infinite length down the tree. Your argument is that since a breadth first traversal will eventualy exhaust that whole path, that the real number described by it will have been encountered. There are two ways to interpret what you are doing wrong: - If we are indexing/pairing these nodes by time steps (an index), your construction is using a countably infinite time step to express the numbers described by an entire path (which defeats the point of being countable). - For countable sets, you have to give me an index of finite size. If I give you a real number, you need to return a natural number (or equivalent) that indicates where it is. To test this, give me the index of pi in your claimed "countable" enumeration. The reason you wont be able to somewhat follows from Cantor's diagonalization scheme. You might want to do some Googling before spending the time to write up an entire blog post about it (god forbid posting it to HN). The mistake you made is very common and has been discussed to death. You would have caught it.

freefrancisco 13y ago
Thanks for your reply, the index of finite size is the part where I was confused. I have actually done some googling about this before, and never caught it, because I wasn't exactly sure where I was uneasy. This has bothered me for a while, but reading that post in HN prompted me to think about it more, and I started writing my thoughts in a communicable manner in order to organize my own thinking. I figured publishing it and submitting it to HN would be a very effective way to get immediate feedback. In HN if you are wrong people will gladly let you know quickly. Also putting it in HN helps prompt people to post and argue about it and other ideas that are related, so it's an interesting and fun discussion.

banku_brougham 13y ago

Why do programmers assume they are mathematicians? There is a huge difference between those disciplines. Trying to uphold the HN principles here, with a civil but pointed question. Computer science is deep, so is physics, and mathematics as well but they are distinct and quite different. Steven Hawking fumbled the proof of the infinitude of primes in his excellent survey of mathematical history "God Created the Integers," as usual for physicists he saw his way to the proof without traversing each step. Infinity is a difficult but knowable concept. Calculus is a good teacher of this, and Euclid is a good teacher of proof. That's what's missing I say: the standard of proof. For physicists and computer scientists that standard depends on the outcome of physical events, but mathematics requires a purity that doesn't exist in the physical world.