Cantor’s famous diagonal argument demonstrates that the real numbers are a greater infinity than the countable numbers. But it relies on the decimal expansions of irrational numbers. Is there any way to demonstrate an equivalent proof in non-positional number systems? Is there any way that a proof that the number of points on a line is greater than the number of whole numbers could have been shown to the ancient Greek mathematicians like Zeno? Or does it rely on too many advances in mathematics between then and the 19th century?
Cantor’s diagonal proof was not his first proof of the uncountability of the reals. His first proof did not depend on numbers being represented by a positional number system. Also his second, diagonal, proof used binary numbers, not decimal.
You obviously need some way of talking about real numbers, but in any method of talking about real numbers, you can come up with some sort of proof.
But questions like this always run into the question of just what it means to say “without using such-and-such mathematical construct”. If nothing else, you can always just construct that concept yourself within your proof. It would get tedious to do that for everything all the time, but it could be done.
Well, binary is surely a positional system: it explicitly incorporates zero.
I always thought the diagonal proof was more of a demonstration than a fundemental thing: sort of “let’s see if we can establish this in a way that doesn’t require advanced theoretical concepts”?
One obstacle is that “the number of whole numbers” and “the number of points on a line” represent actual or completed infinities as opposed to potential infinities, and, as I understand it, the ancient Greeks rejected the idea of actual infinity.
It sounds to me like this conceptual problem would be an insurmountable obstacle for the ancient Greeks.
Yes it is. I was addressing the OP’s statement that “it relies on the decimal expansions of irrational numbers”. Cantor’s original proof used binary numbers, but the proof works (with minor changes) in any radix.
Since it’s pretty easy to understand and doesn’t require any knowledge of advanced math, there are many popular expositions of it that are less than rigorous, but Cantor’s proof is a perfectly valid and rigorous proof.
The idea of a completed infinity was an insurmountable obstacle to many mathematicians even in Cantor’s time. Ancient Greek mathematics was very limited in what they considered to be legitimate mathematical objects. They did not even accept that 1 is a number.
Ancient Greek mathematics was as much philosophy as mathematics. They certainly thought of themselves as philosophers. But some were more pragmatic and smarter than others. Archimedes might have been a lot more receptive.
They were aware of irrationals - at least as much as it was known to them how to prove say \sqrt{2} was not rational. And they famously really didn’t like that. They would likely grudgingly accept the idea of algebraic numbers. But they are still countable. The idea of transcendental numbers would likely be too big a jump. Proof that \pi was not rational, or even algebraic, would just get you back to a special case. Not a question about almost all numbers.
The diagonalisation proof for the countability of the rationals would blow their minds right away. Countability of the algebraics would not be much of a step from this, so wouldn’t change much. The notional of uncountably many transcendentals a much bigger step than any of the others. It isn’t as if we have a that many known transcendentals even now. Most people could probably only name two. Which is a bit short of uncountable.
It isn’t as if this has totally gone away. The constructivist camp of modern mathematics doesn’t have much truck with such numbers.
And of course, there are yet larger sets than even the algebraics, that include pi and e and all the rest of the numbers mathematicians use, but which are still countable sets.
Since of course they’re all the same “size”- countably infinite- what’s the term for broader or more inclusive sets?
The narrower set is a proper subset of the broader set.
Cantor’s Diagonal Argument (CDA) is almost always learned incorrectly. Most deviations from the correct argument are superficial, but some are not. And every objection I have ever seen to it is based on one of them.
It demonstrates that there are sets that have greater cardinality then the infinite set of natural (counting) numbers. The set he used was neither the real numbers, nor their decimal expansions. In the introduction, he literally claimed that the proof he would use does not depend on the irrational numbers at all.
But it relies on the decimal expansions of irrational numbers.
It “relies on” infinite-length binary strings.I call them Cantor Strings. You could use ‘0’ and ‘1’ as the characters, but he used ‘m’ and ‘w’. Cantor didn’t, but you could imagine them as the binary expansions of the reals in [0,1]. However, there is a problem. “10000…” and “01111…” are different Cantor Strings, but both would represent the number one-half.
Is there any way to demonstrate an equivalent proof in non-positional [number] systems?
Not really. The proof depends on identifying the nth position of the nth member of the list, for each member in the list. There could be many ways to define “position,” but it does need that definition. And Cantor Strings are the simplest.
Is there any way that a proof that the number of points on a line is greater than the number of whole numbers could have been shown to the ancient Greek mathematicians like Zeno?
That is essentially Zeno’s Paradox, although I don’t know if he looked at it that way.
+++++
Anyway, here is a rough outline of the correct CDA proof. Symbology is based on what is in Wikipedia.
- Let T be the set of all Cantor Strings.
- Let S be any infinite subset, proper or improper, of T that can be put into a list s1, s2, s3, … . Notice that I do not assume that S = T .
- Technically, he should have included an example here, to prove that such lists exist. There are many trivial ones, like 10000…, 01000…, 001000…, … . The point is that we do not assume the existence of such sets, we know some exist and the following applies to any that do.
- Apply diagonalization to this list, to construct a new Cantor String s0 that is different from every s1, s2, s3, …
- This proves the lemma "If S is a set of Cantor Strings that can be put into a list, then there is a Cantor String s0 that is not in S .
- Now we assume that T can be put into such a list. Then there is a Cantor String t0 that is in T (because T contains every one) and also is not in T (by the lemma). This contradiction disproves the assumption.
Most of the time CDA is taught, the “assumption for contradiction” is made at the beginning, and the alleged contradiction is its negation. That isn’t valid logic, although the reason is subtle. But it is what gives many people heartburn about CDA. The actual contradiction is about the string t0.
+++++
And xtenkfarpl is right - CDA is just a demonstration. The real proof came next, and is called Cantor’s Theorem. It says that the power set of any set A (that is, the set of all possible subsets of A) has greater cardinality than set A itself. What Cantor Strings represent are not numbers, but truth tables defining which natural numbers in N are in each subset.
Everything depends on your definition of real number. From looking at the Wiki article it seems that Cantor was using the Cauchy reals in which every Cauchy sequence converges. If you identify reals as infinite decimals (modulo .99999… = 1) then you get the usual diagonal argument. But the proof that Wiki gives for Cauchy reals is different. The argument goes roughly like this. Let S be a sequence of reals say in the closed interval [0,1]. If either 0 or 1 is missing in S, we can stop here; the list is not complete. Let a_0=0, b_0=1. If the list is complete, let a_1 be the first element of S such that $0<a_1<1 and b_1 the first element of the list for which a_1<b_1<1. Similarly, let a_2 be the first element in the list for which a_1<a_2<b_1 and b_2 be the first element in the list for which a_2<b_2<b_1. Continue in this way to get two sequences
a_0<a_1<a_2<...<a_n<...b_n<...<b_2<b_1<b_0
and every member of the list is either in one of the two sequences or has been bypassed by not being the first such that Now either of the sequences is monotone bounded and can be proven to be a Cauchy sequence, \lim_{n\to\infty}a_n=a and a cannot be on the list since process either uses or bypasses every member of the list.
I imagine a similar argument can be used if you use Dedekind cuts for your reals.
Added: Something has happened to Markdown; every single math shift gets put on a separate line. It didn’t used to do that.
Nothing depends on anybody’s definition of real numbers.
Cantor’s diagonal argument - and by that I mean the actual argument that Georg Cantor made in the paper titled “Uber ein elementare Frage der Mannigfaltigkeitslehre” in 1891 - does not use real numbers. In any way.
“There is a proof of this proposition … which does not depend on considering the irrational numbers.” That’s what he said about them.
What Cantor used, was infinite-length strings using two characters. Those who came later decided it was easier to teach it to High Schoolers as the binary, or sometimes decimal, representations of real numbers. But all it actually uses is the strings, and trying to solve issues related to real numbers is a red herring.
So he was “really” showing that the set of subsets of the positive integers is uncountable. Fair enough. But not the same as showing that the set of points in a real interval is uncountable and that certainly does depend on your definition of the reals. Incidentally, the same argument can be and regularly is used to show that the set of subsets of any set has larger cardinality than the original set.
He never says it, but by all appearances he was demonstrating Cantor’s Theorem for this one specific case. If I remembered more than just a little from my High School German classes, I might be able to correlate Cantor’s symbols (‘m’ and ‘w’) with the concepts of “included in the subset” and “excluded from the subset.”
Right. Unless you can conceive a positional system, that (as OP asks for) could have been shown to Zeno, you can’t use CDA to prove to him “that the number of points on a line is greater than the number of whole numbers.” I doubt that Cauchy sequences qualify.
That’s Cantor’s Theorem. It is in the same paper, but has a different proof. It does not use the positional system we call CDA, even if some people try to call it CDA.
Of course, it’s not hard at all to apply the same argument to real numbers as represented in our positional number system. There are a few subtleties that must be addressed in that case, like 0.999… = 1 (or 0.111… = 1), but those aren’t too difficult (for instance, instead of using base 2, use base 3, and then only ever replace the existing digits with 0 or 1).
Huh? That should equal 1/9
There are 10 kinds of people in the world…