You’re right–the first ‘is’ was supposed to be ‘are’ in that sentence. You spotted that fact and articulated it so readily that I am amazed at your implication that you did not understand the intent of the sentence.
-FrL-
Just as an interesting side note, in intuitionistic logic (often described as a branch of “constructive logic”, where existence proofs have to come with explicit constructions, in some sense), the axiom of choice is not assumed, and, in fact, “fails” so very thoroughly that one cannot even prove “Given a collection of at most one set of two elements, there is a choice function on that collection”. [This is only a tiny bit related to what you were talking about, and as others have said you seem to be a little off on what you take the axiom of choice to be, but it’s an amusing piece of trivia which your remark called to mind]
I agree that Cantor’s proof, as usually presented to high school students, is a little troubling.
Suppose somebody presents a real number: 0.7175 . . . What exactly does that mean? Reasonable people could interpret it in different ways. A better way to represent a real number would be with a description or formula. But logically, the cardinality of the set of descriptions or formulas is equal to Aleph-null.
Does that mean that there exist real numbers that can’t be described with a description or formula? If so, why should we worry about these indescribable numbers?
Yes.
Yes, the standard interpretation is that there exist real numbers which can’t be described with a description or formula. (For example, consider a real number whose nth digit is one off from the nth digit of the nth describable number). I can’t tell you why you should worry about them, though it shouldn’t be hard to see why, for many people, it is natural to take an interest in them.
Incidentally, another curious factoid about intuitionistic logic is that, while Cantor’s proof continues to show that the naturals and the countably infinite binary sequences (which I prefer to speak of over the mess of the real numbers and decimal expansions) cannot have the same cardinality, it doesn’t necessarily follow that there are more reals, in any intuitive sense, than naturals. There are toposes (essentially theories/models of intuitionistic logic) in which the countably infinite binary sequences are “subcountable” (having the same cardinality as induced by some equivalence relation on a subset of the naturals); for example, there is the effective topos, in which all functions are computable. As is easy to see, the computable countably infinite binary sequences are all computably described by particular programs (specifically, the ones which output an unending stream of 0s and 1s), which are, of course, a subset of the countable collection of all programs. However, as Cantor’s Theorem demands, there is no computable surjection from programs to computable countably infinite binary sequences for reasons having to do with the Halting Problem.
So there is room to take Cantor’s Theorem not as telling us that there exists more than what descriptions give us, but as speaking of something rather more subtle than that, about our ability to describe surjections from definitions to the things they describe.
That was rather vaguely worded, but can be illustrated more precisely by observing that Cantor’s Theorem, when interpreted in the appropriate category, yields Tarski’s Indefinability Theorem, among many other such results. For more along this line (seeing how Tarski’s indefinability results, Goedel and Rosser’s incompleteness results, Turing and Church’s undecidability results, Kleene’s recursion theorem, Curry’s fixed point combinator, and much more, simply are Cantor’s theorem when applied in the appropriate contexts, I highly recommend reading Lawvere’s “Diagonal Arguments and Cartesian Closed Categories” (which is a bit heavy in using category theory, but well worth it) or “A Universal Approach to Self-Referential Paradoxes, Incompleteness, and Fixed Points” by Yanofsky (which is much more introductory and has loads more examples, though in trying to avoid explicitly discussing category theory, he makes some mistakes and eye-roll-inducing claims).
Incidentally, if you reject that this and things like it are legitimate description of a real number, you’ll have the start of a way out, but you will be pretty much forced to accept that the legitimate descriptions, while presumably an infinite subset of the countable collection of all possible utterances, are not themselves countably infinite; you will have to adopt something like intuitionistic logic, which is able to maintain a distinction between “subcountably infinite” and “countably infinite”, as remarked in the second paragraph above.
As the article I linked to above mentions, the definable real numbers are not a complete field unless you disallow undefinable sequences. That seems like a reasonable thing to do, but it’s kinda nice that the standard calculus results we know and love hold for things we can’t even begin to talk about.
True, but they are complete with respect to suprema of definable sets, which is generally enough for the standard calculus results we know and love (unless one of the results you know and love is “The reals are complete with respect to arbitrary sets, definable or not”, in which case, there’s just no pleasing you :)).
Whoops, sorry, I forgot to explain the apparent paradox here, that I have given a description of a number which, by construction, cannot have a description. The standard reply is that when I say “nth describable number”, I must say mean describable with respect to some particular language, and that three word phrase “nth describable number” must itself fall in some other language, thus avoiding contradiction but imposing that no language contains within itself the means to interpret descriptions within itself, so to speak (this was Tarski’s strict separation of object language from metalanguage). Some people are ok with that; for others who embrace intuitionistic logic (thus not accepting “A or not A” or “not not A implies A” or other such things as unfailing bedrock logical principles), there are sometimes other trickier ways out as I was speaking of before, though they still only go so far (for those who care, while intuitionistic logic is cool with subcountability of the sequences of binary digits, it’s still not cool with subcountability of the sequences of “truth values”; classical logic isn’t cool with either, since it internally conflates binary digits and “truth values”, in some sense).
(I just realized that in my post two above, I misread ultrafilter’s post and proceeded to make points he had already made, while not addressing his actual final point. Sorry about that…)
ianzin: maybe I can refomulate Cantor’s proof in a way that does not rely on the notion of a ‘list,’ and which is actually more in tune with how mathematicians think about it nowadays.
First, we define the size (cardinality) of a set indirectly:
the cardinality of a set A is less than or equal to the cardinality of the set B if
there is an injective function from A to B. (Recall that an injective function is one that sends different elements to differnent places)
Let’s test this definition on finite sets:
size of {a,b,c} is less than or equal to size of {z,x,c,v}, since there is an injective function from the former to the latter. For example, a goes to z, b goes to x, c goes to c.
However, size of {z,x,c,v} is not less than or equal to size of {a,b,c}, since any function from the former to the latter must send two different elements to the same place.
On to Cantor’s proof:
He assumes (in the sense of a Reductio ad absurdum) that there is an injective function from the set of real numbers between 0 and 1 to the set of natural numbers. So, for each of these real numbers, there is a natural number that this injective function sends it to.
Well, you know the rest: For each natural number n, he takes whichever real number is mapped to it and chooses a different choice for the n-th digit. He then takes all of these different digits, and puts them together in the right order, and says that this new number cannot be mapped anywhere, otherwise it would violate the injectivity of the function (that is, it would be mapped to the same place as a different real number), giving a contradiction (again, in the sense of a Reductio ad absurdum).
Actually, he assumes a surjective (onto) function from the natural numbers to the real numbers between 0 and 1, so that, for each such real number, there is (at least) one natural number sent to it. (I think the usual proof assumes a bijection, but actually shows that there is no surjection.)
Quite right. In classical logic, it’s all the same, though, since the existence of an injection from B to A implies the existence of a surjection from A to B, as long as B is an inhabited set*. However, in various other common systems (such as intuitionistic logic, which I apologize for continuing to harp on about), this fails, and Cantor’s Theorem is best stated in the form dealing with surjections for its generalized interpretation in categories other than that of classical sets (as in Lawvere’s work relating it to indefinability/incompleteness results).
*: Proof: If f is an injection from B to A, and b is some element of B, then define the surjection g from A to B by g(x) = the y in B such that f(b) = x, if such a (necessarily unique) y exists, and g(x) = b otherwise. For this construction to work, it is crucial that for every x, there either is or is not an element of B mapping to it under f, an instance of the law of the excluded middle which can fail intuitionistically.
Incidentally, using the Axiom of Choice, you can get the opposite implication as well; in fact, one way of stating the Axiom of Choice is that, for every surjection g from A to B, there is an injection f from B to A such that g composed with f is the identity function on B.
Typo corrected in bold.
The last several posts show the falsity of this claim.
It’s unclear how “reasonable people” might be defined, but it is also completely irrelevant. Professional mathematicians define “real number” and every other concept in extremely rigorous fashion, with no wiggle room for “reasonable people” to stick their two cents in.
Seems to me this is a continuation of the standard mistake seen on GQ a lot. People confuse the English language depiction of mathematics (or physics or whatever science) with the underlying symbolic language that it is actually written in, and then try to make claims based on the English language version. Or, worse, a garbled understanding of the English-language version implying no understanding at all of the symbolic-language version combined with an absolute insistence that their claims still somehow and against all sense and reason must be right.
Trying to present English-language simplifications, metaphors, or analogies for scientific concepts is a tricky business at best, even when people understand that what’s being said are merely simplifications, metaphors, or analogies. When people take them as absolutes, confusion is inevitable.
Well, let me ask a slightly different question.
By analogy, suppose my child asked me what the point of negative numbers is. One thing I might say is that it’s useful in arithmetic to have a “minus” function. But then a question like “4 minus 7” comes along. Rather than leave the answer undefined, one can introduce the idea of negative numbers and come up with a consistent and logical system which makes use of negative numbers. Not only that, but negative numbers are useful in accounting, engineering, etc.
So negative numbers fill a hole and have a use.
Is there any analogous motivation for “indescribable” numbers? Do they fill some hole? Also, is there any analogous use for them?
As part of the big shake-up at the start of the 20th century, we got a standard recipe for constructing real numbers given the axioms of set theory. The standard sequence is that you start with sets, move on to natural numbers, then integers, then rationals, and finally reals (and the complex numbers after that). The thing is that you can get the natural numbers without negative integers: just stop after the first step. But you can’t get irrational numbers without the undefinable numbers as well, as the real numbers are necessarily uncountable, and the set of descriptions (however that’s formalized) is countable. They aren’t useful, they aren’t something we want, but they exist, and we’re stuck with them.
ETA: You could, in theory, stop with the rationals and avoid the issue of undefinability, but then you end up with an incomplete metric space, and that makes calculus ugly.
Well, for starters, let’s clarify that the standard position is not that numbers are intrinsically definable or undefinable, but only so with respect to a particular language in which to give definitions, of course. What cannot be defined with a polynomial equation may be definable with a transcendental equation. What cannot be defined in first-order logic may be definable in second-order logic. What cannot be defined by a computer program may be definable in English (whatever we are to formalize English as). It is very important to understand that undefinability is language-relative, and I will return to this point later.
As for what use undefinable numbers might have… one might say that they have the same use that everywhere continuous, nowhere-differentiable functions have: it’s not as though we specifically designed our mathematical systems with their construction in mind, but they turned out to be an inevitable consequence of the rules of our system all the same. They are a side effect of decisions we have made with an eye towards convenience in other ways.
Plenty of people have such nominalistic convictions as that they would prefer to say that there are no “undefinable” numbers (or anything else). The problem is that it’s very hard to reconcile this with the apparent proof that, with respect to any given language of definition, undefinable entities do exist. What would you reject in the following line of argument, which shows the existence of an undefinable mathematical entity (relative to a particular language of definition)?
- Fix a language of definition L. As an intuitive example, let’s pretend L is something like English.
- We can define various properties of definitions in the language of L. For example, thinking of L as English, you can define within it the property of being less than a hundred words, the property of being a palindrome, the property of referring to a country in Asia, and so on.
- Let us consider specifically the fact that some terms in L may define properties which they do not themselves satisfy. For example, “the property of being longer than a hundred words”, “the property of being in German”, and “the property of being a palindrome” each define properties which they do not themselves satisfy.
- Call such definitions “L-heterological”.
- Can the property of being L-heterological be defined in L? Well, suppose it could be. We could then ask “Is the definition of L-heterological itself L-heterological”? Well, it would be if and only if the definition of L-heterological didn’t satisfy the property of being L-heterological. This yields a paradox.
- Conclusion: The property of being L-heterological cannot be defined in L. We have shown the existence of an entity which cannot be defined in L.
The result is unsettling for many, particularly when L is taken as something like English, but what would you reject?
Why not? (Assuming that we limit irrational numbers to those that can be described).
I wouldn’t have phrased it the way ultrafilter did. You could get some irrational numbers without the undefinable ones, of course. The problem is that those who believe in the undefinable ones will think you have failed to get all the irrationals. And they will have very specific reasons for thinking you have missed some; the existence of undefinable numbers follows from very natural, seductive principles, including, as I think ultrafilter was pointing out, the ones generally used to construct the real numbers from the rationals.