Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Loosely, a number is describable if it can be unambiguously defined by a finite string over a finite alphabet. Numbers such as $\frac{1}{3}$, $\sum_{n=0}^\infty \frac{1}{n!}$, and "the ratio of circumference to diameter of a circle" are all describable numbers. One can show that the set of all such numbers is countable.

Let $U$ be the set of indescribable real numbers. I "claim" $U$ is empty, and so every real number is describable. Suppose to the contrary. Place a well-order on $U$ (this can be done assuming the Axiom of Choice). The least element $u$ of $U$ admits the description "the least element of $U$ according to the specified well-order", contradicting the indescribability of $u$.

Obviously, something has gone awry here. I suspect it is some combination of my loose definition of describability and my self-referential "description" of $u$. My (slightly open-ended) question is "What's wrong here?".

P.S. There is a blog post addressing something rather like my question. As I understand it, the author's response is "the given description isn't really a description". If so, I'd enjoy some elaboration.

share|improve this question
    
I'm not sure if I had this discussion on the chat some long aeons ago, or was there a question about this some aeons ago on the main site. –  Asaf Karagila Dec 2 '12 at 23:57
7  
See Berry's Paradox ... en.wikipedia.org/wiki/Berry_paradox –  GEdgar Dec 3 '12 at 0:02
    
You were right, my argument was not sound, and there are far more better answers now. –  dtldarek Dec 3 '12 at 0:12
1  
Does the fact that it can be ordered lexicographically really mean that it is countable?? –  Tengu Dec 3 '12 at 0:23
    
@Tengu: Where did lexicographically enter the picture? If you mean to imply that the fallacy here is that there are uncountable well-orders, note that the fallacy is rather that we use the well-ordering to generate more names, so paradoxically we can find a name for every number even if there are uncountably many of them. Because names are finite, this means there are only countably many of them so $U$ was countable to begin with. –  Asaf Karagila Dec 3 '12 at 0:31
show 7 more comments

3 Answers

up vote 17 down vote accepted

But you did not describe the well-ordering of $U$. You merely described the fact that it exists.

You extended your language, and this allowed you to describe another countable set of numbers. Alas repeating the argument until exhausting $U$ would require an uncountable number of iteration, and by that point the language is no longer finite.


Let me give a slightly more advanced analogy. One could argue that in $L$ (Godel's constructible universe) everything is definable including the well-ordering of $\mathbb R$. Recall that GCH holds in $L$ and for every countable $\alpha$ there are new real numbers added in $L_\alpha$, so the construction of the real number is not exhausted until $L_{\omega_1}$.

But in the construction of $L$ we allow parameters which were previously constructed to be used. This allows us to extend our language, so to speak, and by that to generate another countable set of real numbers. In order to exhaust the entire collection of real numbers we had to get to $L_{\omega_1}$, that is to say that we had to make uncountably many steps. So no countable iteration covered everything.

share|improve this answer
2  
In particular, the "extension" is by the use of some well ordering that does exist but which may not itself be describable in terms of the numbers that have already been described. –  Carl Mummert Dec 3 '12 at 0:05
    
Carl, yes. Exactly. –  Asaf Karagila Dec 3 '12 at 0:05
2  
The construction of $L$ allows not only parameters that are previously-constructed, but arbitrary ordinals, which you don't even need to provide individual descriptions for -- they're given to you for free! (Or alternatively you could say that you get each of them successively from the same description: "wrap up all ordinals we've seen so far as a set, please"). –  Henning Makholm Dec 3 '12 at 0:31
    
@Carl, I wanted to add this but I was having second thoughts: The predicate "cannot be described" is itself undefinable internally, and we can only define it externally. Or at least it cannot be recognized internally (much like we may have a model which knows about the set of true formulas of itself, but does not know that this set is the set of true formulas). Am I correct? –  Asaf Karagila Dec 3 '12 at 0:37
    
@Asaf: I would say it's not so much that the set is unrecognizable as it is that there's not a formula of set theory to even express the property we want to recognize. Compare the way we make the elementary diagram for a countable model: we begin with the atomic diagram and then repeatedly take the Turing jump of it. Each jump allows us to decide formulas with one more quantifier; the $\omega$th jump allows us to decide the whole elementary diagram. In the context of set theory the atomic diagram of a model is not even a set, internally to that model, so we can't even get off the ground. –  Carl Mummert Dec 3 '12 at 1:19
show 9 more comments

Besides the issue with the axiom of choice possibly giving you an undefinable well ordering, there is still the usual issue that "unambiguously defined by a finite string over a finite alphabet" does not succeed in defining a set of real numbers. The actual set existence axiom in set theory only allows you to form a set of real numbers if the set is definable by a formula of set theory. The quoted phrase cannot, in fact, be expressed by a formula of set theory.

There is a very thorough answer by Joel David Hamkins located here, which explains the situation in more detail.

share|improve this answer
add comment

The problem is with your description “the least element of $U$ according to the specified well-order”. In fact you don’t have a specified well-order here: after all, you needed the Axiom of Choice even to show that such a well-order exists. Since the well-order is not specified, you are not describing a particular element of $U$; in other words your description isn’t really a description at all.

Actually, I suspect that with the appropriate amount of care your argument could be made into a proof that $U$ cannot be well-ordered without using the Axiom of Choice (since your argument shows there is no constructible well-ordering).

share|improve this answer
    
But what about a universe like $L$ where there is a canonical well-ordering of the universe? In such universe of sets $U$ can be well-ordered in a "relatively" definable way, which is sufficient to agree that we may include this canonical order in our language. –  Asaf Karagila Dec 3 '12 at 0:11
    
@AsafKaragila Thank you. I see I was mistaken. –  Robin Houston Dec 3 '12 at 9:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.