= 27d567bc2d48d9f40e9ccc20ea370b15)
Vaniver comments on Respond to what they probably meant - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (42)
Wiki's discussion of base pi.
Wiki raises an interesting point, a little further down, talking about base sqrt(2). Any number that can be expressed in a finite number of digits in base 2 can also be expressed in a finite number of digits (albeit twice as many) in base sqrt(2); also, some irrational numbers (like sqrt(2)) can also be expressed in a finite number of digits in base sqrt(2).
This leads me to wonder whether there is any number base in which any number, rational or irrational, can be fully described as either a finite (potentially extremely large) number of digits or a repeating pattern (like 1/7 in decimal) or not...
There isn't. You can see this by considering the cardinality. The set of all (finite) sequences of digits in any finite alphabet (e.g. 0 to 9) is only countably large. So it can't map the irrational (real) numbers.
Actually, the set of all infinite sequences of digits in any finite alphabet with two or more symbols is uncountable - this can be shown via a diagonalization argument. I suspect you meant to say that the set of all finite sequences of digits is countably large.
Yes, that's right. Thanks!
I thought I might be able to get around that limit by permitting infinite repeating sequences of digits - but it turns out that that's equivalent to introducing a single new symbol to the notation (with the further restriction that it can only be used not more than once per number), and therefore the set of infinite repeating sequences is also countable; thus, in order to represent all real numbers, it remains insufficient.
Yup. Just for fun, some other ways to see that there are only countably many repeating sequences:
That's an interesting point. A computer program is itself a finite number of symbols chosen from a finite list (with certain restrictions that further reduce the number of programs that make sense).
The same can be said for the English language. In fact, the same can be said for any language that can be translated into English, or into any other language that has a finite alphabet.
And I don't know how a language with an infinite alphabet would work, but if it can be explained in English, then that implies that it can be translated to English.
This therefore implies that there must exist numbers which cannot be precisely specified at all.
Almost all of them! But, y'know, I can't tell you what any of them are :-).
And among these, there is the smallest undefinable number.
There isn't. The collection of positive, undefinable numbers is bounded below by zero, but doesn't actually have a smallest element (due to the reals not being well-ordered).
I was going to say "Congratulations, you just proved the halting theorem." -- but actually I think the paradox you're gesturing at fails to "work" for shallower reasons (e.g., the reals not being well-ordered -- trivially not by the usual ordering, and less trivially not by anything computable, because it's consistent with ZF for there to be no well-ordering of the reals).
If you mean the smallest undefinable positive number, then isn't that epsilon?
Technical note: strictly this requires the Axiom of Choice, or at least some weaker version of it. For each of your countable sets, there is at least one way of counting it; but to count the whole lot you need to pick one way of counting each set. This is exactly the kind of thing that can fail to happen without Choice. You don't need "very much" Choice; e.g., the axiom of choice for countable collections is enough; but it turns out that the axiom of choice for countable collections of countable sets is not enough.
That was quick. Thank you.