13
$\begingroup$

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".

Improve this question
$\endgroup$
  • 3
    $\begingroup$ You might find more information if you drop "undefinable" and use "non-computable", and I refer you to en.wikipedia.org/wiki/Chaitin's_constant and related topics. This is just another example of uncountable infinity brushing up against intuition, and it can be resolved if you're willing to read some of the excellent resources out there. But computability is a gold mine for this question. $\endgroup$ – Eric Tressler Nov 8 '15 at 23:05
  • 1
    $\begingroup$ Note that the notion of definability makes sense only relatively to a structure. (or when the thing whose definability you are questionning is actually definable) $\endgroup$ – nombre Nov 8 '15 at 23:41
  • 1
    $\begingroup$ First order logic over what structure? Over $\langle\Bbb R,<\rangle$? Every number is undefinable over that structure. Over $\langle\Bbb R,+,\cdot,0,1,<\rangle$? You can show that the definable numbers are exactly the algebraic reals. Over $\langle\Bbb R,\pi\rangle$? You can show that anything other than $\pi$ is undefinable. Or maybe first-order definable in the universe of set theory, in which case you are running into a quagmire from which there is little escape. $\endgroup$ – Asaf Karagila♦ Nov 9 '15 at 10:44
  • $\begingroup$ @AsafKaragila: Why it is quagmire if I would use the structure of ZFC? $\endgroup$ – Stephan Kulla Nov 9 '15 at 18:12
  • 1
    $\begingroup$ Almost. It is consistent with ZFC that every real number (and in fact every set) is definable with a first-order definition in the language of set theory which includes a single binary relation $\in$. But it is also consistent that there are non-definable real numbers as well. $\endgroup$ – Asaf Karagila♦ Nov 9 '15 at 18:22
21
$\begingroup$

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)!

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ @Nate: No, because there's an automorphism that fixes only $0$ (namely multiplication by any real not in $\{0,1\}$). $\endgroup$ – hmakholm left over Monica Nov 8 '15 at 23:41
  • 1
    $\begingroup$ What do you mean by "true" reals or "truly" uncountable? $\endgroup$ – user2357112 supports Monica Nov 8 '15 at 23:49
  • 2
    $\begingroup$ By true I mean, well, true - i.e., not a countable model, but the actual reals. Similarly with "truly uncountable." I.e., I'm assuming the existence of a "background universe" $V$ of set theory, and I mean the reals in $V$ or uncountable in $V$. If you dislike talk of the "true" universe of set theory, that's perfectly reasonable - I do too, much of the time - but it's very convenient language to describe how, the "nicer" a model of ZFC+V=L is, the weirder a phenomenon occurs. $\endgroup$ – Noah Schweber Nov 8 '15 at 23:53
  • 1
    $\begingroup$ Am I right in guessing that both $\pi$ and $e$ are definable in $(\Bbb R;+,\times,<)$? (Since, with $<$, we can define limits.) $\endgroup$ – Akiva Weinberger Nov 9 '15 at 1:30
  • 2
    $\begingroup$ @AkivaWeinberger No, they're not - "definable" here means "definable by a first-order formula." The issue, basically, is that to describe a sequence for $\pi$, you need an infinitely long formula. Now on the one hand it's not really that bad - $\pi, e$, and basically every real you've ever heard of are definable by computable infinitary first-order formulas - but it's still not first-order. (Also, side note: the ordering is already definable once we have $+$ and $\times$, since $x>y\iff \exists z(z\times z=x-y)$.) $\endgroup$ – Noah Schweber Nov 9 '15 at 2:23
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ But you can't prove that $u$ exists. $\endgroup$ – nombre Nov 8 '15 at 23:32
  • $\begingroup$ The definition is of a standard mathematical kind. One can take the point of view that the only objects that exist are the ones for which we can provide a constructive proof, but that is very much a minority point of view. $\endgroup$ – André Nicolas Nov 8 '15 at 23:37
  • $\begingroup$ @nombre Why not? $T$ isn't definable, but it exists, and then all that's needed is that the three sets partition $\mathbb{N}$ (which is true by definition). $\endgroup$ – Steven Stadnicki Nov 8 '15 at 23:40
  • $\begingroup$ Well, how would you prove that $u$ (or $T$) exists? $\endgroup$ – nombre Nov 9 '15 at 0:02
  • 1
    $\begingroup$ @nombre Of course it depends what your axioms are, but e.g. ZFC is more than enough to prove the existence of $u$, since in ZFC we can define truth or falsity of first-order sentences in (set-sized) structures. $\endgroup$ – Noah Schweber Nov 9 '15 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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