What was intended to be a short throwaway blog post about someone else's nifty idea regarding the Axiom of Choice (AoC) ended up getting a lot more attention and being much more widely misunderstood than I ever expected, so I decided to follow up with a more detailed explanation.
Note that I deliberately chose the word "detailed" and not "rigorous". Although I am going to try to be a little more rigorous as well, this is emphatically not a "proof" of anything, and particularly not a proof that the AoC is "wrong". Such a proof is not possible. The AoC is, as its name implies, an axiom. It is a free choice to do mathematics with it or without it, and either choice leads to some weird results. This is simply an informal argument that the AoC is not self-evidently true. It is analogous to someone before Gauss saying about Euclid's fifth postulate, "Suppose we tried to do geometry on the surface of a sphere..."
The AoC sounds innocuous enough when you first hear it: given a collection of non-empty sets, it is possible to construct a new set whose members consist of one member chosen from each of the given sets. How could this not be true? Note that this question is analogous to: Euclid's fifth postulate says that given a line an a point not on that line, you can construct a unique line parallel to the given line. How could this not be true? And the answer is: it can be non-true if you are doing geometry on a curved surface.
The answer in the case of the AoC is something like: it can be not-true if the sets you are dealing with are really weird. My post was an attempt to give a specific example of that kind of weirdness. I ended up tripping over playing too fast-and-loose with the notion of "describable". So here I am going to take another whack at it, trying to be a little less sloppy. Note that less-sloppy does not mean rigorous. Like I said, this is not an attempt to prove anything, notwithstanding that parts of what I am about to say might sound a bit like a proof.
So with that in mind, let us start with a few elementary observations.
1. There are at most a countably infinite number of finite-length unicode strings.
2. Some unicode strings are unambiguous descriptions of numbers under certain uncontroversial background assumptions. Examples include "123", "pi", "e", "the successor of zero", and "the golden ratio". Other unicode strings are unambiguously not unambiguous descriptions of numbers. Examples include "hamburger", "irvnwoihdphweg" and "😱". And still other unicode strings may or may not be unambiguous descriptions of numbers. An example of this is "the smallest counter-example to the Goldbach conjecture." That might be an unambiguous description of a number, or it might not, depending on whether the Goldbach conjecture is true.
A lot of the discussion generated by my original post turned on this last point, that it is very hard, arguably impossible, to pin down what an "unambiguous description of a number" actually means. The meaning of "unambiguous description of a number" is ambiguous. But this will turn out not to matter.
Here are a few more observations that will turn out not to matter. I include them just to short-circuit some of the discussion.
3. All computable numbers have unambiguous descriptions, to wit, the algorithms that compute them.
Note that unambiguous descriptions need not be unique. "One", "1" and "the successor of zero" are all unambiguous descriptions of the same number. Two different algorithms that compute the same (computable) number are each an unambiguous description of that number.
It is tempting to conclude that the number of unambiguously describable numbers must be strictly less than the number of computable numbers, except that...
4. Some uncomputable numbers have unambiguous descriptions. Chaitin's constant is the canonical example. It is not known (and probably unknowable) how many uncomputable numbers have unambiguous descriptions.
So now we get to the thorniest bit. Some commenters claimed that:
5. It is not possible to give an unambiguous description of what an "unambiguous description of a number" means, because any such putative description is subject to Cantor's famous diagonalization argument. In this case the argument goes like this: suppose we had an unambiguous description of what an unambiguous description means. Then we could make an (infinite) list of all the numbers with unambiguous descriptions, and then construct a new number with an unambiguous description that is not on that list.
This is true, but I claim it is irrelevant for two reasons. First and foremost, I don't need an unambiguous description of unambiguous descriptions for my argument to hold. All I need is to show that there exist numbers that do not have any unambiguous description, and for that all I need to show is that the number of numbers with unambiguous descriptions is (at most) countable, and all I need for that is to stipulate that an unambiguous description must be renderable as a finite-length unicode string. The number of finite-length unicode strings is countable, and so the number of unambiguous descriptions must be countable, and so the number of numbers with unambiguous descriptions must be countable. But since the reals are uncountable, there must remain an uncountable number of reals with no unambiguous description, at least not one that is renderable as a finite-length unicode string.
So I don't need an unambiguous description of unambiguous descriptions. All I need is an oracle for it, and any oracle will do.
That is sufficient reason that diagonalization doesn't matter, but since this is an informal argument I'm going to point out something else: Cantor originally advanced diagonalization to prove that the reals are uncountable. Far from invalidating my argument, I am actually relying on that result! The whole point is that it doesn't matter what an unambiguous definition actually is, or that we can't necessarily tell whether a given unicode string is one or not (c.f. "the smallest counter-example to Goldbach's conjecture"). We have some strings that are (by social convention) unambiguously unambiguous descriptions (which I am now going to start abbreviating UDs), and others that are unambiguously not UDs, and still others that might be or might not. None of this matters. Take any description of what it means to be a UD and I will happily stipulate that the Nth diagonalization of the list of numbers generated by that specification is also a number with a UD, and so the original specification must have been incomplete or even inconsistent. You can only diagonalize a countable number of times, which is the whole point of the diagonalization argument. If you think that diagonalization invalidates my position, then you either don't understand diagonalization, or you don't understand the argument I am advancing.
None of the above matters, because the conclusion I am trying to defend has nothing to do with the details of what it means to be UD. My claim, which I would have thought would be obvious and wholly uncontroversial, is that there must exist an uncountable number of numbers that unambiguously do NOT have unambiguous descriptions under ANY reasonable definition of an unambiguous description. And the argument for that is simply that the reals are uncountable, but any reasonable definition of unambiguous description will yield only a countable number of them, and hence only a countable number of numbers they can possibly describe.
I could even go meta and point out that a reasonable condition on reasonable definitions of unambiguous descriptions (or anything else for that matter) is that they be renderable as a finite string of unicode characters, and so there can be at most a countable number of "reasonable" definitions of UD. No matter how you slice it, you are still left with an uncountable number of numbers that unambiguously lack any unambiguous description.
Henceforth I will adopt the abbreviation NULUD for Number Unambiguously Lacking an Unambiguous Description. So there are an uncountable number of NULUDs. The NULUDs are a proper subset of the set of uncomputable numbers.
OK, but so what? So there are an uncountable number of NULUDs. How does that cast doubt on the validity of the axiom of choice?
Well, imagine that I gave you two NULUDs and asked you if they were equal. Think about that for a moment. For starters, what would it even mean for me to "give" you two such numbers? I can never actually exhibit a NULUD, or even describe one. I can't write one down. I can't given you an algorithm to compute one. There is no way for me to communicate any NULUD to you by finite means. For me to even contemplate "giving" you two NULUDs I have to do something like postulate some sort of oracle for them which offers finite clues about their identities, something like spitting out successive digits of their decimal expansions. But then what? You could start comparing the outputs of the oracles, and if the numbers are not equal you will eventually find out. But if they are equal you will never know! Comparing NULUDs for equality is analogous to trying to solve the halting problem by running the program and waiting to see if it halts. So not only do you need to postulate oracles for the numbers themselves, you have to postulate an oracle for their equality! That's an awful lot of postulating.
In fact, an oracle for equality of two NULUDs is a mighty powerful oracle. Such an oracle is even more powerful than an oracle for the halting problem, which only has to deal with computable numbers (of which there are only countably many).
What does any of this have to do with the AoC? Well, if you are going to "choose" a number from a set you need to be able to determine whether the number you chose is a member of the set, i.e. whether or not it is equal to a member of the set. To do that for a set of NULUDs you need an oracle for equality of NULUDs, which means you need an oracle that is more powerful than an oracle for the halting problem.
So you see, asking someone to accept the AoC for all sets is asking an awful lot. The AoC hides a lot of power.
But let us grant ourselves all of this extraordinary oracular power. I claim that you will still not be able to describe a procedure by which you can choose a member of an arbitrary set of NULUDs. Again, think about it. You can't just treat the set like a bag where you can just reach in and grab some of its contents. The contents of a set of NULUDs is a bunch of things that can't be described, and so the set itself cannot be described. The best you can do, given what we have allowed ourselves, is to somehow pick an arbitrary NULUD and invoke the equality oracle on every member of the set to see if you got lucky. That process is not guaranteed to converge.
Now, a mathematician (as opposed to a computer scientist like me) would read the above talk of oracles and procedures and say that this is all rubbish, that all I need to do to "give" you two NULUDs is to say, "Let x and y be two (un)equal NULUDs." And what we need for the AoC is not a procedure but a function, specifically a choice function. And here, they will say, there is no problem because there are many functions that can be defined perfectly well on NULUDs. f(x) = x+1 for example.
I don't deny this. But defining a function on NULUDs is not the same thing as defining a choice function. A choice function is not a function on NULUDs, it is a function on arbitrary sets of NULUDs whose value is a NULUD that is guaranteed to be a member of the set. That is a very tall order. I challenge anyone to come up with a description of such a function, even an informal one, that does not invoke the AoC. (That would, of course, be cheating.) And if no one can come up with a description of such a function, a reasonable person could hypothesize that this is because such a function does not exist. Indeed, the AoC exists because the only way we can produce such a function in some circumstances is by postulating it. If we could describe a choice function for all circumstances, we would not need the AoC. Of course, I cannot prove that NULUDs are such a circumstance, but it seems plausible to me. I can't even begin to imagine how you would do it. (But maybe some mathematician out there can enlighten me.)
Of course, none of this disproves the AoC. Like I said at the beginning, the AoC is not false (at least not under standard set theory). My point here is just to describe a set of circumstances under which it is not self-evidently true.
No comments:
Post a Comment