Is there an example for an undefinable number?

This question is motivated by a comment of Robert on the question Can any Real number be typed in a computer? :

Can you "think of" an undefinable number? – Robert Israel

I would like to reformulate this (ironic) question to:

Can you give an (concrete) example for an undefinable number?

My first guess would be "No!" because when you give an example of a number you need a definition for it which contradicts that the number shall be undefinable. But we are talking about mathematics and I learned that the first guess is not always true ;-) So I can imagine that finally the answer is "Yes" to the above question (maybe it is possible to give an undefinable number in first order logic by using higher order logic).

Note: I mean "undefinable" in the sense "undefinable in first order logic".

Solution 1:

You say you mean "undefinable" in the sense "undefinable in first order logic," but this is still ambiguous: what is the language (i.e., the collection of non-logical symbols) you are using?

For instance:

• ${1\over 2}$ is undefinable in $(\mathbb{R}; +)$.

• $e$ is undefinable in $(\mathbb{R}; +, \times)$.

• $\pi$ is (almost certainly :P) undefinable in $(\mathbb{R}; +, \times, exp)$.

And so forth.

There are even some examples which may seem to strain the limits of possibility:

• Fix a countable language $\Sigma$, and enumerate the $\Sigma$-formulas as $\varphi_i$. Let $r$ be the real whose $n$th bit (in binary) is $0$ iff $\varphi_n$ holds of some real whose $n$th binary bit is $1$. Then I have "defined" $r$, in a language larger than $\Sigma$, but still somehow "$\Sigma$-ish."

• Much more weirdly: Suppose there is a definable well-ordering of the reals - this is a consequence of e.g. $V=L$. Then there is a least (according to this well-ordering) real which is not definable in the language of set theory$^*$! The reason this isn't a contradiction is that "definable" isn't definable. :P Nonetheless, in some sense I have "given" you a real . . .

And, of course, there is no real which is "absolutely" undefinable: we can always expand the language to include a constant for that particular real!

(A natural question at this point is to ask whether there is a sense in which some reals are "more definable" than others. Depending how you ask this, you wind up in computability theory, descriptive set theory, model theory, . . . )

$^*$I'm assuming that we're working with the true reals, or at least a model which is well-founded and whose $\mathbb{R}$ is truly uncountable; beware of weird countable models, e.g. the pointwise definable ones (http://arxiv.org/abs/1105.4597)!

Solution 2:

If the choice of language is the type of language we use in everyday life, Ian Stewart's How to Cut a Cake gives the example of Richard's paradox:

"In the English language, some sentences define positive integers and others do not. For example 'The year of the Declaration of Independence' defines the number 1776, whereas 'The historical significance of the Declaration of Independence' does not define a number. So what about this sentence: 'The smallest number that cannot be defined by a sentence in the English language containing fewer than twenty words.' Observe that whatever this number may be, we have just defined it using a sentence in the English language containing only nineteen words. Oops."

Of course, this can also be extended to Spanish, French, German, etc., instead of just English.

Solution 3:

As in non-recursive? There are lots. At a higher level of complexity, index the sentences of arithmetic in one of the usual ways. Let $u$ be the number whose $n$-th decimal digit is $1$ if $n$ is not the index of a sentence, $2$ if $n$ is the index of a sentence true in the natural numbers, and $3$ if $n$ is the index of a sentence false in the natural numbers. Then $u$ is an undefinable real, by Tarski's result on the undefinability of truth of arithmetical sentences.