# Is there at least one irrational number with the property that it cannot be defined by a finite string of information?

Ok, so maybe that wasn't the best way of phrasing the question, but I think it's specific enough. Let me explain myself a bit more below in case I am wrong.

So I'm assuming (although I've never checked) that the irrational numbers are defined as simply all reals that are not rational.

I'm asking about the existence, then, of an irrational number that has no finite description. I.e, not only does it not have a finite-number or recurring decimal description, but no other description could be made (counting things such as "The ratio of the circumference and diameter of any circle in a Euclidean plane" as finite).

Clearly, there would have to be infinitely many of these and they would have to form continuous connected regions of the real line, otherwise they would afford descriptions such as "The otherwise-non-finitely-describable number lying between x & y" where x & y bound the "otherwise-non-finitely-describable z, and z can be shown to be the only such number between x & y.

If so, then this would have implications for Laplace's Demon and other similar philosophical arguments since it would be mathematically impossible to have knowledge of all of the universe so long as at least one parameter lay within one of these non-finitely-describable regions.

-
@Craig: I noticed that you re-tagged the question as [computability]. But computability and definability are distinct concepts. For instance, Chaitin's constant (for any given choice of encoding) is definable, but not computable. I would re-tag it to [logic], but perhaps there are better options, and in any case I don't want to start a tag war. But [computability] is wrong. – TonyK Sep 7 '11 at 20:02
You're making the groundless and false assumption that either undefinable numbers form continuous connected regions or there are x and y such that there exists only a single undefinable number in [x,y]. You forgot the possibility that they are dense but disconnected (which is the actual truth in the matter). Note all connnected regions of reals are intervals & all intervals contain a rational - which is definable. Also, you should be cautious about your levels of description; formally defining a number as undefinable from a specific set of symbols requires a higher level than those symbols. – anon Sep 7 '11 at 20:24
This reminds me of the All numbers are interesting-theorem, also mentioned by Quinn below, which in this case also "contradicts" the existence of such numbers. – TMM Sep 8 '11 at 0:29
There is a thorough answer to this question at mathoverflow.net/questions/44102/… – Carl Mummert Sep 8 '11 at 0:30
Regarding problems with Laplace's demon: What makes you think all the irrationals — let alone any uncountable set — exist (or even are represented?) within the physical universe? – jwodder Sep 8 '11 at 1:41

Yes, there are such numbers. Chaitin discusses them extensively, he has a popular book on the subject, Meta Math: The Quest for Omega. They do not form continuous connected segments of the real line, because for example, the rationals are dense (that is, between any two real numbers there is at least one rational -- and in fact there are an infinite number of rationals).

However, these non-computable numbers are also dense in the real line.

You might want to take a look at the "computability theory", "definable number", and "analytical hierarchy" articles in Wikipedia.

Note that this doesn't pose as big a problem for the philosophy of physics as you might think: This doesn't say that you cannot measure a physical constant to whatever precision you might wish.

-
Many thanks. Brilliant answer. But your proof (whilst seeming watertight if your statement about, and definition of the density of rationals, is accurate) doesn't address the reasoning I outlined for continuous regions – John-Mark Allen Sep 7 '11 at 20:10
@John-Mark: Craig's exposition is water-tight. You don't need a maths degree to see that between any two real numbers there is a rational number. – TonyK Sep 7 '11 at 20:33
In fact, most reals are not definable. The finite descriptions are countable and the reals are not. It is the same argument that says most reals are irrational or transcendental. – Ross Millikan Sep 7 '11 at 20:40
@Ross: Craig's answer is OK because he only refers to computablity, but cf. mathoverflow.net/questions/44102/… – Carl Mummert Sep 8 '11 at 0:26

Be very careful with such statements. For example, take Berry's paradox: Let n be "The smallest number which can not be described with less than 14 words". Should it exist? Then it has been described with 13 words. The number of descriptions is countable, but the number of reals is not. Therefore, most reals are not finitely describable. Does it imply anything for physics? I don't think so...

-
I imagine there's no serious mechanical implications, but there are philosophical ones (like is the universe able to be simulated by a Turing machine?, i.e. the Church-Turing-Deutsch principle). – anon Sep 7 '11 at 20:32

Of course you'd need to define precisely how the finite string is interpreted, but the answer is yes. There are only countably many strings and uncountably many reals.

-
The Charles, there was a recent MSE question which illicited almost identical answers. I'll have to – The Chaz 2.0 Sep 7 '11 at 20:12
investigate when I get to a computer (the split posts are due to a misclick on the iPhone)! – The Chaz 2.0 Sep 7 '11 at 20:13
@The Chaz, this one? math.stackexchange.com/questions/58036/… – lhf Sep 8 '11 at 0:14
The difficulty with this answer is that there are models of ZFC in which every set is definable. There is a longer explanation at mathoverflow.net/questions/44102/… – Carl Mummert Sep 8 '11 at 0:22
@Ihf: YES! Thanks :) – The Chaz 2.0 Sep 8 '11 at 3:09

To be as generous as possible, allow yourself a countably-infinite alphabet and descriptions of finite (but unbounded) length. This seems to describe the human state of affairs, since we seem to able to create many new ways of describing things, but we certainly don't have an infinite amount of time to read a description.

The set of all possible descriptions arising from this scenario is still only countably infinite. (Proof: Fix an ordering on your alphabet and list all descriptions lexicographically.) Since the reals are uncountable, there are uncountably-many real numbers that admit no description in this sense.

-
Google "indescribable numbers" for more on this idea. – Austin Mohr Sep 7 '11 at 20:07
This argument has the same difficulty as the answer by Charles. – Carl Mummert Sep 8 '11 at 0:24

Your question is too vague, especially regarding your requirement of a finite description. Here's an ostensible paradox that can arise if you're not careful:

Suppose there is a real number that cannot be described by any finite sequence of characters. Further, assume that the reals can be well-ordered. Then the set of all reals with no finite description is nonempty, so must have a least element (with respect to the given well-order). But what we've just given is a "finite description" of a number that's not supposed to have a finite description!

The "paradox" just described is redolent of the interesting number paradox and has the same resolution. The point is that descriptions must be fixed ahead of time; the string "the least (with respect to some well-order of the reals) real number that is not finitely describable", if it describes some number, should describe it before you form the set of all non-finitely-describable elements and hence cannot be used to describe any other. This is an issue of syntax vs. semantics; the string already syntactically describes the real, regardless of what its semantics seem to describe.

Thus your question should really be posed like this: fix a finite alphabet $\Sigma$ sufficient to form any English word, sentence, paragraph, etc.; and a function $f: \Sigma^{*} \to \mathbf{R}$, where $\Sigma^{*}$ denotes the set of all finite words over $\Sigma$. Note that a word in this context might actually be what you or I would really call a sentence, paragraph, etc. Define a description of a real number $r$ to be a word $\sigma \in \Sigma^{*}$ such that $f(\sigma) = r$.

With this precise setup, it is trivial to see that some reals have no description, since the collection of all words over a finite (countably infinite, even) alphabet is countable and the reals are uncountable.

To see concretely why there's now no paradox, consider the (definitely nonempty) set of all reals without a description. This set will still have a least element (with respect to any well-ordering of the reals), but now we cannot say that the string $\sigma=$"the least (with respect to some well-order of the reals) real number that is not finitely describable" describes it, since $\sigma$ is already a description of of some other real number.

Edit. I'd like to see someone come up with a paradox without using a well-ordering of the reals (or any other consequence of the axiom of choice). If no one can, I'll ask it as a separate question.

-
I hate to make the same comment under every answer, but the countability argument has deep issues; compare mathoverflow.net/questions/44102/… – Carl Mummert Sep 8 '11 at 0:27
@Carl But aren't we working in a fixed model of ZFC so that, from our perspective, it is the case that the reals are uncountable whereas the collection of words over a finite alphabet is countable? I mean, even if there are models of ZFC where all reals are definable, the people living in that model who are having a discussion about descriptions of numbers would be able to conclude that some number are not describable by them. – Quinn Culver Sep 8 '11 at 1:00
If every real was definable in a (transitive) model, people in that model couldn't conclude that some real isn't definable, because they have the same formulas as we do, since they have the same natural numbers. The trouble is, even if there are only countably many formulas, because there is no way to construct a map from formulas to the reals they define, we can't actually make the supposed diagonal argument go through to prove there is an undefinable real, even if we also think the reals are uncountable. If we could do it, there would be no model where every real is definable, but there is. – Carl Mummert Sep 8 '11 at 1:11
Your answer is OK because you take a fixed description function $f$; the trouble is that all you can conclude is that there is some $f$-undefinable real number. There is no way to construct the $f$ whose domain is the set of formulas of ZFC and which maps such a formula to the set it defines, or $\emptyset$ if the formula doesn't define a set. So it is naively possible that for every $f$ there is an $f$-undefinable real, but actually every real is defined in the sense of first-order logic by some formula of ZFC, and in fact this does happen in some models. – Carl Mummert Sep 8 '11 at 1:15
@Carl But isn't that what's tacitly meant when someone asks for a finite description? That is, isn't he really asking for a uniform way to describe the reals? – Quinn Culver Sep 8 '11 at 13:54

Formally, we say an object $c$ in a structure $M$ is definable (where the language of $M$ is $L$) iff there is formula $\varphi(x)$ in the language s.t. $M \vDash \exists! x \ \varphi(x)$.

If the language is finite, then the set of formulas in the language is countable, and therefore the set of definable objects is also countable. If $M$ is an uncountable structure, then there are many objects in it that are not definable.

Fix a language for the defining real number. If the language is finite, then there are many real number that is not definable.

Also note that if the language is reasonable (i.e. includes $0$, $1$, $+$, and $.$) then all rational numbers are definable, so all undefinable real numbers in such a language will be irrational.

-
This answer has the same problem as many of the others. There is no way to tell from inside a structure whether it is countable or not, and in fact there are models of ZFC in which every real number and in fact every set is definable, as explained at mathoverflow.net/questions/44102/… – Carl Mummert Sep 8 '11 at 13:34
@Carl, I don't see that as a problem. Obviously we are talking in a meta-language as is usual in mathematics, and in that language the structure is provably uncountable. You are saying that if we consider the meta-language and meta-theory then there is the possibility that there is no uncountable set from the perspective of someone looking from outside because of Lowenheim-Skolem and the limitations of first-order logic, but that is besides the point IMHO. – Kaveh Sep 8 '11 at 20:36
from the perspective of someone inside the theory there is a real number which is not definable. – Kaveh Sep 8 '11 at 20:43
Kaveh: there is a model of ZFC in which, for every set $s$, there is a formula $\phi(x)$ which holds of $s$ and only of $s$. Someone inside the model will recognize that the formula holds of $s$ and only of $s$, so they will recognize that $s$ is definable. As the link I gave explains, the argument that there must be an undefinable real simply because of cardinality reasons cannot be made to work. The place this shows up in your answer is in the claim "the set of definable objects is also countable". How do you form this set? Note that it is consistent for that "set" to be a proper class. – Carl Mummert Sep 8 '11 at 20:48
Right, it does work for set models $M$. The difficulty is only if we try to apply this reasoning to $V$ itself, since this isn't a set model. – Carl Mummert Sep 8 '11 at 21:54

I don't think the set of all such numbers is well-defined. Using particular words to mean one thing makes defining other things more difficult. Is the set of irrationals that can be defined in English the same as the set that can be defined in French or Chinese?

-
"Is the set of irrationals that can be defined in English the same as the set that can be defined in French or Chinese?" One would certainly hope so. Otherwise mathematics is busted. Of course the lengths of the descriptions may vary. – TonyK Sep 7 '11 at 19:21
@TonyK: why? Depending on the logical system (language) the definable numbers are different: see en.wikipedia.org/wiki/Definable_real_number and en.wikipedia.org/wiki/Analytical_hierarchy – Willie Wong Sep 7 '11 at 19:39
@Willie: You can't be serious. Do you think that there are mathematical theorems that can only be understood by speakers of, say, Malayalam? – TonyK Sep 7 '11 at 19:54
I agree with @TonyK. At the least you should be able to embed a translation... – Charles Sep 7 '11 at 20:07
@TonyK, Charles: Not that kind of language, silly. Willie called it a logical system and put "language" in parentheses for a reason. See the links will you two? Also, -1 for you OP: this is misleading. – anon Sep 7 '11 at 20:28