Indescribable numbers: The theorem that made me fall in love with math(blog.ram.rachum.com)
blog.ram.rachum.com
Indescribable numbers: The theorem that made me fall in love with math
http://blog.ram.rachum.com/post/54747783932/indescribable-numbers-the-theorem-that-made-me-fall-in
31 comments
> You can take any bitstring (but not all bitstrings) of any length, including infinite, and assign a specific shorter (and finite) bitstring to represent it. You then have a finite encoding for that specific infinite sequence of symbols which can henceforth be used to describe it. You just can't do it for every infinite bitstring because you have insufficiently many finite bitstrings with which to represent them.
I agree with your general idea, but, won't you run into a problem already before you run into the pigeon-hole principle?
How do you do that, even for a single one?
I mean, how do you "take" an infinite bitstring to assign a symbol to it, without first having to have a finite description of this infinite bitstring?
You can't say "this infinite bitstring is now represented by the symbol 01101", without directly or indirectly specifying what "this infinite bitstring" refers to, and you need to do that specifying in a finite amount of symbols.
So it seems to me that, if you were to (foolishly) try the above infinite task, you'd run out of infinite bitstrings (that you can describe) just as fast as you'd run out of finite bitstrings that you'd like to compress them with?
I agree with your general idea, but, won't you run into a problem already before you run into the pigeon-hole principle?
How do you do that, even for a single one?
I mean, how do you "take" an infinite bitstring to assign a symbol to it, without first having to have a finite description of this infinite bitstring?
You can't say "this infinite bitstring is now represented by the symbol 01101", without directly or indirectly specifying what "this infinite bitstring" refers to, and you need to do that specifying in a finite amount of symbols.
So it seems to me that, if you were to (foolishly) try the above infinite task, you'd run out of infinite bitstrings (that you can describe) just as fast as you'd run out of finite bitstrings that you'd like to compress them with?
I like how the post reflects the excitement of discovering something for yourself, even if only to find out later that it's commonly known in certain domains. Sometimes in this day and age with search engines it seems useless to sit and think about a problem when you can just search and see if and how someone has already solved it.
For me, I like to wonder about the transition point in history where man went from not using numbers to using them. What prompted this? Were numbers used first to indicate order (e.g. my first born son) or quantity? How did someone first teach the idea of numbers to another?
I'm sure there are endless books and articles written on this topic, but I've never had the desire to see what others have to say on the subject. Sometimes it's just nice to let my mind relax and drift to such questions; I sometimes recapture the feeling of wonder and exploration that I had originally...
For me, I like to wonder about the transition point in history where man went from not using numbers to using them. What prompted this? Were numbers used first to indicate order (e.g. my first born son) or quantity? How did someone first teach the idea of numbers to another?
I'm sure there are endless books and articles written on this topic, but I've never had the desire to see what others have to say on the subject. Sometimes it's just nice to let my mind relax and drift to such questions; I sometimes recapture the feeling of wonder and exploration that I had originally...
This is good. I really liked it.
But just to continue the mind-games, yes there are an infinity more indescribable numbers than there are describable ones, but should there be?
Given the balloon example, he makes the case that as an imaginary god: "...stare imploringly into the siren call of the final ellipsis, for you know that no matter how often you expand it, I will always smile when giving you more and more digits, because you and I will both know that the final wisdom of The Number will always be mine and never yours..."
But we know that, given any exact point in time, only a certain number of atoms are inside the balloon. Therefore, whatever the number is to answer the equation, it is one with a finite number of digits. (One imagines the experiment being done in such a manner that quantum tunneling is minimized)
So while yes, using symbols you can certainly construct numbers which are indescribable (given either an infinite series of symbols or a self-recursive way of generating more), does the real world actually work that way?
In other words, is mathematics truly isomorphic with reality as we observe it? Or is it somehow a superset of logic sitting above an infinite number of possible realities? In a universe full of discrete things (perhaps at the sub-quark level), do we need a system of mathematics that works over continuities? Is such a model always helpful? If not, where might it be tripping us up?
But just to continue the mind-games, yes there are an infinity more indescribable numbers than there are describable ones, but should there be?
Given the balloon example, he makes the case that as an imaginary god: "...stare imploringly into the siren call of the final ellipsis, for you know that no matter how often you expand it, I will always smile when giving you more and more digits, because you and I will both know that the final wisdom of The Number will always be mine and never yours..."
But we know that, given any exact point in time, only a certain number of atoms are inside the balloon. Therefore, whatever the number is to answer the equation, it is one with a finite number of digits. (One imagines the experiment being done in such a manner that quantum tunneling is minimized)
So while yes, using symbols you can certainly construct numbers which are indescribable (given either an infinite series of symbols or a self-recursive way of generating more), does the real world actually work that way?
In other words, is mathematics truly isomorphic with reality as we observe it? Or is it somehow a superset of logic sitting above an infinite number of possible realities? In a universe full of discrete things (perhaps at the sub-quark level), do we need a system of mathematics that works over continuities? Is such a model always helpful? If not, where might it be tripping us up?
What you describe has to do with mathematical constructivism[0], and also with the Axiom of Choice, and it's really complicated (to me, I'm not a mathematician, and I only sort-of get it).
You may have heard about the Banach-Tarski paradox[1], which tells you that if you assume "Real numbers" are actually reality, and the Axiom of Choice, you can divide a sphere into five pieces (one of which is just a point) and rearrange them into two spheres of the same volume.
Obviously you can't do that in reality. This is the point where it gets really complex and I won't fill in the details as I understand them, because they are probably wrong.
R. Buckminster Fuller also wrote some ideas on this constructivism (or something a lot like it), basically advocating against the set of "Real Numbers" as an accurate depiction of reality. For instance if you make a 1m x 1m square out of a real material. The sides of that square will have N atoms, and the number of atoms (and how far they are apart, which is a property of the material used) is really what describes the length. This is a whole number. But according to geometry math, the diagonal of this square has a length of sqrt(2) metres, or sqrt(2) * N atoms. That can't be because you can't have an irrational number of atoms. Then what is really going on suddenly depends on how these atoms are packed inside the square, and again, it gets really complex and that's where my understanding (of both atomic physics and mathematical constructivism) stops.
[0] http://en.wikipedia.org/wiki/Constructivism_(mathematics)
[1] http://en.wikipedia.org/wiki/Banach-Tarski_paradox
You may have heard about the Banach-Tarski paradox[1], which tells you that if you assume "Real numbers" are actually reality, and the Axiom of Choice, you can divide a sphere into five pieces (one of which is just a point) and rearrange them into two spheres of the same volume.
Obviously you can't do that in reality. This is the point where it gets really complex and I won't fill in the details as I understand them, because they are probably wrong.
R. Buckminster Fuller also wrote some ideas on this constructivism (or something a lot like it), basically advocating against the set of "Real Numbers" as an accurate depiction of reality. For instance if you make a 1m x 1m square out of a real material. The sides of that square will have N atoms, and the number of atoms (and how far they are apart, which is a property of the material used) is really what describes the length. This is a whole number. But according to geometry math, the diagonal of this square has a length of sqrt(2) metres, or sqrt(2) * N atoms. That can't be because you can't have an irrational number of atoms. Then what is really going on suddenly depends on how these atoms are packed inside the square, and again, it gets really complex and that's where my understanding (of both atomic physics and mathematical constructivism) stops.
[0] http://en.wikipedia.org/wiki/Constructivism_(mathematics)
[1] http://en.wikipedia.org/wiki/Banach-Tarski_paradox
> Banach-Tarski
Yes, but in that construction, not all the sets are Lebesgue measurable. It's a curious fact, already true just in one dimension, i.e., the reals, that we can't have a nice way to assign a length, area, or measure to all the subsets. Instead there have to be some subsets to which we can't assign a length, etc. Here the usual proof on the reals does use the axiom of choice!
With measurable sets, which already can be wildly bizarre, can't do anything like Banach-Tarski.
So, suddenly in this thread, instead of hackers, we are all turning into undergraduate pure math majors!
Yes, but in that construction, not all the sets are Lebesgue measurable. It's a curious fact, already true just in one dimension, i.e., the reals, that we can't have a nice way to assign a length, area, or measure to all the subsets. Instead there have to be some subsets to which we can't assign a length, etc. Here the usual proof on the reals does use the axiom of choice!
With measurable sets, which already can be wildly bizarre, can't do anything like Banach-Tarski.
So, suddenly in this thread, instead of hackers, we are all turning into undergraduate pure math majors!
Constructivism is significantly more fundamental than AC. AC is notable for being famously perplexing, less foundationally perplexing. For a more graspable investigation of the perplexities and arbitrariness of our choice of foundational set theory, take a look at Vicious Cycles where the author investigates what happens when set theory does not assume a terminating world (and thus introduces a lot of things that we use in CS often, try to model on sets, and are left dissatisfied because we really wanted costa, not data).
From there please take a deep look into topos theory and you'll discover again that AC is just one choice of properties that make for a meaningful "foundation of mathematics (of a kind)" and a not particularly remarkable one at that.
From there please take a deep look into topos theory and you'll discover again that AC is just one choice of properties that make for a meaningful "foundation of mathematics (of a kind)" and a not particularly remarkable one at that.
"Costa, not data", what does that mean?
And Vicious Cycles is a book, I presume? Who is the author?
And Vicious Cycles is a book, I presume? Who is the author?
[deleted]
When I tell many people that I do my research in infinite combinatorial games, they immediately assume that my research is more impressive[0] than my officemate's research dealing with finite combinatorics. I always move quickly to correct them: dealing with infinity often has the effect of making mathematics easier, and unfairly "trivializes" distinctly difficult problems. After all, in my work, 2^100 is "just finite", even though that many milliseconds would compose over 40 quintillion years.
To your point, I don't know the answer of whether the universe is finitely describable or not. But I certainly know it's easier to abstract many small aspects of the universe with an approximation by an "infinite model" than to deal with the ridiculously large finite numbers involved.
[0] if more useless
To your point, I don't know the answer of whether the universe is finitely describable or not. But I certainly know it's easier to abstract many small aspects of the universe with an approximation by an "infinite model" than to deal with the ridiculously large finite numbers involved.
[0] if more useless
I would find it very beautiful if we could get away with only integers, for example a large number of interacting state machines. This way we could get rid of the complex ideas like space and time (if you manage to convince your brain that there is no need to embed a net of state machines in space and that they have to change state over time).
I think you have your argument backwards, we use math to describe reality. So whatever axiom system you choose to build your physical theory, there is then some correspondence between the objects of your axiom system and reality. And if you somehow manage to construct a physical theory with integers alone, then there will only be integers in your description.
Interestingly: Indescribable numbers do not appear in physical theories.
Proof: The number would need to be described by the theory in order to have a correspondence to nature.
( None of the above should be constructed as a statement about the existence of Platonic ideals.)
Interestingly: Indescribable numbers do not appear in physical theories.
Proof: The number would need to be described by the theory in order to have a correspondence to nature.
( None of the above should be constructed as a statement about the existence of Platonic ideals.)
The interesting thing here is that it's much harder to put this problem properly into mathematical terms than it is to solve it. The whole insight here is that you a "description" of number is just some finite sequence of symbols from a finite alphabet. Now, if you understand why cardinality of continuum is greater than aleph null, it's totally straightforward to show that there are only countably many descriptions, but continuum many reals, it's the kind of problem you give freshmen students on their first encounter with cardinalities. Thus, the big achievement of this guy is to actually come up with idea of indescribable numbers by himself and interpreting this question mathematically. In other words, the questions are usually more important than answers.
There's one minor, but nevertheless important mistake made by the author. Author says :
>The infinity just a step bigger than [aleph null] is Aleph one, the infinity of real numbers: The infinity of an impossibly dense line of numbers
While cardinality of reals is certainly larger than cardinality of integers, it is not true that it's just one step larger. Funny thing is that it's not false either: it was proved by Cantor and Cohen that it's impossible to prove or disprove that aleph one is cardinality of continuum. This is the famous continuum hypothesis.
There's one minor, but nevertheless important mistake made by the author. Author says :
>The infinity just a step bigger than [aleph null] is Aleph one, the infinity of real numbers: The infinity of an impossibly dense line of numbers
While cardinality of reals is certainly larger than cardinality of integers, it is not true that it's just one step larger. Funny thing is that it's not false either: it was proved by Cantor and Cohen that it's impossible to prove or disprove that aleph one is cardinality of continuum. This is the famous continuum hypothesis.
> it was proved by Cantor and Cohen
Goedel and Cohen. Goedel proved it might be (constructible universe); Cohen proved it might not be (forcing). I think Cohen's on record as saying he suspects that with the "right" axioms, mathematicians might come to think that CH is obviously false.
Goedel and Cohen. Goedel proved it might be (constructible universe); Cohen proved it might not be (forcing). I think Cohen's on record as saying he suspects that with the "right" axioms, mathematicians might come to think that CH is obviously false.
Ah, of course, I don't know why I have written Cantor. It's too late to edit now.
Interestingly, for any method of describing real numbers (i.e. mapping from finite strings to real numbers), the diagonal argument gives an explicit description of a single number that's undescribable by that method. Just out of reach, so to speak.
I will just assume the continuum hypothesis is true until someone shows me a set with cardinality between Aleph 0 and Beth 1...oh, wait...
It is well proven that Aleph one, which is the infinity of the real numbers, is undeniably bigger than the infinity of the natural numbers.
The clause "Aleph one, which is the infinity of the real numbers", is known as the continuum hypothesis, and has a fascinating background in itself.
First, the existence of Aleph one in axiomatic Zermelo-Fraenkel set theory depends (surprisingly) on the Axiom of Choice. If you reject AC, we can't show that there exists a unique Aleph one.
It gets weirder. If you accept ZFC (ZF set theory, plus the Axiom of Choice), we can prove that both Aleph one and the cardinality of the reals are greater than Aleph nought. However, Gödel proved in 1940 that Aleph one cannot be proven to be equal to the cardinality of the reals, given ZFC. In fact, none of the main ZFC axioms constrain the continuum hypothesis--there are some proposed axioms, like constructability, which imply CH, but nobody is really sure whether we should accept them.
This is very much a philosophical problem in mathematics: having proven we cannot decide on the basis of the axioms we widely accept, it's now up to us to choose which branch (or both) of mathematics is more useful or epistemologically satisfying--or find other axioms we can agree on that in turn constrain CH.
[edit] derp, just read to the bottom, and it's comment #1. Right then, carry on. :)
The clause "Aleph one, which is the infinity of the real numbers", is known as the continuum hypothesis, and has a fascinating background in itself.
First, the existence of Aleph one in axiomatic Zermelo-Fraenkel set theory depends (surprisingly) on the Axiom of Choice. If you reject AC, we can't show that there exists a unique Aleph one.
It gets weirder. If you accept ZFC (ZF set theory, plus the Axiom of Choice), we can prove that both Aleph one and the cardinality of the reals are greater than Aleph nought. However, Gödel proved in 1940 that Aleph one cannot be proven to be equal to the cardinality of the reals, given ZFC. In fact, none of the main ZFC axioms constrain the continuum hypothesis--there are some proposed axioms, like constructability, which imply CH, but nobody is really sure whether we should accept them.
This is very much a philosophical problem in mathematics: having proven we cannot decide on the basis of the axioms we widely accept, it's now up to us to choose which branch (or both) of mathematics is more useful or epistemologically satisfying--or find other axioms we can agree on that in turn constrain CH.
[edit] derp, just read to the bottom, and it's comment #1. Right then, carry on. :)
I feel like every time I get deep enough into a topic of mathematics, Gödel inevitably shows up to say, "things beyond this point are provably unprovable!" It's simultaneously vexing and fascinating.
It's precisely this conundrum and others like it that have lead me to take two controversial opinions that are far less firm than the real thought that your describing: 1) mathematics and what is taught as physics are not "real," but merely leaky abstractions. Even though they can capture reality very well, they are not reality itself. There is no perfect circle that exists in physical space, and not necessarily a pi represented anywhere in physical space. You'll notice that a lot of the wonder that is expressed in this post comes from thinking that 3sin(57) is something that is exactly* reality. And 2) all of mathematics is invented, not discovered. The particular math we use may be discovered independently by different, unconnected, civilizations, because there are certain thought processes that fit well with human intelligence. If we discover other intelligent life forms, there may be some small overlap by coincidence in our mathematics, it's likely that it could be quite different. Perhaps even arithmetic could be considerably different.
We are taught from day one in class that mathematics is some sort of ideal plane of existence, pure, and real. However I see it only as technology for our squishy gray matter to help navigate a mysterious universe. I get huge huge resistance on this from engineers and some young scientists; they see the textbook science and math where everything has a nice closed-form answer you can look up in the back of the book. More mature scientists object less, but that may just be because they think it's pointless to discuss these things with me.
Trying to use mathematical technology in the real world in new areas makes one realize that only a tiny percentage of questions are answerable with the tools they teach us in school. The lack of a closed solution to the 3-body problem is not due to a lack of cleverness in answering, but a lack of cleverness in questioning. And further study leads to the paradoxes and the holes that were discovered in the previous century, at which point, most people's faith in math's fidelity to reality begins to become less than absolute.
We are taught from day one in class that mathematics is some sort of ideal plane of existence, pure, and real. However I see it only as technology for our squishy gray matter to help navigate a mysterious universe. I get huge huge resistance on this from engineers and some young scientists; they see the textbook science and math where everything has a nice closed-form answer you can look up in the back of the book. More mature scientists object less, but that may just be because they think it's pointless to discuss these things with me.
Trying to use mathematical technology in the real world in new areas makes one realize that only a tiny percentage of questions are answerable with the tools they teach us in school. The lack of a closed solution to the 3-body problem is not due to a lack of cleverness in answering, but a lack of cleverness in questioning. And further study leads to the paradoxes and the holes that were discovered in the previous century, at which point, most people's faith in math's fidelity to reality begins to become less than absolute.
Excellent article. If you like this sort of thing, you may enjoy Busy Beaver numbers, my favorite treatment of which is the essay "Who Can Name the Bigger Number?"
http://www.scottaaronson.com/writings/bignumbers.html
http://www.scottaaronson.com/writings/bignumbers.html
Thank you for this resource. I hadn't formally been exposed to tetration, but I had recently been pondering the concept, I guess in the same way Ackermann came up with his sequence. I'm so glad to know that this isn't uncharted territory in mathematics, and I now have more knowledge with which to frame my thought experiments.
Graham's number - for a while, the largest number used in a proof:
https://www.youtube.com/watch?v=XTeJ64KD5cg
There are faster growing sequences as well, see: http://math.stackexchange.com/questions/2497/what-is-the-big...
both fun as well.
But busy beaver consumes them all.
There are faster growing sequences as well, see: http://math.stackexchange.com/questions/2497/what-is-the-big...
both fun as well.
But busy beaver consumes them all.
Yes! I read that article years ago and was absolutely captivated!
The most incredible thing in this article is the assertion that there exists at least one math professor that is unaware of this theorem - I was taught all of this in the first algebra course at university...
Yeah... I mean, am I the only one that thinks this article is kind of trite? Uncountability isn't a completely mind blowing concept to me.
I think that both you and svantana are talking about countability, which is not the point of this post but just a tool used to prove the theorem of indescribable numbers.
I didn't think that dating this theorem to the 1940's was accurate. This was originally proved by Cantor in 1874 [1]. Cantor's work was well-known (and highly controversial) during his lifetime [2].
[1] http://en.wikipedia.org/wiki/Uncountability_of_the_real_numb...
[2] http://en.wikipedia.org/wiki/Georg_Cantor
[1] http://en.wikipedia.org/wiki/Uncountability_of_the_real_numb...
[2] http://en.wikipedia.org/wiki/Georg_Cantor
The theorem(s) about uncomputable numbers do date back only as far as the 1940's, because that's when computability was first being discovered/invented. Yes, the point about there being uncountably many reals dates back to Cantor, but that's a different theorem, and a different proof. The existence of uncomputable numbers follows as a corollary from Cantor's first proof of 1874, but the conclusion must be drawn - it wasn't there in Cantor's work.
Specifically:
We can prove that there are uncomputable numbers simply by noting that the number of Turing machines is countable, so the number of computable numbers is countable. Since there are uncountably many reals (by Cantor - 1874) then we can conclude that there are numbers that cannot be produced by a Turing machine.
Specifically:
We can prove that there are uncomputable numbers simply by noting that the number of Turing machines is countable, so the number of computable numbers is countable. Since there are uncountably many reals (by Cantor - 1874) then we can conclude that there are numbers that cannot be produced by a Turing machine.
You're misunderstanding the theorem the author proved.
Theorem A (author's theorem): No mapping from finite-length strings to real numbers will hit all the real numbers.
Theorem B (your theorem): Let's map strings of finite length to real numbers as follows: Consider the string as the specification for a Turing machine. If the specification is syntactically OK as a Turing machine description, and the output is syntactically OK as the decimal expansion of a (potentially infinite) real number, then that string maps to that real number. Otherwise, the string maps to zero. Then this particular mapping doesn't hit all the real numbers.
It's obvious that Theorem B is just a special case of Theorem A. And it's also obvious that Theorem A is a trivial corollary of Cantor's result (that no mapping from natural numbers to real numbers hits all real numbers), with no Turing machines or computation theory anywhere in sight.
I can well believe that Theorem B was either proven by Turing himself, or established in the early years post-Turing; it's low-hanging fruit once you've defined Turing machines and are familiar with Cantor's results. And it could hardly have been proven before the Turing machines were defined! So Theorem B is a special case that could plausibly have first arisen in the 1940's, but Theorem A is actually the theorem the author is talking about.
Theorem A (author's theorem): No mapping from finite-length strings to real numbers will hit all the real numbers.
Theorem B (your theorem): Let's map strings of finite length to real numbers as follows: Consider the string as the specification for a Turing machine. If the specification is syntactically OK as a Turing machine description, and the output is syntactically OK as the decimal expansion of a (potentially infinite) real number, then that string maps to that real number. Otherwise, the string maps to zero. Then this particular mapping doesn't hit all the real numbers.
It's obvious that Theorem B is just a special case of Theorem A. And it's also obvious that Theorem A is a trivial corollary of Cantor's result (that no mapping from natural numbers to real numbers hits all real numbers), with no Turing machines or computation theory anywhere in sight.
I can well believe that Theorem B was either proven by Turing himself, or established in the early years post-Turing; it's low-hanging fruit once you've defined Turing machines and are familiar with Cantor's results. And it could hardly have been proven before the Turing machines were defined! So Theorem B is a special case that could plausibly have first arisen in the 1940's, but Theorem A is actually the theorem the author is talking about.
You're right, although I wasn't so much misunderstanding, as misremembering. As so often happens, there's been a flurry of similar comments, and I mis-remembered what had been said, and hadn't re-read before commenting.
Apologies.
Apologies.
The social-cultural construct of the whole EE to Math conversion makes the story interesting, and has not been commented on.
An EE who focuses on infinite decimal places doesn't belong in EE at all. That push out is at least as strong as the attraction into math that everyone else caught.
To qualify the push out, an affection for unreasonable / ridiculous sig figs leads to junior EEs having arguments like "I'm not going to approve this power on indicator LED bias resistor value unless its precisely 72.66 ohms using a 0.01 precision resistor because that's what I got with a SPICE run using datasheets, none of this preferred value "82 ohm 10% tolerance 1/4 watt metal film" stuff". You can tell those guys in the lab, because they use uncalibrated three digit multi meters but write down all 10+ digits off their calculator.
An EE who focuses on infinite decimal places doesn't belong in EE at all. That push out is at least as strong as the attraction into math that everyone else caught.
To qualify the push out, an affection for unreasonable / ridiculous sig figs leads to junior EEs having arguments like "I'm not going to approve this power on indicator LED bias resistor value unless its precisely 72.66 ohms using a 0.01 precision resistor because that's what I got with a SPICE run using datasheets, none of this preferred value "82 ohm 10% tolerance 1/4 watt metal film" stuff". You can tell those guys in the lab, because they use uncalibrated three digit multi meters but write down all 10+ digits off their calculator.
Ah, he's just getting started on his
journey into the set of real numbers!
Eventually he will discover, "God made the integers. All else is man made.".
In particular, man made the real numbers to be complete which means that every sequence that appears to converge, that is, meets, the Cauchy criterion, actually does converge. Really his discoveries are about the completeness property of the real numbers. So, in particular, if we have an infinite series that meets the Cauchy criterion, then it converges, in particular, there is real number for it to converge to. The same statement is not true in the rational numbers or the algebraic numbers!
Calculus: Sure, the elementary properties of the completeness property of the real numbers.
How do we know that anything like the real numbers can exist? Because we can start with the simplest things, say, just the empty set, do a lot of set theory pushing around, construct something that looks like the natural numbers -- 1, 2, 3, .... Then we can use the naturals to construct (something that looks like) the integers -- ..., -3, -2, -1, 0, 1, 2, 3, ....
Continuing in this way, we can construct the rationals and the reals. For the reals, a popular approach, nicely intuitive, is Dedekind cuts.
So, we base it all on just set theory starting with just the empty set.
So, the reals exist but only because man said that they exist!
Too soon he will face a danger, compactness! That's where every infinite subset has a limit point, that is, in the infinite subset is a sequence that converges to something. This is true if and only if every open cover has a finite subcover. And every closed and bounded subset of finite dimensional, real Euclidean space is compact. A real valued continuous function with domain a compact set is uniformly continuous and bounded and achieves both its upper and lower bounds. Seeing these results, the poor guy might lose it! The usual way we show that the Riemann integral of calculus exists is via uniform continuity.
After he recovers from seeing the completeness property of the reals, under no circumstances let him learn about Hilbert space -- a complete inner product space! Okay, but are there any examples? Actually, yes: The set of all real valued random variables X so that E[X^2] is finite. Yup, the set of all of these is complete and, thus, forms a Hilbert space. Totally mind blowing that any such thing could be true! Here complete means Cauchy convergent means convergent where we consider distance in Hilbert space which is the metric we get from the inner product. So, with just that concept of distance, a Cauchy convergent sequence of E[X^2] finite random variables actually converges, that is, there is a random variable for the sequence to converge to. You'd think that random variables could wiggle too much, but, no, they can't! Beyond belief.
If he survives these severe trials of the mind, keep him away from a classic text on point set topology, e.g., Kelley. There learn that can have a set A and a point x so that point x is right next to set A but there is no sequence in set A converging to point x. That is, sequences are not enough to characterize the more general case of convergence. For this more general case, there is Moore-Smith convergence, nets, filters, etc.
Somewhere in there he will discover the continuum hypothesis, model theory, etc.
But under no circumstances let him get near
John C. Oxtoby, 'Measure and Category: A Survey of the Analogies between Topological and Measure Spaces', ISBN 3-540-05349-2, Springer-Verlag, Berlin, 1971.
If he sees this book, he may never recover!
Eventually he will discover, "God made the integers. All else is man made.".
In particular, man made the real numbers to be complete which means that every sequence that appears to converge, that is, meets, the Cauchy criterion, actually does converge. Really his discoveries are about the completeness property of the real numbers. So, in particular, if we have an infinite series that meets the Cauchy criterion, then it converges, in particular, there is real number for it to converge to. The same statement is not true in the rational numbers or the algebraic numbers!
Calculus: Sure, the elementary properties of the completeness property of the real numbers.
How do we know that anything like the real numbers can exist? Because we can start with the simplest things, say, just the empty set, do a lot of set theory pushing around, construct something that looks like the natural numbers -- 1, 2, 3, .... Then we can use the naturals to construct (something that looks like) the integers -- ..., -3, -2, -1, 0, 1, 2, 3, ....
Continuing in this way, we can construct the rationals and the reals. For the reals, a popular approach, nicely intuitive, is Dedekind cuts.
So, we base it all on just set theory starting with just the empty set.
So, the reals exist but only because man said that they exist!
Too soon he will face a danger, compactness! That's where every infinite subset has a limit point, that is, in the infinite subset is a sequence that converges to something. This is true if and only if every open cover has a finite subcover. And every closed and bounded subset of finite dimensional, real Euclidean space is compact. A real valued continuous function with domain a compact set is uniformly continuous and bounded and achieves both its upper and lower bounds. Seeing these results, the poor guy might lose it! The usual way we show that the Riemann integral of calculus exists is via uniform continuity.
After he recovers from seeing the completeness property of the reals, under no circumstances let him learn about Hilbert space -- a complete inner product space! Okay, but are there any examples? Actually, yes: The set of all real valued random variables X so that E[X^2] is finite. Yup, the set of all of these is complete and, thus, forms a Hilbert space. Totally mind blowing that any such thing could be true! Here complete means Cauchy convergent means convergent where we consider distance in Hilbert space which is the metric we get from the inner product. So, with just that concept of distance, a Cauchy convergent sequence of E[X^2] finite random variables actually converges, that is, there is a random variable for the sequence to converge to. You'd think that random variables could wiggle too much, but, no, they can't! Beyond belief.
If he survives these severe trials of the mind, keep him away from a classic text on point set topology, e.g., Kelley. There learn that can have a set A and a point x so that point x is right next to set A but there is no sequence in set A converging to point x. That is, sequences are not enough to characterize the more general case of convergence. For this more general case, there is Moore-Smith convergence, nets, filters, etc.
Somewhere in there he will discover the continuum hypothesis, model theory, etc.
But under no circumstances let him get near
John C. Oxtoby, 'Measure and Category: A Survey of the Analogies between Topological and Measure Spaces', ISBN 3-540-05349-2, Springer-Verlag, Berlin, 1971.
If he sees this book, he may never recover!
> God made the integers. All else is man made.
"God made natural numbers; all else is the work of man" - Leopold Kronecker. Possibly misquoted by Raymond Ayoub in "Musings of the Masters: An Anthology of Mathematical Reflections".
"God made natural numbers; all else is the work of man" - Leopold Kronecker. Possibly misquoted by Raymond Ayoub in "Musings of the Masters: An Anthology of Mathematical Reflections".
Thanks! I wanted to say natural
numbers but thought that the
original quote was the integers.
No excuse! Should have at least tried to Google the quote instead of just typing quickly from undergraduate school memory!
No excuse! Should have at least tried to Google the quote instead of just typing quickly from undergraduate school memory!
Stephen Hawking appears to disagree with garysweaver:
http://en.wikipedia.org/wiki/God_Created_the_Integers
Not that Hawking is intrinsically more qualified.
http://en.wikipedia.org/wiki/God_Created_the_Integers
Not that Hawking is intrinsically more qualified.
> In particular, man made the real numbers to be complete which means that every sequence that appears to converge, that is, meets, the Cauchy criterion, actually does converge.
Indeed, but by the same argument as the author's, there are more Cauchy sequences than can be described, so it looks like the real numbers are much bigger than necessary to do mathematics :)
Indeed, but by the same argument as the author's, there are more Cauchy sequences than can be described, so it looks like the real numbers are much bigger than necessary to do mathematics :)
No, to "do mathematics", e.g., show that
the Riemann integral exists, that e and
pi exist, etc., we want completeness.
Then we are done: The reals are the only
complete Archemedean ordered field! So,
we have no choice!
On the contrary, we do have a choice! We could use computable numbers instead of reals. A computable number is any number which is output by some Turing machine, or, equivalently, any number which can be found by some algorithm. e and pi are computable. You are right that Riemann integrals won't exist, but if you modify definitions somewhat, derivatives and integrals can be defined just as easily for computable numbers as for reals and you can do calculus with them (see second link).
Unlike reals, computable numbers are countable, and are all describable. (That is, there are aleph-null of them, so there are exactly as many computable numbers as natural numbers, and fewer than real numbers). And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is.
I prefer computable numbers to reals because I have trouble accepting that a thing exists when it by principal cannot be defined.
https://en.wikipedia.org/wiki/Computable_number
http://www.amazon.com/Computable-Calculus-Oliver-Aberth/dp/0...
Unlike reals, computable numbers are countable, and are all describable. (That is, there are aleph-null of them, so there are exactly as many computable numbers as natural numbers, and fewer than real numbers). And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is.
I prefer computable numbers to reals because I have trouble accepting that a thing exists when it by principal cannot be defined.
https://en.wikipedia.org/wiki/Computable_number
http://www.amazon.com/Computable-Calculus-Oliver-Aberth/dp/0...
Numbers that can be computed by Turing Machines are countable, so list them: c_0, c_1, c_2, etc.
Take any interval [a0,b0] (with a0 and b0 computable), and cross out your computable numbers until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] (again with computable endpoints) within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off computable numbers, each time taking a sub-interval with computable endpoints to exclude any that happen to be in the interval currently under consideration.
The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of computable points. This sequence is bounded above, and so we would like there to be a least upper bound.
And yet it cannot be one of the numbers you first chose, because each has been excluded at some stage. So here we have a strictly increasing, bounded above sequence of computable numbers such that there is no limit in the computable numbers.
This proves the computable numbers are not complete, and that makes analysis really messy.
Take any interval [a0,b0] (with a0 and b0 computable), and cross out your computable numbers until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] (again with computable endpoints) within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off computable numbers, each time taking a sub-interval with computable endpoints to exclude any that happen to be in the interval currently under consideration.
The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of computable points. This sequence is bounded above, and so we would like there to be a least upper bound.
And yet it cannot be one of the numbers you first chose, because each has been excluded at some stage. So here we have a strictly increasing, bounded above sequence of computable numbers such that there is no limit in the computable numbers.
This proves the computable numbers are not complete, and that makes analysis really messy.
There's two related arguments you (may) be making. One is philosophical, and to that I say: can you give an algorithm to compute a0, a1, ...? If you can't (and I suspect you can't), I'd be hesitant to say that such a sequence exists. But I don't think there's a useful argument to have here ;-).
But more concretely: no, the computable numbers aren't complete. Why would this make analysis messy? I didn't find the presentation and results in Computable Analysis (the book) all that different from what you find in an ordinary analysis course. Is there something it makes hard which I'm missing? (This might be impossible to answer without specific knowledge of Computable Analysis; remember that the definitions of, e.g. limits, are different.)
But more concretely: no, the computable numbers aren't complete. Why would this make analysis messy? I didn't find the presentation and results in Computable Analysis (the book) all that different from what you find in an ordinary analysis course. Is there something it makes hard which I'm missing? (This might be impossible to answer without specific knowledge of Computable Analysis; remember that the definitions of, e.g. limits, are different.)
And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is.
Not every number though. It turns out that there are numbers that are describable but not computable.
What is the difference? Well here's an example. A Chaitin omega number is the probability that a valid program randomly constructed according to a specific set of rules will eventually halt. It is describable - indeed I just described it. Yet Chaitin has proven that an algorithm to compute it will lead to an algorithm that solves the halting problem, so it cannot be computable.
So there you have it. A class of perfectly describable numbers that are not computable. Indeed it can be proven that we cannot know more than a fixed number of digits for any particular one without increasing the size of our axiom system.
Not every number though. It turns out that there are numbers that are describable but not computable.
What is the difference? Well here's an example. A Chaitin omega number is the probability that a valid program randomly constructed according to a specific set of rules will eventually halt. It is describable - indeed I just described it. Yet Chaitin has proven that an algorithm to compute it will lead to an algorithm that solves the halting problem, so it cannot be computable.
So there you have it. A class of perfectly describable numbers that are not computable. Indeed it can be proven that we cannot know more than a fixed number of digits for any particular one without increasing the size of our axiom system.
I'm afraid I'm not a good enough logician to answer your objection properly, but there are, I believe, credible approaches to doing mathematics on a countable carrier set, for example:
http://arxiv.org/pdf/math/0509245
http://arxiv.org/pdf/math/0509245
"Credible", likely yes. Likely
also awkward. To weasel out,
I just said we "want
completeness". When you look
at the alternatives, you may
conclude that you still want
completeness and, thus, are
stuck with the reals with no
alternative you "want"!
Awkward I would agree with, but probably only because we're much more used to the usual approach (cf the "awkwardness" of Haskell).
Still, you'll see in that paper that the reals he constructs are complete. The get out clause is that they are not a set, but a class.
Still, you'll see in that paper that the reals he constructs are complete. The get out clause is that they are not a set, but a class.
> The get out clause is that they are not a set, but a class.
Good grief! In axiomatic set theory, introducing 'classes' was the "get out clause" from the Russell paradox of the the set of all sets that are not members of themselves. So, the patch, the time I studied one version of axiomatic set theory, was to say that there are some sets and we know what they are and we know that the Russell paradox can't happen now, so let's go on.
It appears that the OP and alternatives to the usual treatment of the real numbers are based on what can be described. This issue doesn't impress, or, really, concern me. To me, for just an easy answer, there is the real line with points, and that's description enough for me. Apparently the OP wants a description in terms of digits and is bothered that uncountably infinitely many reals need countably infinitely many decimal digits to be described. Okay, if don't like all those digits, then just return to the points on the line and let those points be the description. Good enough for me, but at this point I have quite different fish to fry getting my business going, really like the real numbers and what classic pure and applied math do with them, and see no good reason to change the foundations of what I do.
More generally, it appears that computer science is struggling to find something to do beyond the biggies of quicksort, heap sort, merge sort, AVL trees, red-black trees, BNF, YACC, LALR parsing, relational database, P versus NP, etc. So computer science wants to take parts of statistics, optimization, control theory, and now the foundations of math for its own and, in those fields, do things differently.
Maybe I'm missing a point: Maybe the idea is to have all the 'numerical' data computing works with be describable in some finite way, that is, not just a countably infinite sequences of digits, and, thus, get rid of, say, numerical error. Maybe. Seems a bit far fetched.
Good grief! In axiomatic set theory, introducing 'classes' was the "get out clause" from the Russell paradox of the the set of all sets that are not members of themselves. So, the patch, the time I studied one version of axiomatic set theory, was to say that there are some sets and we know what they are and we know that the Russell paradox can't happen now, so let's go on.
It appears that the OP and alternatives to the usual treatment of the real numbers are based on what can be described. This issue doesn't impress, or, really, concern me. To me, for just an easy answer, there is the real line with points, and that's description enough for me. Apparently the OP wants a description in terms of digits and is bothered that uncountably infinitely many reals need countably infinitely many decimal digits to be described. Okay, if don't like all those digits, then just return to the points on the line and let those points be the description. Good enough for me, but at this point I have quite different fish to fry getting my business going, really like the real numbers and what classic pure and applied math do with them, and see no good reason to change the foundations of what I do.
More generally, it appears that computer science is struggling to find something to do beyond the biggies of quicksort, heap sort, merge sort, AVL trees, red-black trees, BNF, YACC, LALR parsing, relational database, P versus NP, etc. So computer science wants to take parts of statistics, optimization, control theory, and now the foundations of math for its own and, in those fields, do things differently.
Maybe I'm missing a point: Maybe the idea is to have all the 'numerical' data computing works with be describable in some finite way, that is, not just a countably infinite sequences of digits, and, thus, get rid of, say, numerical error. Maybe. Seems a bit far fetched.
You argued (without much detail, but I'll buy it) for completeness, but then snuck in ordered-ness and Archimedean-ness. As a p-adic analyst, I object to taking these latter two characteristics for granted as necessary for mathematics.
(Also, one has to be careful about the meaning of 'complete' in the uniqueness statement; i.e., it must be understood to mean complete as an ordered field (satisfying the least-upper-bound property), not just complete as a uniform space (having every Cauchy sequence converge). See Paul Sally's "Tools of the trade" (http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345) for some discussion of this.)
(Also, one has to be careful about the meaning of 'complete' in the uniqueness statement; i.e., it must be understood to mean complete as an ordered field (satisfying the least-upper-bound property), not just complete as a uniform space (having every Cauchy sequence converge). See Paul Sally's "Tools of the trade" (http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345) for some discussion of this.)
I was assuming that for counting, measuring,
and arithmetic, we want a field (you know,
addition, multiplication, both with an identity
element and inverses, associativity,
a distributed law, commutativity). We want
order -- that is bigger and smaller.
And likely we want Archimedean order.
So, if we was also want each nonempty set bounded above to have a least upper bound, then we are stucko with the usual reals.
For algebra, and in particular number theory, already in undergraduate school one of my math profs declared that I'm an analyst and not an algebraist. The difference? As that math prof explained, it: "Analysis has an idea behind it. Algebra is just pushing symbols around." I can think intuitively about analysis and often convert the intuitive ideas into good proofs; in algebra, mostly I can't do such a thing. I ended up writing my honors paper in group representations -- I didn't like such concentration on algebra.
For using strange constructions from algebra or computer science to replace the reals, I will have to decline to buy in based if only on ignorance of the offering. But somehow I suspect that the reals are the right answer!
So, if we was also want each nonempty set bounded above to have a least upper bound, then we are stucko with the usual reals.
For algebra, and in particular number theory, already in undergraduate school one of my math profs declared that I'm an analyst and not an algebraist. The difference? As that math prof explained, it: "Analysis has an idea behind it. Algebra is just pushing symbols around." I can think intuitively about analysis and often convert the intuitive ideas into good proofs; in algebra, mostly I can't do such a thing. I ended up writing my honors paper in group representations -- I didn't like such concentration on algebra.
For using strange constructions from algebra or computer science to replace the reals, I will have to decline to buy in based if only on ignorance of the offering. But somehow I suspect that the reals are the right answer!
Got any links to expound on some of your notes?
Or would non-mathematicians just be better off starting from the beginning..
Thanks for the book mention. It's now sitting in my Amazon cart.
It's a fun book, likely intended to
be entertaining, like a dessert
buffet. It's elegantly done.
The first chapter
connects well with this thread.
Some of the results in the later chapters are also mind blowing. Seeing some of those results in a course in measure theory, I staggered around for about two days wondering how a universe could exist with such things being true.
Some of the results in the later chapters are also mind blowing. Seeing some of those results in a course in measure theory, I staggered around for about two days wondering how a universe could exist with such things being true.
This reminded me of http://en.m.wikipedia.org/wiki/Berry_paradox
> It is well proven that Aleph one, which is the infinity of the real numbers, is undeniably bigger than the infinity of the natural numbers.
This language really aggravates me. Thus far, there is no definition for what it means for one infinite series of numbers to be "bigger" than another.
> bear in mind that the set of real numbers is “even more infinite", and that’s the closest I can give you to an intuitive description.)
Again, there is no definition for what "even more infinite" means.
It seems like it's standard practice to talk to newbies about math without defining all your terms, and as a math newbie, that really turns me off. Sometimes it feels like math people are trying to "get away with" something, like politicians.
This language really aggravates me. Thus far, there is no definition for what it means for one infinite series of numbers to be "bigger" than another.
> bear in mind that the set of real numbers is “even more infinite", and that’s the closest I can give you to an intuitive description.)
Again, there is no definition for what "even more infinite" means.
It seems like it's standard practice to talk to newbies about math without defining all your terms, and as a math newbie, that really turns me off. Sometimes it feels like math people are trying to "get away with" something, like politicians.
There are several different definitions for comparing infinite quantities, and I've used one of them.
If I defined all the terms, my article would be twice as long (and it's too long as it is.) Whoever wants precise technical terms is welcome to go on Wikipedia.
If I defined all the terms, my article would be twice as long (and it's too long as it is.) Whoever wants precise technical terms is welcome to go on Wikipedia.
The standard intuitive explanation seems pretty easy and worthwhile:
Two sets are the same size if and only if you can pair members up.
{1, 2, 3} and {4, 5, 6}, obviously.
{1, 3, 5...} and {2, 4, 6...} are too, you can pair them up (1, 2) (3, 4) (5,6) ...
But some sets aren't the same size; you can't pair them up. It's easy if they're both finite, or one is infinite. If both are infinite, well, if they're not the same size, one has to be larger: there are elements in one that are "left over" after trying to pair them up. That's the bigger one. Cantor proved that this does, in fact, happen. The reals can't be paired up with integers.
Two sets are the same size if and only if you can pair members up.
{1, 2, 3} and {4, 5, 6}, obviously.
{1, 3, 5...} and {2, 4, 6...} are too, you can pair them up (1, 2) (3, 4) (5,6) ...
But some sets aren't the same size; you can't pair them up. It's easy if they're both finite, or one is infinite. If both are infinite, well, if they're not the same size, one has to be larger: there are elements in one that are "left over" after trying to pair them up. That's the bigger one. Cantor proved that this does, in fact, happen. The reals can't be paired up with integers.
Thanks. I don't know if this is the right place to get into this, but I still find that explanation aggravating. Perhaps (probably) if I went and read Cantor's original work, I would be satisfied. But perhaps you can save me the trouble.
Here is my problem. You actually can't pair up the reals with the integers, simply because the reals cannot be enumerated. If you take two sets whose members actually can be enumerated, you can pair them up up long as you want.
To reiterate: I'm claiming that the "pairing" operation is not defined validly here, because it would rely on enumerating the elements of both sets, which you cannot do for the reals. Since the proposed definition of "bigger" rests on the "pairing" operation, that definition doesn't appear to be valid to me.
Here is my problem. You actually can't pair up the reals with the integers, simply because the reals cannot be enumerated. If you take two sets whose members actually can be enumerated, you can pair them up up long as you want.
To reiterate: I'm claiming that the "pairing" operation is not defined validly here, because it would rely on enumerating the elements of both sets, which you cannot do for the reals. Since the proposed definition of "bigger" rests on the "pairing" operation, that definition doesn't appear to be valid to me.
> There are several different definitions for comparing infinite quantities, and I've used one of them.
Well, that makes it even worse. Now you're saying, "There are multiple definitions, and I used one of them, but I did not specify which one."
> Whoever wants precise technical terms is welcome to go on Wikipedia.
All right, but in the meantime, when you use terms that you leave undefined, you turn away anyone besides people who already know what you are saying.
Well, that makes it even worse. Now you're saying, "There are multiple definitions, and I used one of them, but I did not specify which one."
> Whoever wants precise technical terms is welcome to go on Wikipedia.
All right, but in the meantime, when you use terms that you leave undefined, you turn away anyone besides people who already know what you are saying.
The charming bit of this story shows something I think should be part of any education - the most fun we have is when we go out and think about things and discover stuff on our own. Getting on to this path is the sure fire way to get out of the "grades game" that college can get you into playing.
I have notes of discovering[1] the Cauchy-Riemann equations for f(z) before I had any clear notion of analyticity or whatever. Gosh! What adrenaline flows!
[1] Deliberate choice here, instead of "rediscovering".
I have notes of discovering[1] the Cauchy-Riemann equations for f(z) before I had any clear notion of analyticity or whatever. Gosh! What adrenaline flows!
[1] Deliberate choice here, instead of "rediscovering".
Anyone interested in this would immensely enjoy Meta Math! by Gregory Chaitin. Basically, he demonstrates that there are theorems which are randomly true: they're true for no particular reason. It's, of course, deeply connected with Gödel's work.
If anyone's working in this space, I'd love to chat with people familiar this stuff.
Edit: arXiv PDF preprint is at http://arxiv.org/pdf/math/0404335.pdf
If anyone's working in this space, I'd love to chat with people familiar this stuff.
Edit: arXiv PDF preprint is at http://arxiv.org/pdf/math/0404335.pdf
Cantor's diagonal argument. I learned it all in high-school!
You learned it, but the author worked it out for himself.
Good for him - kudos.
Good for him - kudos.
He had probably previously encountered Cantor's diagonalization technique for proving the uncountability of the reals. He just saw how to apply the same technique to the question of describability.
It's important to note that the "diagonal argument" used to show countability of rationals or describable numbers is completely different from the one used to show the uncountability of the reals. In fact, the two counting arguments used to show countability of rationals and describable numbers are themselves quite different (I would say the latter isn't even a diagonal argument at all; it just goes through a countable union of finite sets one by one).
[deleted]
My message to the OP - have a look at Gregory Chaitin work :)
I had a similar experience working with products of numbers of the form (a+b)/(c+d), and then I showed it to John Conway (lucky me, I had access to the master), who instantly recognized that I had only stumbled across a known realization of GL(2).
Sigh...
Also (hehe): quantum theory, everything is quantized. So as far as I understand physics, indescribable numbers aren't god's numbers, they're actually our own invention.
Sigh...
Also (hehe): quantum theory, everything is quantized. So as far as I understand physics, indescribable numbers aren't god's numbers, they're actually our own invention.
what the author means to allude to, through some nonsensical rambling, are the incomputable numbers [1]
the cardinality of all real numbers that can be described by a terminating computer program to some accuracy is a countable set (since the number of such programs is countable) however, the cardinality of the reals is uncountable.
hence most real numbers cannot be computed beyond a certain accuracy.
Edit (additionally): the set of computable numbers forms a field (if a,b are computable, so is their sum, etc). and there are several movements in "constructive" mathematics, to work exclusively in this field, instead of the field of real numbers. however, many cornerstone theorems in analysis fail in this context, such as, the least upper bound of a bounded increasing computable sequence of computable numbers need not be a computable number [1].
[1] http://en.wikipedia.org/wiki/Computable_number
the cardinality of all real numbers that can be described by a terminating computer program to some accuracy is a countable set (since the number of such programs is countable) however, the cardinality of the reals is uncountable.
hence most real numbers cannot be computed beyond a certain accuracy.
Edit (additionally): the set of computable numbers forms a field (if a,b are computable, so is their sum, etc). and there are several movements in "constructive" mathematics, to work exclusively in this field, instead of the field of real numbers. however, many cornerstone theorems in analysis fail in this context, such as, the least upper bound of a bounded increasing computable sequence of computable numbers need not be a computable number [1].
[1] http://en.wikipedia.org/wiki/Computable_number
Yeah, but you can describe many incomputable numbers. Indescribable numbers are not the incomputable numbers- Chaitin's constant's a nice one, it's the proportion of Turing machines that halt. Described. Now, compute it...
Way too impressed with numbers. The height of a helium balloon is only connected with numbers in the mind of a mathematician. Its actually not specifically anywhere, what with defining what constitutes the position of the balloon (the top? The bottom? an imaginary centroid? All are unmeasurable in an absolute way) and quantum mechanics and all.
[deleted]
[deleted](1)
I somehow misread the title as something like "The theorem that prevented me from falling in love with math". The article actually still made sense up until the very end where I expected the author to turn out as a finitist.
Reminds me of Zeno's paradoxes. They also impressed me as a kid http://en.wikipedia.org/wiki/Zeno%27s_paradoxes
Wow.. After having read the comments here, I now know how _little_ I know about even sets of numbers.
I guess it's back to human-interest stories of the less endowed hacker and onto the Ubuntu 13.04 article...
I guess it's back to human-interest stories of the less endowed hacker and onto the Ubuntu 13.04 article...
[deleted]
No EE would ever forget to mention i, sqrt(-1), that is my favorite, it makes what we are doing right now possible.
That is a very cool story :-)
P.S. trying to work out what proof is being used here... Proof by contradiction perhaps?
P.S. trying to work out what proof is being used here... Proof by contradiction perhaps?
reminds me of the berry paradox
from wikipedia: "an expression like 'the smallest positive integer not definable in fewer than twelve words' (note that this defining phrase has fewer than twelve words)"
from wikipedia: "an expression like 'the smallest positive integer not definable in fewer than twelve words' (note that this defining phrase has fewer than twelve words)"
I thought of that too. Which leads me to think that the proof status of the OP's "theorem" is less clear. You cannot exhibit a deterministic algorithm that maps every English phrase to the integer that phrase describes, unless you are prepared to accept that some phrases like "the smallest positive integer not definable in fewer than twelve words", are meaningless or illegal. (The thing is, once you exhibit such a mapping, that phrase immediately obtains an obvious meaning, and so it "should" be included in the domain, which would then lead to a contradiction... so you will be stuck with an obviously deficient mapping.)
In that case, I'm not sure if you could write a formally rigorous proof in English. You might come up with some rule to monster-bar such meta-descriptive phrases as "the smallest positive integer not definable ..."; I suspect many such rules, perhaps all of them, would rule out the meta-descriptive language needed to state the conclusion. (How do you formally define "describable" without exhibiting an algorithm that computes integers from their descriptions? Perhaps you'd be satisfied by merely constraining what "describable" could mean...) Even if there are a few such rules under which the proof is valid English, is it not kind of arbitrary which rule you choose, and kind of empty to say "I proclaim this choice to be the right one, and then my proof is valid"?
In that case, I'm not sure if you could write a formally rigorous proof in English. You might come up with some rule to monster-bar such meta-descriptive phrases as "the smallest positive integer not definable ..."; I suspect many such rules, perhaps all of them, would rule out the meta-descriptive language needed to state the conclusion. (How do you formally define "describable" without exhibiting an algorithm that computes integers from their descriptions? Perhaps you'd be satisfied by merely constraining what "describable" could mean...) Even if there are a few such rules under which the proof is valid English, is it not kind of arbitrary which rule you choose, and kind of empty to say "I proclaim this choice to be the right one, and then my proof is valid"?
See also Godel's incompleteness theorem (i.e. "this statement is false.")
Aleph 1 is not the cardinality of the Reals (this is also noted in the top comment)
http://en.wikipedia.org/wiki/Continuum_hypothesis
http://en.wikipedia.org/wiki/Continuum_hypothesis
They are real numbers, for which we have just proven it is impossible to find a description that will match them. We have proven that no description will ever describe them.
Of course you can describe them. But describe them in terms of what? I think that's the key. Let's say you have a pencil and you want to describe its length, which will be a unit multiplied by a number. If I were to try to describe the true length in meters it will be: 0.0178(...) * meters. This would be an "indescribable" number the author talks about.
However, I can just describe it in terms of itself and call it one pencil long - we use the pencil itself as the basis of the unit so the number we multiply the unit to is just: 1 * pencil long.
Of course you can describe them. But describe them in terms of what? I think that's the key. Let's say you have a pencil and you want to describe its length, which will be a unit multiplied by a number. If I were to try to describe the true length in meters it will be: 0.0178(...) * meters. This would be an "indescribable" number the author talks about.
However, I can just describe it in terms of itself and call it one pencil long - we use the pencil itself as the basis of the unit so the number we multiply the unit to is just: 1 * pencil long.
> "describe them in terms of what?"
Describe them (completely) in terms of any finite series of symbols.
Some numbers can be described as "7". Some as "pencil length". Some as "the fourth zero of the third Bessel function of the first kind". These are all describable numbers.
Yet there are vastly more numbers that cannot be described in this way -- vastly more numbers that we miss than that we hit.
Describe them (completely) in terms of any finite series of symbols.
Some numbers can be described as "7". Some as "pencil length". Some as "the fourth zero of the third Bessel function of the first kind". These are all describable numbers.
Yet there are vastly more numbers that cannot be described in this way -- vastly more numbers that we miss than that we hit.
What you've shown is that that particular number (0.0178.../the length of the pencil in metres) is describable. This isn't the same as showing every real number is describable. There are some numbers which are not the length of anything (in metres), or the mass of anything (in kilograms), or the square root or sin of anything. You could try to capture more numbers by using descriptions like "the length of this pencil in feet" and other made-up units of measurement, but you'll never describe them all.
"describe them in terms of what?"
Decimal system :)
Interesting philosophical point though.
Decimal system :)
Interesting philosophical point though.
Decimal system (well, numbers in general) is a great way to describe things as they provide infinite accuracy both in positive and in negative directions. But you must describe them relative to something - some kind of unit.
So your balloon, to fully described its length, you have chosen to describe it relative to meters. Here's the kicker - how well you can measure the length of the balloon depends also on how well you can measure a meter. In the real world, if you try to measure both, the decimal number that describes how relative a meter is to your balloon will only be limited by how accurate your methods of measuring are. You can develop better measuring technology that will forever approach but never reach the True value (only God knows). It is if you try to measure an analog signal, you can only get a digital estimation. But extracting knowledge requires energy, so you need greater computing power to measure an analog signal but all the computing power in the universe couldn't acquire the True value. This is the result of the real world being nondiscrete and containing infinite knowledge. You can measure things by proportion (such as tau (2*pi) being the relative constant of circle circumference to radius); these numbers are transcendental and we don't know their True value. Your "indescribable" numbers are as indescribable as transcendentals. So yes the decimal goes on forever, but you can still describe it in terms of itself and just give a constant name (like pi).
So your balloon, to fully described its length, you have chosen to describe it relative to meters. Here's the kicker - how well you can measure the length of the balloon depends also on how well you can measure a meter. In the real world, if you try to measure both, the decimal number that describes how relative a meter is to your balloon will only be limited by how accurate your methods of measuring are. You can develop better measuring technology that will forever approach but never reach the True value (only God knows). It is if you try to measure an analog signal, you can only get a digital estimation. But extracting knowledge requires energy, so you need greater computing power to measure an analog signal but all the computing power in the universe couldn't acquire the True value. This is the result of the real world being nondiscrete and containing infinite knowledge. You can measure things by proportion (such as tau (2*pi) being the relative constant of circle circumference to radius); these numbers are transcendental and we don't know their True value. Your "indescribable" numbers are as indescribable as transcendentals. So yes the decimal goes on forever, but you can still describe it in terms of itself and just give a constant name (like pi).
The simple explanation for incompressibility goes something like this: Compression means reversibly mapping longer bitstrings to shorter bitstrings. For each bit you add to the length of a string, you multiply the number of values it can represent by two. That means you cannot uniquely (i.e. reversibly) represent each bitstring having n bits with a bitstring having m bits where n > m, because you run out of unique values of the shorter bitstrings before you have a representation for each of the longer bitstrings. QED.
Now you just apply that to numbers with infinite precision. The number "exactly 4.5" is really 4.5000000… meaning "4.5" followed by an infinite number of zeros. That number, despite having infinite precision, is one we compress into less than infinite storage. Various other numbers (like four and one third) are likewise. But as we just proved, there have to exist some numbers with infinite precision that we don't represent with anything less than an infinite number of symbols.
The interesting thing about this is that you can never say that any specific number is incompressible and thus indescribable. You can take any bitstring (but not all bitstrings) of any length, including infinite, and assign a specific shorter (and finite) bitstring to represent it. You then have a finite encoding for that specific infinite sequence of symbols which can henceforth be used to describe it. You just can't do it for every infinite bitstring because you have insufficiently many finite bitstrings with which to represent them.