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.
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.
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.
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:
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.
> What axiom lets either of us do an infinite number of steps and say we're finished?
The same one that says we can build the naturals from successors — without that, we don’t have all of the naturals. As I’ve been saying repeatedly, this is due to building sets from induction.
A limit L for an infinite sequence (an) is such that for any epsilon, there’s some n where after that n, | L - an | < epsilon. You have a set of rationals indexed by naturals building towards that real number — but you can do it the other way and define reals as those sets which converge to it.
> And as you keep adding more digits, I can keep telling you an infinite number of places that match.
The reals that are indescribable are truly weird: they look like subsets of N that are infinitely large but exclude infinitely many as well, without any pattern to inclusion or exclusion. And you can show this power set definition matches [0,1] by taking the binary 0 or 1 at position n to be if n is included in that subset.
To get rid of the weird reals, you need to force sequences like that out. What makes the reals larger is that they’re defined to include the limits of all converging sequences. Rationals don’t, eg, sqrt(2) or pi.
> 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.
But this doesn’t end in a bijection, because after you follow this construction for an infinite number of turns, I can name a real number not in your list — as my final move. That’s what the schema says: no matter how we construct the list, after it’s built, I can name a number outside of it. You’re not showing the list is complete, ie includes all reals, merely that we can include a particular number if I tell you it digit by digit — but we knew that by construction (ie, there will always be some countable converging sequence of rationals).
Every real is constructed by some countable sequence of digits; but there’s more real numbers than countable infinity.
> The reals that are indescribable are truly weird [...]
Well, I appreciate your patience. I'm certain I won't find a hole in any of your arguments or the conventional wisdom, but the Reals outside of the Computables (or Defineables might be a better choice) are more than weird, they're absurd. They're dense in the number line but only a countable number of them are anywhere to be found, named, or described past a few digits.
Additionally there is always a Computable number between any two Reals and a Real between any two Computables. *This* ought to imply a one-to-one correspondance, but I'm certain I can't defend that argument either.
As for applied math, any situation where we claim the Reals are required (perhaps as the position of a particle or the coefficients of a wave function or something) is uncomputable. So saying the Reals apply to reality probably says something very weird about determinism too.
They’re a consequence of subsets being more complicated to talk about than the set itself.
Real numbers are weird compared to naturals because the indescribable ones match to subsets with infinite complexity. But functions on the real numbers are similarly large compared to the reals themselves — because they can have any subset of reals as their output, including infinitely complex ones.
> This ought to imply a one-to-one correspondance, but I'm certain I can't defend that argument either.
The interval is like a fractal: between any two points is a full copy of it. And for any prefix there’s a lot more “and then the tail is infinitely weird” than coherent tails.
> So saying the Reals apply to reality probably says something very weird about determinism too.
Math is a model.
Nothing we compute can’t be don’t purely over computable numbers — but you simplify a lot of proofs if you work in the space where every convergent sequence has a limit, then just approximate. Including proving that approximations work nicely.
You’re not making a claim about reality; you’re simplifying your mathematical machinery by packing all of the badness into a few technical axioms about induction — and then just shrugging because Banach-Tarski paradoxes are probably unphysical and purely a construction of the model.
Btw, I wasn't saying to just add one of Cantor's numbers. His mechanism for picking diagonals, whatever it is, is a countable list. He picks a first digit to disagree with the first digit of my first number: That gives him 9 choices. He picks a second digit, another 9 choices. It grows exponentially, but I can make a one-to-one mapping for all (any) of his choices, so ALL of his numbers come from a countable set.
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.