Unknowable Numbers
Unknowable NumbersThesis: Consider finite specifications of real numbers. Each is done using a string, either explicitly or as a program. These are countable, and even the programs can produce only countable outputs. Since the reals are uncountable, there are uncountably many reals that we cannot specify, even in principle.
MichaelChermside nominates the term "Unknowable" for these, and is interested in pursuing this idea further.
NOTE: While I place this in the public domain (or at least grant it to Ward to do with as he pleases ;-] ), and I welcome... no, ENCOURAGE contributions, enhancements, and refactoring, I would appreciate it if I could get some of the credit, at least until I find someone else who said it first. And when that happens I'll switch to their terminology. -- MichaelChermside
Certainly there are things we can say. Consider unknowable reals. We can say they are reals. We can say they are unknowable (undefinable). From a mathematical theory perspective, where existence predicated upon consistent abstraction, you can prove they 'must' exist. OTOH, from a computation theory perspective, where 'existence' is predicated by proofs over describable computation, undefinable numbers don't exist. You'll never receive one. You'll never send one. You'll never compute one. Computation theory is quite a bit more practical than math theory.
Ground Rules: Valid vs invalid specifications:
Here are some "valid" specifications for the same number:
Questions to be picked up in the discussion:
Question 1: Are the number of number specifications countable or uncountable? (see AreTheSpecifiableRealsWellDefined)
Question 2: What if uncountably long specifications are allowed? (see NumberSpecificationsAndTuringMachines)
Question 3: Is there at least one real number that simply cannot be specified? (if so, there are probably uncountably many such)
Question 4: Is there a relationship between undefinable numbers and the HaltingProblem?
There are more lurking below.
Theorem 1: The set of real numbers which can be specified is countable.
Proof: This is trivially true, given the countability of the mechanisms of specification available to us.
Responses:
Both VickiKerr and RichardKulisz disagree (in a sense).
Vicki offers that applying 'diagonalization' to the countable set of specifiable reals seemingly gives a contradiction (BerrysParadox). (Strictly, Richard's paradox is closer, but the two are logically very similar.) Vicki is not saying that the knowable reals are uncountable. See AreTheSpecifiableRealsWellDefined. For an overview of self-referential "paradoxes", see http://www.utm.edu/research/iep/p/par-log.htm#self, but it's a little informal.
Richard generalizes to infinite specifications, eg., Turing machine programs (of countable length), hence specifying all reals, but not all subsets of the reals. This discussion is moved off to NumberSpecificationsAndTuringMachines.
Theorem 2: You cannot specify a finite set of unknowable numbers.
Assume the theorem to be false, so S is a well-defined set of unknowable numbers with a finite number of elements. Then let j be the smallest of these. The specification "The smallest element of the set S.", combined with a definition for S, is a clear and unambiguous specification of the number j. But this makes j not an unknowable number, and contradicts the assumption, proving the theorem.
I would LIKE to prove that you can't construct (specify) a COUNTABLE set of unknowable numbers... but I haven't been able to do so or find a counterexample. If it were impossible, that would mean that all (finitely-specified) sets which include unknowable numbers are uncountable, while all which don't are countable (by theorem 1). This would make unknowable numbers the very essence of uncountability. Even if this cannot be proved, the very concept of unknowable numbers is very challenging. Does a number which you can never write down... can never describe to anyone... can never even think of (and still be certain you're thinking of the particular one that you mean)... does such a number really exist"? -- MichaelChermside
Responses:
AlistairCockburn says: I think you have a bit of self-circularity in your reasoning... you say, "If I could finitely specify one, it wouldn't be unknowable." But that is simply tautological.
(AC's point is another route to BerrysParadox (see previous link).)
[AC please note - there is no smallest real in an open interval. (Ah, I take it you don't care for humor in math discussions. -- ac)]
In this case, the things we are measuring the complexity of are real numbers. We could ask that the TuringMachine output the number in binary on its tape. A machine that output 1/2 would be VERY simple... just print a 1 then move right printing 0's. A machine that output Pi/10 would also be quite simple, as there are simple algorithms for generating the digits of Pi. A program that output the digits of 987394832/(1227904844 * Sqrt(91)) would probably have to be a bit longer.
The UnknowableNumbers described here would necessarily be impossible to generate (from finite input) with a finite TuringMachine program (if it were possible, the program would serve as a specification for the number). However, the set of "UncomputableNumbers?" may not be the same as the "UnknowableNumbers" as there may be some numbers which can be specified (*), but not computed. For instance, suppose I can prove that one and only one real number has a special property, but I prove it in a non-constructive manner, so I know the number can exist, but I can't necessarily find what it is. Then I can say "The number that has property x", along with a description of the property, and it will serve as a specification... but give no procedure for computing the number. Can anyone think of an example of a non-constructive proof that some property is possessed by a unique, non-rational real number?
[* A number giving the solution to the HaltingProblem would not be computable, but could have a 'defined' (though unknown!) value. -- vk]
So UnknowableNumbers would have an infinite KolmogorovComplexity, but not all numbers with infinite KolmogorovComplexity would be unknowable.
Attempts to describe an unknowable / undefinable number:
A random digit in every place. sum of x:(1->infinity) [rnd(10)/10^x] where rnd(10) is independently evaluated for each value of x. It seems to be computable, clearly bounded in the set of real numbers and unknowable. -- AndyPierce
If you're talking about one particular number that will be randomly selected when this definition is used once, at some well-defined point in the future, then it falls under "These aren't specifications: The number I'm thinking of right now." - given at the top of the page. -- JeffGrigg
The smallest positive real. This is not a valid specification, since no such real exists. If it did, it couldn't be divided by two!
Halting Problem. Knowing which numbers are knowable seems to be the same problem as knowing which general recursive functions terminate. Of course, then you had a list, you could always apply a diagonalization method to it to get a new, clearly knowable(*) number. Does this prove that a gloop program could be written to compute every real number, and as such there would have to be uncountably many, thus conclusively showing gloop is impossible to express in terms of strings? -- JoshuaGrosse [* No. That's Berry's paradox again. See previous link. -- vk]
I mean gloop in the sense of BloopFloopAndGloop: something to solve the halting problem. Btw, your program to find every real will not work. Its output, no matter how long I wait, will be finite, so it will only ever approach a countable infinite. There are more real numbers than that. Why, that's the whole point of this page! :)
non-constructive specifications:
Interjection: non-constructive specifications still don't let you cover all the real numbers, since no matter what spec system you use, you only have countably many possible specifications.
What is this page about anyways? About a trivial theorem in mathematical logic wrapped up in several layers of indirection and put into "intuitive" wording so that people can oooh and aaah at it as if it were remotely significant? I expect more for some reason. -- RichardKulisz
I think the point of this page is that the power set axiom is fundamentally non-constructive, which is pretty neat, IMO - shows the axiom of choice is in good company. Doesn't that say something significant about the philosophy of constructivism? Though I must agree, the response is surprisingly large. -- JoshuaGrosse
The power set of an infinite set is itself specifiable. However, at this point we run into the problems laid forth above: most of the elements of the power set are not. This opens the door to problems like the continuum hypothesis. From a constructivist point of view, it should throw the existence of the power set into question, and I think might even force you to the belief that only countable infinites exist. But Kroenecker never did like Cantor's work anyways.
Is it pretty much some luck-of-the-draw which reals get specified and which don't? -- Alistair
It depends on what kind of alphabet you're using. If the symbols in your language are drawn from a countably infinite set then there are reals which are simply unspecifiable. Intuitively, you might be changing the system you're using but you can only do so in a countably infinite number of ways. The union of a countably infinite number of countably infinite sets is still merely countably infinite. If your alphabet is uncountably infinite then you can specify all the reals. But it also lets you generate a bigger set of numbers which you can't specify.
Reals are defined in terms of sets of rationals. The usual approach is to identify a real number with what will end up being the set of all rationals greater than it, called a DedekindCut?. Basically this means that the reals are defined as topological rather than algebraic closure of the rationals. See also: JohnHortonConway's OnNumbersAndGames.
Some reals may be definable using one set of axioms, but not definable using another set. MC wanted to consider all the finitely definable reals, but that requires using all valid finite sets of axioms. The question is whether you can do that without getting into the type of difficulty known as Berry's paradox. -- vk
Ah, I was thinking of one set of axioms, and hadn't considered collecting the output of all sets of axioms. That gets rid of the luck factor. -- Alistair
all valid finite sets of axioms
Yes, and there's a countable number of those and if each of them yields a countable number of definable reals then their union gives you a countable number of definable reals. Whether or not you allow that set (and I see no reason why not as long as each set of axioms is self-contained) doesn't change the fact that there are uncountably many reals which are undefinable using any finite axiomatic system. If you could have a countably infinite number of axioms (and GoedelsIncompletenessTheorem proves this is meaningful) then you'd have an uncountably infinite number of axiomatic systems ... is there a reason we're limiting it to finite axiomatic systems? -- rk
Ah, but then you couldn't say which particular system you were using to specify any particular number... (AC)
Thesis 3: From MichaelChermside: I maintain that the UnknowableNumbers more-or-less define the boundary between countable sets of real numbers and uncountable sets. Specifically I claim (but I'm not sure I can rigorously prove) that any finitely-specified set of real numbers which DOES contain some unknowable numbers will be uncountable, while any such set which does NOT contain any unknowable numbers will be countable.
So what is meant by "countable?" And what is meant by "specify?" I don't think integers are any more countable than reals, and that real numbers are defined within mathematics.
The real numbers have several equivalent definitions and constructions, the most straightforward probably being that in terms of DedekindCut?s. Try reading http://www.math.vanderbilt.edu/~schectex/courses/thereals/. Countable means that a set can be put into one-to-one correspondence with the natural numbers. You can't match up finite sets to proper subsets of themselves, but infinite sets are different. Here's a correspondence, for instance, for the integers:
0 <-> 0 1 <-> 1 2 <-> -1 3 <-> 2 4 <-> -2 ...No such correspondence can exist for the real numbers, though. The proof is called Cantor's diagonalization argument (see CantorsProof). We also have a longer explanation of CountablyInfinite.
Related question(?)
Are there numbers (reals) that can NOT be represented as an infinite series containing operations on integers only? So Pi is not such a number since it can be represented as (for example) 4 * (1 - 1/3 + 1/5 - 1/7 ...) which only requires operations on integers.
Are you talking about finite definitions of the terms in the series? The question needs to be defined better. -- vk
Yes. Are there reals that require defining in terms of non-rational numbers?
It's still not obvious what you mean. Certainly, any real number can be written in the form
a1 a2 an
a0 + -- + --- + ... + ---- + ...
10 100 10^n
where each of a0, a1, a2... is an appropriate chosen integer, because that's just the decimal expansion. Of course you need an infinite number of such choices, and they may be entirely random, in the sense that there is no finite expression or program that will generate the whole sequence.
That's no fun. The question arose from reading about KolmogorovComplexity where the point is made that Pi is not very complex because the program needed to output it is quite simple. I guess what I was looking for is: are there numbers that can be defined by an infinite series that does not require explicit specification of an infinite number of terms (so the simple decimal expansion doesn't count) that must contain non-rational terms in the expansion? These numbers should be easy to specify, yet still Kolmogorov complex since the requirement of non-rational terms would make the program infinitely long.
I would guess that the series concept is irrelevant in that at least one term (which would suffice) would need to involve one of the "unknowable" reals; i.e., knowable reals can be defined in terms of integers. -- vk
What about GregoryChaitin's BigOmega?
It is not necessary to consider only irrational numbers. There are a lot of natural unknowable numbers, when using finite descriptions. There is a smallest number which may not be described with a finite alphabet. Even more, there are a lot of unknowable numbers you cannot know actually, because your brain is too small and the time is too short. This happens to all finite brains and even if you consider all combinations of all finite languages applied to all finite amounts of letter combinations. Borges described a very similar problem called "The infinite library". If I say: I know any number I ever read until now and a knowable number is any number I can read until my life ends, there is no big difference. The only thing: you cannot know the number.
I'll readily agree that there are very big and very precise numbers that are unknowable due to the limitations of finite storage and processing ability and the inability to describe in 'reasonable' space even an algorithm that would produce it (KolmogorovComplexity), but that's not really the issue with UnknowableNumbers. UnknowableNumbers involves finite space, not fixed space. The bound for space is as high as you need it, so long as one can be shown to exist.
I'm not so ready to accept your claim that "There is a smallest number which may not be described with a finite alphabet". It is trivially possible to create descriptions that have no referent (or reference 'nothing'), including "mu" and "all integers simultaneously less than 10 and greater than 100". To prove that such an 'unknowable number' exists, you must show that it simultaneously exists and cannot be represented. It's a non-trivial proof. And your statement that "There are a lot of natural unknowable numbers, when using finite descriptions" is simply incorrect. For ANY natural number, it is VERY easy to give an algorithm that will compute an upper-bound for the space-cost of representing that number in a particular language. And that upper bound is all it takes to prove that it can be represented in finite space. Same for any rational number, which takes at most two natural numbers and a sign character to represent.
UnknowableNumbers need to be irrational, so they're not natural (i.e., whole) numbers. The "not necessary" paragraph above is completely incorrect.
0.1234567891011121314...
Should be obvious but no algebraic expression can express this one.
It can easily be expressed with a small program, even a functional one. I think it merely a matter of the algebra being expressive enough.
Number of digits in n (for n > 0): d(n) = floor(log n) + 1
Number of digits in 1...n: D(n) = sum d(i) as i goes from 1 to n
0.0000...00n : N(n) = n * 10 ^ (-D(n))
The number above = sum N(n) as n goes from 1 to infinity.
On the more general question above: "Is there prior art on this topic?", the Wikipedia page http://en.wikipedia.org/wiki/Computable_set points to three references:
I will call the numbers that are not unknowable as knowable, for shortness.
The knowable numbers form a field, that a+b, a-b, a*b and a/b are knowable, provided that a and b are knowable. It contains all algebraic numbers (that is, all real roots of polynomials with integer coefficients). The set of complex numbers with both real and imaginary parts knowable (that is, knowable complex numbers) is algebraically closed, which means that it contains all real roots of polynomials with coefficients that are knowable.
If k is knowable and u is unknowable than k+u, k*u, k/u, k^u, u^k,... must be unknowable (provided that u<>0 or u<>1 in some obvious cases).
This set is also closed under knowable functions. By knowable function I mean a function mapping real numbers into real numbers that can be specified in the same manner as knowable numbers. So, for example, sin(a), exp(a), atan(a) is knowable if a is knowable.
The set of unknowable numbers is dense in real numbers - between any two real numbers there is an unknowable number. This is a consequence of the fact, that any segment of real numbers has cardinality equal continuum.
I hearby name the smallest unknowable number "fee". --JoshuaHudson
For the heck of it: Here is a proof that the set of the knowable numbers is countable, based on the definition of humans:
For any knowable number, there must be a finite, formal specification of it. Any finite specification may be represented in a finite amount of UTF-8, provided it allows mathematical symbols. UTF-8 is binary. Therefore any UTF-8 file may be trivially converted to a finite whole number. Whole numbers are a subset of the integers. So for every knowable number, there is at least one integer.
There is no smallest unknowable number. CategoryMath MathematicalParadoxes
EditText of this page
(last edited January 12, 2014)
or FindPage with title or text search