4 ms·

Even Cantor's counterexample, where he traverses the diagonal of an enumerated list of numbers, he has a countable number of choices to pick his digits. So we'

by xscott 2y ago

Even Cantor's counterexample, where he traverses the diagonal of an enumerated list of numbers, he has a countable number of choices to pick his digits. So we've built a countable set, and he claims it's incomplete by picking one number from a countable set of counterexamples. So now lets union the original set with Cantor's countable set of counterexamples, and get a combined set which is also countable, right?

zmgsabst 2y ago
But that schema can be applied to your new set, as well — to create yet more counter examples. Your method didn’t exhaust the real numbers outside the original list. You merely added one of them. For any listable subset of the real numbers, we can provide a counter example. And since we’re proving by contradiction in Cantor’s argument, we assume the original list is exhaustive, ie there’s a bijection between naturals and reals. We show that assumption leads to a contradiction, because there’s at least one real number for which no natural maps to it. Therefore, there can’t be such a bijection. - - - Assume f is a bijection between N and [0,1]. Let an be the nth digit of f(n). Then x = sum(1,inf)[10^-n * (an + 1 % 10)] is a real number in [0, 1] for which there is no f(k) = x. So f is not onto and therefore f is not a bijection. Therefore, no such bijection can exist — by contradiction. - - - You can’t patch that schema up just by adding counter examples to your first choice of bijection — because a counter example is constructable for any bijection attempt. The fundamental problem is that reals include limits — which is what allows the sum to be a real number.
- xscott 2y ago
  I won't claim to have any proof in hand, but there's still something fishy about it all. I think things like Banach-Tarsky and such ought to be treated as counter examples to show the absurdity of the Reals. At times I've thought maybe the problem with diagonalization is forcing me to do a (countably) infinite number of steps before Cantor gets to take an infinite number of steps. For instance, I can give a trivial counting scheme and claim it will eventually generate every number between zero and one, perhaps by writing a program to write programs that generate digits. It's all very deterministic, and I state exactly what I'm doing up front. So I give the first number (program), and Cantor gives his first digit and says it's not in my list. Then I tell Cantor the countably infinite number of places where his first digit is found, and we select those programs. Then he gives me his second digit, and I select the subset where those are found. So we go back and forth, he keeps saying his number so far is not in my list, and I keep telling him all the places where it is in the list... Feels like stalemate there. There are other places (such as summing the alternating harmonic series) where you have to be very careful about the ordering of operations. If he really has a higher order infinity of numbers not in my list, maybe I should be able to ask him for his list first, no? It's uncountably infinite, but he can't provide even one of them.
  - zmgsabst 2y ago
    You don’t have to do anything but assume such a bijection does exist, as in my comment: its existence leads to a contradiction in the presence of limits — just like I showed. But without that same limiting to build sets, you can’t construct N from the successor function and you can’t discuss the power set of N. So we either need to throw out countable limiting to build sets or accept that such set building rules out bijections between reals and naturals. You think Banach-Taraki is weird (as do most people), but I’d argue a world where you have finite numbers or couldn’t discuss the set of subsets of the naturals is even weirder. > maybe I should be able to ask him for his list first, no? There’s no such list indexable by the naturals, as shown by that contradiction. If you allow indexing by the reals, that request is trivial.
    - xscott 2y ago
      You've edited your post a bit from what I originally replied to. Looking at your bijection stuff, I think you're just restating Cantor's diagonalization with `(a_n + 1) % 10` as your mechanism for choosing digits, but maybe I've got that wrong. I appreciate that it's well defined, but I think it ignores my complaint. Let's say I tell you that I'm building my list of numbers between zero and one by taking the natural numbers, reversing the digits, and just putting a decimal place in front: 0: 0.0.... 1: 0.1.... 2: 0.2.... ... 10: 0.01... 11: 0.11... 12: 0.21... It's a silly mapping, and I'm sure there are a few problems with it, but let's start there. For now it doesn't matter what digits I'll choose afterwards - maybe it's all zeros, maybe it repeats the digits, maybe I'll do something more clever, but skip that for now. My list has a number that agrees with your number to any number of digits we choose. You and Cantor have to force me to give my infinite list of numbers all at once, and then build your infinite length counter example all at once. What axiom lets either of us do an infinite number of steps and say we're finished? What axiom says you can do an infinite number of steps after I do my infinite number of steps? When we do limits with deltas and epsilons, we say that we will get closer as we keep going, not that we got there. If you give me the first 1000 digits of your counterexample, I can tell you all the elements in my set that match your number up to the first 1000 digits. If you give me 1001, I can tell you all the places that match that too. A million, a gazillion, I can keep matching. And as you keep adding more digits, I can keep telling you an infinite number of places that match. So it really seems like there's a problem with the order of operations. It's like playing chess, and you force me to make all my moves and come afterward to checkmate me. But if we take turns, where I make a finite number of steps and you give me your next digit, then it's my turn again, I can keep matching you all day and all night.

by xscott 2y ago

zmgsabst 2y ago

But that schema can be applied to your new set, as well — to create yet more counter examples. Your method didn’t exhaust the real numbers outside the original list. You merely added one of them. For any listable subset of the real numbers, we can provide a counter example. And since we’re proving by contradiction in Cantor’s argument, we assume the original list is exhaustive, ie there’s a bijection between naturals and reals. We show that assumption leads to a contradiction, because there’s at least one real number for which no natural maps to it. Therefore, there can’t be such a bijection. - - - Assume f is a bijection between N and [0,1]. Let an be the nth digit of f(n). Then x = sum(1,inf)[10^-n * (an + 1 % 10)] is a real number in [0, 1] for which there is no f(k) = x. So f is not onto and therefore f is not a bijection. Therefore, no such bijection can exist — by contradiction. - - - You can’t patch that schema up just by adding counter examples to your first choice of bijection — because a counter example is constructable for any bijection attempt. The fundamental problem is that reals include limits — which is what allows the sum to be a real number.

xscott 2y ago
I won't claim to have any proof in hand, but there's still something fishy about it all. I think things like Banach-Tarsky and such ought to be treated as counter examples to show the absurdity of the Reals. At times I've thought maybe the problem with diagonalization is forcing me to do a (countably) infinite number of steps before Cantor gets to take an infinite number of steps. For instance, I can give a trivial counting scheme and claim it will eventually generate every number between zero and one, perhaps by writing a program to write programs that generate digits. It's all very deterministic, and I state exactly what I'm doing up front. So I give the first number (program), and Cantor gives his first digit and says it's not in my list. Then I tell Cantor the countably infinite number of places where his first digit is found, and we select those programs. Then he gives me his second digit, and I select the subset where those are found. So we go back and forth, he keeps saying his number so far is not in my list, and I keep telling him all the places where it is in the list... Feels like stalemate there. There are other places (such as summing the alternating harmonic series) where you have to be very careful about the ordering of operations. If he really has a higher order infinity of numbers not in my list, maybe I should be able to ask him for his list first, no? It's uncountably infinite, but he can't provide even one of them.
- zmgsabst 2y ago
  You don’t have to do anything but assume such a bijection does exist, as in my comment: its existence leads to a contradiction in the presence of limits — just like I showed. But without that same limiting to build sets, you can’t construct N from the successor function and you can’t discuss the power set of N. So we either need to throw out countable limiting to build sets or accept that such set building rules out bijections between reals and naturals. You think Banach-Taraki is weird (as do most people), but I’d argue a world where you have finite numbers or couldn’t discuss the set of subsets of the naturals is even weirder. > maybe I should be able to ask him for his list first, no? There’s no such list indexable by the naturals, as shown by that contradiction. If you allow indexing by the reals, that request is trivial.
  - xscott 2y ago
    You've edited your post a bit from what I originally replied to. Looking at your bijection stuff, I think you're just restating Cantor's diagonalization with `(a_n + 1) % 10` as your mechanism for choosing digits, but maybe I've got that wrong. I appreciate that it's well defined, but I think it ignores my complaint. Let's say I tell you that I'm building my list of numbers between zero and one by taking the natural numbers, reversing the digits, and just putting a decimal place in front: 0: 0.0.... 1: 0.1.... 2: 0.2.... ... 10: 0.01... 11: 0.11... 12: 0.21... It's a silly mapping, and I'm sure there are a few problems with it, but let's start there. For now it doesn't matter what digits I'll choose afterwards - maybe it's all zeros, maybe it repeats the digits, maybe I'll do something more clever, but skip that for now. My list has a number that agrees with your number to any number of digits we choose. You and Cantor have to force me to give my infinite list of numbers all at once, and then build your infinite length counter example all at once. What axiom lets either of us do an infinite number of steps and say we're finished? What axiom says you can do an infinite number of steps after I do my infinite number of steps? When we do limits with deltas and epsilons, we say that we will get closer as we keep going, not that we got there. If you give me the first 1000 digits of your counterexample, I can tell you all the elements in my set that match your number up to the first 1000 digits. If you give me 1001, I can tell you all the places that match that too. A million, a gazillion, I can keep matching. And as you keep adding more digits, I can keep telling you an infinite number of places that match. So it really seems like there's a problem with the order of operations. It's like playing chess, and you force me to make all my moves and come afterward to checkmate me. But if we take turns, where I make a finite number of steps and you give me your next digit, then it's my turn again, I can keep matching you all day and all night.