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
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
- Thanks Michael. I think you and I might have hit upon the same area of research from two different angles. When I encountered it, I was re-considering the [irrational] definition of the unit square diagonal (see the commentary and dialog at BigInt). I simply called them "indefinite rationals", but I think your term is better (you can have credit for that). Note the use of the term and domain "rationals" because of your requirement of "finite specifiability". I think you might find my EpistemicsOfQuantity useful with regard to your idea of "specification". -- MarkJanssen
- The basic idea is not new, but the specific exploration ideas may be.
- The existence of undefinable numbers is an elementary theorem in mathematical logic. -- rk
- "elementary" theorem??
- Anything you learn in the third week of an intro to math logic class is very elementary.
Are there things we can say about the UnknowableNumbers
, or is that itself impossible? Is there prior art on this topic?
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:
- 5^2 + 4^2 + 1
- x, where x > 0 and x^2 - 10 x - 1344 = 0.
- The product of the fourth PrimeNumber and the first perfect number.
- The number which DouglasAdams made famous.
And here are some specifications for some other numbers.
- The ratio between the circumference of a circle and its diameter.
- The integral of 1/x from 1 to infinity.
- The first PrimeNumber which is exactly equal to the sum of 10 Fibonacci numbers. (I haven't worked out what this is... but I've specified it clearly.) It isn't obvious that there is any such number... if there isn't, your statement specifies nothing. This is an important point in the PhilosophyOfMathematics?. [If the Fibonacci numbers do not need to be distinct, the prime above is 11, else I think it is 211.]
These aren't specifications:
- The number I'm thinking of right now.
- The value of x which solves the equation x^2 + 12 x + c = 0, where c is not specified.
- The smallest number bigger than 3. No such thing (absent infinitesimals).
- Actually, even allowing infintesimals there is still no smallest number bigger than 3.
- The smallest zero of the Quiggle function. "Quiggle function" needs to be defined. So does "smallest" (does it allow a negative?).
- specifications of (even countably) infinite length. Without this, every real can be specified. (However, Richard generalizes by reference to members of power sets if this restriction is not applied.)
Questions to be picked up in the discussion:
Are the number of number specifications countable or uncountable? (see AreTheSpecifiableRealsWellDefined
What if uncountably long specifications are allowed? (see NumberSpecificationsAndTuringMachines
Is there at least one real number that simply cannot be specified? (if so, there are probably uncountably many such)
Is there a relationship between undefinable numbers and the HaltingProblem
There are more lurking below.
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.
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
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
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)
seeks to quantify the inherent complexity of a thing by measuring the length of the shortest program for a TuringMachine
which, when run, will calculate that thing. (Obviously, you have to map TuringMachine
output to the kinds of things you're measuring. See http://www.best.com/~szabo/kolmogorov.html
for an introduction. It turns out that the choice of what language to program in doesn't affect the result (to within a constant), and thus the concept is fairly well-defined. See http://homepages.cwi.nl/~tromp/cl/cl.html
for an excellent machine on which to measure KolmogorovComplexity
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.
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]
would have an infinite KolmogorovComplexity
, but not all numbers with infinite KolmogorovComplexity
would be unknowable.
- I wonder if UndefinableNumbers? is a better name for this concept/page. Possibly. A google search finds "undefinable" and other synonyms, but doesn't locate anything of much interest.
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.
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.
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!
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! :)
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.
- When did humor become illegal?
- Humor is not illegal, but in the written medium it can be seriously misleading.
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.
- Eh? Don't you merely get new sets of numbers, but not new numbers?
- The difference is really one of semantics; reals are defined in terms of sets of rationals.
- But once you go beyond complex numbers, the term "numbers" is not used.
HEY WAIT A MINUTE! Reals are not merely defined in terms of rationals. Proof by counterexample: PiNumber?
. For some handwaving: If you add, subtract, multiply, or divide rationals, you get rationals. You can do this up to and including AlephNought
times and still have a rational.
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
- The other way to get at reals is via Cauchy sequences. Some people find them easier to understand. We're still talking about set of rationals, though, and the two techniques are equivalent.
The reals which are definable will depend on the axioms you have chosen. But the axioms themselves are expressed as sentences in the language, as are any definitions constructed from those axioms. Whether you have these axioms or those axioms or even an infinite number of axioms doesn't change the limitations of the language itself. -- rk
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.
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)
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/
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
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.
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.
What about GregoryChaitin
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.
need to be irrational, so they're not natural (i.e., whole) numbers. The "not necessary" paragraph above is completely incorrect.
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.
It's impossible to actually offer a constructive example of any unknowable number. Such a thing would be a contradiction in terms.
- I think not. It's a categorical limitation, given the normal definition of "algebra". Now you could perhaps, define a 'meta-algebra to express such a number, but then you might as well be back in the CS domain.''
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'd guess that these books predate this article appearing here?
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.