Time for some hard-core geeking-out.
This comment on HN by /u/jiggawatts struck me as a brilliant idea: it's an intuitive counter-example to the axiom of choice, which seem intuitively obvious, but leads to weird results like the Banach-Tarski paradox.
For those of you who are not hard-core geeks, the axiom of choice says (more or less) that if you are given a collection of non-empty sets, you can choose a member from each of those sets. That seems eminently plausible. How could it possibly not be true?
Here's how: consider the set of numbers that cannot be described using any finite collection of symbols. Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers. So not only are there numbers that cannot be described using a finite number of symbols, there are vastly more of these than numbers that can be so described.
And yet... how would you describe such a number? By definition it is not possible! And so it is not at all clear (at least not to me) what it would even mean to "choose" a number from this set.
This is, of course, not a proof that the axiom of choice is wrong. It's an axiom. It can't be wrong. But it is a good example for casting doubt in its intuitive plausibility, and that feels like progress to me.
I wonder if such a set really can exist.
ReplyDeleteFirst, an element that cannot be described by using _any_ finite collection of symbols might not exist. The number of finite collections of symbols is not neccesarity countable (symbols themselves are not really countable: if a symbol is e.g. a trace of a pen on paper, it's a curve in 2D space).
Second, if we can denote the set of these undescribable elements with a symbol, then we can probably agree on a notation for a specific element from this set (a_1), thus creating a paradox. But if thus the set itself can not be noted, then we probably cannot use a collection of non-empty sets including this set, because we'll not be able to write that one down, and thus we won't be able to use the axiom of choice :)
I assume by "description" it means the "definable set" (https://en.wikipedia.org/wiki/Definable_set) or "definable number" (https://en.wikipedia.org/wiki/Definable_real_number) in model theory using some finitary language like FOL. So they have explicit definition in mathematics. It is a countable set by definition, however it is only "countable" under the context of ZFC, which means, by FOL or similar deduction system, there is no deduction of the form ZFC |- exists a 1-1 mapping from N to R-{definable numbers}. On the other hand, it is conservative to have a countable transitive model (ctm) of ZFC (M |= ZFC, and |M| <= |N|), such M |= not exists a 1-1 mapping from N to R-{definable numbers}, but you can construct a 1-1 mapping between N with the relativization of R-{definable numbers} in M (probably with the help of AC).
ReplyDeleteBtw you can have uncountably infinite definable set of numbers using infinitary logic (https://en.wikipedia.org/wiki/Infinitary_logic).
Great start, but I think this misses the final step.
ReplyDeleteThere’s no particular problem with claiming, in isolation, to have picked one element from some infinite collection of non-empty sets. The problem arises when you try to use that to construct an argument or proof.
In each step where your argument depends on the existence of some set of unambiguous specific choices , then, if you are dealing with things like indescribable reals, there is no way, in principle, for the reasons you outline, to check or confirm that you are still talking about the same items.
That is why we need the axiom of choice.
@Unknown:
ReplyDelete> symbols themselves are not really countable
Symbols have to be drawn from a finite set. That is part of the standard definition of a symbol.
@ Kaa1el:
> I assume by "description" it means the "definable set" (https://en.wikipedia.org/wiki/Definable_set) or "definable number" (https://en.wikipedia.org/wiki/Definable_real_number) in model theory using some finitary language like FOL.
I haven't thought this all the way through, but the reason I went with "definable" rather than "computable" was to eliminate uncomputable but definable numbers like Chaitin's constant from the set.
I'll have to think more deeply about the rest of your comment.
@Simon:
> There’s no particular problem with claiming, in isolation, to have picked one element from some infinite collection of non-empty sets.
Sure, just as there is no problem in postulating an oracle for the halting problem. You can assume anything in math. Like I said, the intent here was not to *disprove* the AoC, just to offer an intuition as to how a reasonable person might choose to reject it.
I don't think your example has anything to do with the axiom of choice, which informally states that "given any collection of sets, you can pick an element from each of them". Set theory has no problem picking elements from a _single_ set, even without choice, provided you can prove that it is non-empty!
ReplyDeleteAnd indeed, ordinary set theory (even without choice) proves that the reals are not countable.
You can "construct" a non-describable real as follows using a diagonalization argument: let xi be the real number given by the i'th description in whatever system you like. Then define a real number y by choosing it's i'th digit so that it is different from the i'th digit of xi.
Clearly y is different from any of your describable reals! But I've just described it, so what gives? The trick is that, once you unroll my previous paragraph, y has an infinite description.
Nevertheless I can reason about this real number y just fine, so personally I'm okay with this state of affairs. Maybe your example just highlights the strangeness of allowing infinities into mathematics? It's not to everyone's taste!
Special irrationals like pi and e are described by their specialness. Doesn't the diagonal argument for irrationals being a higher order of infinity depend on the Axiom of Choice? Maybe the problem is not with Choice but continuity.
ReplyDelete[Corrected version]
ReplyDelete@Guy:
> Clearly y is different from any of your describable reals! But I've just described it, so what gives?
What gives is that your original description system "whatever system you like" was incomplete, as all such description systems necessarily are. But that doesn't matter to my argument, which includes *all possible* description systems, including diagonalization. No matter how many times you diagonalize and meta-diagonalize you will still be left with uncountably infinite undescribable reals.
Note that I don't have to actually *construct* this set (that is not possible). All I have to do is prove that it exists and it's not empty. Existence is easy: it's just the complement of the (countable) set of describable reals. And since it's uncountable, it's obviously not empty, QED.
"Describable" depends on a choice of alphabet (basically, any finite set is an alphabet and s symbol is just an element of an alphabet) and grammar for well-formed formulas on that alphabet, and thats completely arbitrary. Non-describable will be more of a limitation of my choice of language than a characteristic of the non-describable object.
ReplyDeleteAnd we do expand alphabets all the time - the real line doesn't include \infty, but instead of saying lim_{x->0+} of 1/x is undefinable we just added \infty to the alphabet.
i think Gödel explored some analogue of this using his evil Cantor diagonal argument variants, but I haven't touched that in 20 years...
Maybe if one formalizes the description of choice functions (a choice over a set X is a function c:2^X->X, the axiom of choice stating that for every X there is at least one choice over X) under some language...
@CientistaNãoAcadêmico:
ReplyDelete> we do expand alphabets all the time
Sure, but they are nonetheless always bounded, which means that the number of possible descriptions is still countable.
@Ron You have not actually proved that such a set, containing all possible descriptions and all possible diagonalizations, exists within set theory. In fact, diagonalization shows that such a set is not definable in set theory!
ReplyDeleteTo put it differently: your counterpoint that my original description system is incomplete is not important: my description of y was given using English, which must be a description system contained in your set, otherwise it does not, as you claim, contain all possible descriptions in all possible description systems.
Or differently: if your set really does contain literally all possible descriptions systems, diagonalisations and meta-diagonalisations, then it cannot be countable, by the same argument!
This is all true even in the realm of definability, not just compatibility. I wrote "construct" because I gave a construction for y, not because I'm thinking about turing machines =)
Nevertheless, this still has nothing to do with the axiom of choice! You can pick elements from non-empty sets just fine in set theory without choice.