Was Cantor Wrong? Are the real numbers countable?
medium.com
medium.com
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.
You can object to ZF(C) as the basis for set theory, but I don't see how one can call it "wrong." If you want to build up a theory without the Axiom of Infinity you're free to do so — many mathematicians have. Either Cantor's arguments follow from ZF(C) or they don't (hint: they do).
It's not a philosophical problem at all. One can certainly explore what it would mean to do mathematics without access to "infinity", as many mathematicians in the first half of the 20th century did. IMO this conversation is all air until you propose your own precise set of axioms.
Well, that was my main point. You are free to disagree.
> IMO this conversation is all air until you propose your own precise set of axioms.
Apoplectically, the three basic axioms are Existence, Identity and Consciousness. Whatever the proper mathematical axioms (and methods) are they have to be consistent with these three. Cantor's method treats infinity as a real thing, which violates the axiom of identity. You could even call it the Reification of Infinity but the error is easier to see in Rand's identification of Reification of Zero by the mystics who attempt to treat nothingness as real.
That's fine — I don't care whether it does or not — but mathematics has no opinion on the matter. You're free to choose a set of mathematical axioms which you don't find objectionable and go about doing your math in that universe.
If you want to claim Cantor's argument is invalid then you need to tell me what axioms you're taking as the foundation for your mathematics. It is valid in ZF(C) and I'm 99% sure it's valid in plain ZF. Which of the axioms of ZF do you find objectionable and what would you replace them with?
Assuming you're trying to engage sincerely, I'd ask you to be precise. This means listing whatever foundations of mathematics you don't find objectionable and talking about how they differ from ZF(C).
If you're unfamiliar with it, I'd read up on proof theory: http://en.wikipedia.org/wiki/Proof_theory
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.
Philosophical* perspectives require clear, factually driven, referencable arguments.
Philosophy is not a fancy word for opinion.
.
"which contradicts the meaning ... at least on my terms."
When you have to change the meanings of words in order to feel like you've made a point; etc.
.
"Unfortunately, to separate the wheat from the chaff means some future mathematician will need to become an epistemologist"
The person you're looking for is named Georg Cantor. That work was all done already. You are merely unfamiliar with it.
.
"the problem is in philosophy not mathematics."
The philosophy of mathematics has considered this matter settled for several hundred years now.
It turns out they're an existing community. You could try reaching out to them. Nuel Belnap is a very nice man, and would probably explain this to you if you asked, without presuming first that you knew someone to be wrong when you weren't familiar with their work.
This was not a cop out as you portray but recognition that many people are not familiar with Aristole's position on infinity nor is it the popular view. I defined my terms and explained my position as to why Cantor's use of "completed infinity" is a contradiction. It is clear to anyone who wants to understand. I defy you to define, in your own words, your concept of infinity and what you actually mean by a completed one without degenerating into non-sense.
> The philosophy of mathematics has considered this matter settled for several hundred years now.
This was hardly a fair fight. As I conceded, the mystics won round one which is why Cantor's non-sense is accepted. The philosophy of mathematics is and was dominated by Platonists and other avowed irrationalists. So no surprise in this outcome.
Potential infinity aligns with the explanation you provide in the second paragraph. It refers to the process of arbitrarily unbounded enumeration (having the potential to count to any arbitrary number). This is equivalent to the capabilities of a Turing Machine. Aristotle's argument is that the human mind (Turing Machine) is restricted to computing decidable problems and cannot compute undecidable ones. The whole point of the application of Cantor's diagonalization argument is to demonstrate this limitation.
Cantor rather argues that assuming the Axiom of Infinity does not necessarily lead to a contradiction (unless you assume the opposite of course). The assumption simply states that some infinitely large set exists, in particular, the natural numbers. It does not have to physically exist, but we certainly can theoretically associate a finite characterization to it. You should look into Kolmogorov complexity for this. Note that this is NOT at all the same thing as "counting to infinity".
A lot of people will counterargue that infinity is just a concept, but I feel as if they miss part of the point. A similar argument would lead to the conclusion that pi does not exist and neither does the number, 2. The only difference is that we apply the concept of two-ness to discrete objects we can compute with. We do have recursive descriptions (programs) that can describe a countable infinity (aleph null) or even pi. We might as well use these descriptions as placeholders for the actual thing. While we cannot contain the base 10 encoding of pi, we have another encoding of it of finite length (the program). Who is to say that a base 10 encoding of numbers is a better proof of existence than one written in C++?
You might have more success with arguing against the existence of undefinable numbers. These do not have a description of finite length and are definitely numbers that we cannot conceptualize with our current assumed limitations.
I agree, this is the crux of the issue.
> It refers to the process of arbitrarily unbounded enumeration (having the potential to count to any arbitrary number).
This is too narrow. The world is full of infinite processes including your life or the earth revolving around the sun, etc. These are the facts that give rise to the concept though enumeration is the archetypical example because its so easy to see. The danger is forgetting that that someone (or a TM) must be doing the enumeration and eventually he (it) will die, planets will be engulfed by the sun, etc. So no real process goes on literally for infinity.
>Aristotle's argument is that the human mind (Turing Machine) is restricted to computing decidable problems and cannot compute undecidable ones.
He went even farther than that -- he argued that what ever the mind (or Turing machine) is processing, becoming aware of or knowing has to be finite too. His basic principle of existence is that whatever exists must have identity, including the mind.
> It does not have to physically exist, but we certainly can theoretically associate a finite characterization to it.
Here is where we disagree or maybe misunderstand each other. You are equivocating on "it". "It" what? By definition, infinity leaves undefined the length, life or extent of the process. Whatever the process is, it is open-ended. Now you can't add back or sneak in some finite measure of the length or extent of the process without destroying its meaning. What you can do is say things about the process even while abstracting away its metaphysical and eventual termination. This is in fact the main value of infinity as a mathematical concept, such as with limits.
> A similar argument would lead to the conclusion that pi does not exist...
Well, what do you mean by "exist"? Clearly the relation it identifies exists but it does not denote a specific number. Pi denotes a specific open-ended process to calculate a number based on what you are trying to do with the math. So if you are buying tile for your circular patio you might use 3.14 to determine the area and how much tile you need but if you are a NASA engineer and want to land a rover on Mars you'll need to carry a few more decimal places, but not an infinite number of them, and the meaning is clear.
That Pi is irrational means that curved paths are incommensurable with linear measures. This did not stop the mathematicians as they just defined a symbol to represent an infinite process (implicitly at first but later fully developed in calculus) that defines the ratio and treat it just like any other number in further equations and theory, and in that sense it is a specifically defined number, and math theory could proceed.
The mistake that mathematicians made, primarily due to Plato, was thinking that Pi is a "completed" number in some super reality where ideal, abstract math exists. It was just a matter of time before Cantor came along and applied the same idea to infinity itself.
Describe to me any particular infinite process which does not derive or presume the existence of an actual infinity (e.g. an infinitely large set). You may also want to specify the details of your model for an infinite process to prove that your example isn't circular.
---------------
I promise that I will not simply quantify over all the results of the process and call it an infinite set.
You may use time as part of the definition of your process, but you may not prematurely assume that there is an infinite process for enumerating timesteps. If you did, the example would run the risk of being circular. If you can construct it, then you can use it.
Likewise, you may include a finite number of atoms, but you can't sweep any actual infinite objects underneath them.
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.
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?]
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!
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.
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.
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).
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.
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.
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.