Can the Universe hold all of mathematics?
June 23, 2009 5:33 AM Subscribe
Can the Universe hold all of mathematics?
First assumption: The universe is finite in size and time. (Size, OK, but time is undetermined AFAIK.)
Second assumption: There is some scale below which information cannot be packed. At the planck scale, say. Put another way, there is a maximum information density to the universe.
These two assumptions imply that there is some maximum amount of information storable in the universe.
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information. The reals, for instance. Or, if that's not "information" in a strict sense, consider Godel's Incompleteness Theorem. It basically says that no matter how big the axiom list, there's always another one you can add.
Where is this information stored if not the universe?
Running this past an acquaintance of mine, he first suggested that while space was quantized, time wasn't. I countered by noting that General Relativity doesn't differentiate between the two.
His second attempt to wiggle free was to cloud the issue with a discussion of "creating" vs "discovering" mathematics. However, I think this is a red herring. Whether one creates or discovers, the information exists and had to come from somewhere. (There's a Conservation of Information principle, right? Entropy?)
Let's say I had a box. When I crank the handle, it applies Godel's method and pops out a new mathematical axiom that can't be proved from the existing list. *crank* P=NP! *crank* Riemann! *crank* Etc! I furiously scribble all these down at the tiniest scale possible.
At some point, the universe will be completely packed with information. I crank the handle one more time. And....?
Now that I think about it, how can such a box exist? There's much more information coming out of that box than the space(time) inside can hold. Is "raw information" leaking into the box from the universe? My understanding was that an "information generator" such as this box couldn't produce more information than it was "made of". That helpfully prevents the box from filling the universe up (whew!) but does not explain where all the information of mathematics is coming from.
First assumption: The universe is finite in size and time. (Size, OK, but time is undetermined AFAIK.)
Second assumption: There is some scale below which information cannot be packed. At the planck scale, say. Put another way, there is a maximum information density to the universe.
These two assumptions imply that there is some maximum amount of information storable in the universe.
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information. The reals, for instance. Or, if that's not "information" in a strict sense, consider Godel's Incompleteness Theorem. It basically says that no matter how big the axiom list, there's always another one you can add.
Where is this information stored if not the universe?
Running this past an acquaintance of mine, he first suggested that while space was quantized, time wasn't. I countered by noting that General Relativity doesn't differentiate between the two.
His second attempt to wiggle free was to cloud the issue with a discussion of "creating" vs "discovering" mathematics. However, I think this is a red herring. Whether one creates or discovers, the information exists and had to come from somewhere. (There's a Conservation of Information principle, right? Entropy?)
Let's say I had a box. When I crank the handle, it applies Godel's method and pops out a new mathematical axiom that can't be proved from the existing list. *crank* P=NP! *crank* Riemann! *crank* Etc! I furiously scribble all these down at the tiniest scale possible.
At some point, the universe will be completely packed with information. I crank the handle one more time. And....?
Now that I think about it, how can such a box exist? There's much more information coming out of that box than the space(time) inside can hold. Is "raw information" leaking into the box from the universe? My understanding was that an "information generator" such as this box couldn't produce more information than it was "made of". That helpfully prevents the box from filling the universe up (whew!) but does not explain where all the information of mathematics is coming from.
but mathematics/information is not really an "Object In the Universe". why need it be stored anywhere. I doint' think your question makes sense.
posted by mary8nne at 5:46 AM on June 23, 2009
posted by mary8nne at 5:46 AM on June 23, 2009
One could argue that a finite amount of information exists and it just keeps getting recycled in extraordinary ways. Much like a finite # of elements exist, though a near infinite amount of combinations. You can come up with more compounds that don't exist in nature, but not without using the finite amount of basic stuff.
This is a good question, and I'm sure you'll get more cogent responses than this one.
No information was employed in the authorship of this response.
posted by Potomac Avenue at 5:51 AM on June 23, 2009 [1 favorite]
This is a good question, and I'm sure you'll get more cogent responses than this one.
No information was employed in the authorship of this response.
posted by Potomac Avenue at 5:51 AM on June 23, 2009 [1 favorite]
Mathematics is a product of the human mind, a way of understanding objective reality.
And, like the every creation of the human mind, it is imperfect. Mathematics does not perfectly fit the objective universe. The work of the great German mathematician, Kurt Godel, tells us that any mathematical system is inherently either incomplete or inaccurate. If you want a complete system of describing the universe, it will be inaccurate. If you want an accurate mathematical system, it will be incomplete.
From Godel's work, I would say, the answer to your questions is: no.
posted by Flood at 5:56 AM on June 23, 2009 [3 favorites]
And, like the every creation of the human mind, it is imperfect. Mathematics does not perfectly fit the objective universe. The work of the great German mathematician, Kurt Godel, tells us that any mathematical system is inherently either incomplete or inaccurate. If you want a complete system of describing the universe, it will be inaccurate. If you want an accurate mathematical system, it will be incomplete.
From Godel's work, I would say, the answer to your questions is: no.
posted by Flood at 5:56 AM on June 23, 2009 [3 favorites]
Well, your question assumes that we actually know exactly what makes up this universe, it's boundaries, and whether or not it's part of a Multiverse. At this point in time, the majority of the actual mass that makes up the known universe is a largely unknown mystery. So there's no way to rationally use the known constraints of this framework to come to some sort of understanding of how it relates to mathematics, another noble - and incomplete - body of knowledge. I'm neither a mathematician nor astronomer - but I'm reasonably interested in both, especially the latter - so take that into consideration when reading the above.
posted by dbiedny at 6:01 AM on June 23, 2009
posted by dbiedny at 6:01 AM on June 23, 2009
Loto: to be fair, a finite volume can still be expanding.
DU: This might or might not be appropriate, but cosmologist Max Tegmark's Mathematical Universe Hypothesis sprang to mind when I read your question. Food for thought anyhow. (Caveat: frames and links to New Scientist on his site.)
posted by aught at 6:01 AM on June 23, 2009
DU: This might or might not be appropriate, but cosmologist Max Tegmark's Mathematical Universe Hypothesis sprang to mind when I read your question. Food for thought anyhow. (Caveat: frames and links to New Scientist on his site.)
posted by aught at 6:01 AM on June 23, 2009
A recursive relation describing an infinite sequence can neatly pack an infinite amount of numbers in a finite amount of space.
You need a better definition of information, as well as one for mathematics.
posted by Dr Dracator at 6:02 AM on June 23, 2009 [3 favorites]
You need a better definition of information, as well as one for mathematics.
posted by Dr Dracator at 6:02 AM on June 23, 2009 [3 favorites]
I think you're conflating "mathematical ideas in the abstract" and "physical notation of mathematical ideas." Yes, I suppose you could fill up the universe with the latter, but I don't think that proves anything pertaining to the former.
posted by letourneau at 6:03 AM on June 23, 2009 [4 favorites]
posted by letourneau at 6:03 AM on June 23, 2009 [4 favorites]
I enjoyed "Warmth Disperses and Time Passes" by Hans Christian von Baeyer for its discussion of thermodynamic and information entropy. You might also look for a discussion of Chaitin complexity. I can't just now put my hand on the book that introduced that concept to me.
One answer to your question is that the Universe can contain more of mathematics than the collective human intellectual tradition.
posted by fantabulous timewaster at 6:07 AM on June 23, 2009
One answer to your question is that the Universe can contain more of mathematics than the collective human intellectual tradition.
posted by fantabulous timewaster at 6:07 AM on June 23, 2009
Where is this information stored if not the universe?
Just ask that again, but as a rhetorical question.
posted by UbuRoivas at 6:09 AM on June 23, 2009
Just ask that again, but as a rhetorical question.
posted by UbuRoivas at 6:09 AM on June 23, 2009
I believe there is a formal proof that it can't by someone like hilbert or godel, but it's been so long since I studied I don't recall - ah bingo
DU do your own homework ;)
posted by fistynuts at 6:11 AM on June 23, 2009
DU do your own homework ;)
posted by fistynuts at 6:11 AM on June 23, 2009
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information.
Response 1:
Depends on your definition of "information." Certainly, there are an infinite number of true mathematical equations which can be expressed.
Suppose I want a way to represent a string consisting of a repeating number of occurrences of a substring. Let's say that substring is the letter a. I'll represent the longer strings as follows:
a·3=aaa
a·13=aaaaaaaaaaaaa
a·124=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Now consider the following:
a·∞
Voila! I have just represented an infinite amount of information (for one sense of "information"), not just within the universe, but within a handful of bytes!
But for another sense of "information," I have not represented an infinite amount of information, for anything which can be encoded (including both the representation and the encoding scheme itself) finitely is itself finite. (If you think of my representation as a compression scheme, this sense of "information" specifies that something carries only as much information as the compressed form, not the uncompressed form.)
It does not seem that mathematics represents an infinite amount of information in the latter sense, since standard mathematics is based on a finite number of axioms plus a finite set of rules for generating mathematical statements. (Although you could add more and more axioms indefinitely, standard mathematics does not.)
Response 2:
Mathematics exists only in the human mind (and possibly other sentient minds in the universe). Mathematics does not exist in the same sense that stars or planets or the Eiffel Tower exists. It makes no more sense to ask "how can an infinite number of mathematical statements exist in a finite universe" than it does to ask "how can an infinite number of leprechauns exist in a finite universe" or "how can Borges' infinite library exist in a finite universe?" Just because humans can imagine an infinite number of leprechauns or an infinite number of possible books or an infinite mathematics does not mean that they must "exist" in any real sense which demands they be contained within a finite universe.
posted by DevilsAdvocate at 6:14 AM on June 23, 2009 [6 favorites]
Response 1:
Depends on your definition of "information." Certainly, there are an infinite number of true mathematical equations which can be expressed.
Suppose I want a way to represent a string consisting of a repeating number of occurrences of a substring. Let's say that substring is the letter a. I'll represent the longer strings as follows:
a·3=aaa
a·13=aaaaaaaaaaaaa
a·124=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Now consider the following:
a·∞
Voila! I have just represented an infinite amount of information (for one sense of "information"), not just within the universe, but within a handful of bytes!
But for another sense of "information," I have not represented an infinite amount of information, for anything which can be encoded (including both the representation and the encoding scheme itself) finitely is itself finite. (If you think of my representation as a compression scheme, this sense of "information" specifies that something carries only as much information as the compressed form, not the uncompressed form.)
It does not seem that mathematics represents an infinite amount of information in the latter sense, since standard mathematics is based on a finite number of axioms plus a finite set of rules for generating mathematical statements. (Although you could add more and more axioms indefinitely, standard mathematics does not.)
Response 2:
Mathematics exists only in the human mind (and possibly other sentient minds in the universe). Mathematics does not exist in the same sense that stars or planets or the Eiffel Tower exists. It makes no more sense to ask "how can an infinite number of mathematical statements exist in a finite universe" than it does to ask "how can an infinite number of leprechauns exist in a finite universe" or "how can Borges' infinite library exist in a finite universe?" Just because humans can imagine an infinite number of leprechauns or an infinite number of possible books or an infinite mathematics does not mean that they must "exist" in any real sense which demands they be contained within a finite universe.
posted by DevilsAdvocate at 6:14 AM on June 23, 2009 [6 favorites]
To my limited understanding, your notion that there is a maximum (if enormous) amount of information in the universe is thought by many who think about these things to be accurate. A paper that you might want to look at suggests one bound of about 10^122 bits. The notion that information is conserved, however, is entirely wrong. Information, being defined as more or less 1/Entropy, is very frequently lost due to thermodynamics because order tends to decay into disorder. This would be an equivalent effect of the second law of thermodynamics, that entropy doesn't decrease.
The other problem is in interpreting "information" appropriately. It is an abstract notion related to the predictability of correctly observing a signal, where signal is broadly defined. When you talk about something having a finite amount of information, what that tells you is how much information you can store on it. If you have two binary switches, say, you can store 2 bits of information in it. If you have a gas of atoms that you can control extremely well, one can calculate from statistical physics and information theory how many bits of information you can store in it before you run out of physical ways to encode the information. Mathematical axioms are no different than any other piece of information generated by someone. The same bounds would be created if you just wanted to say some binary representation of "Hi!" as many times as possible.
posted by Schismatic at 6:25 AM on June 23, 2009
The other problem is in interpreting "information" appropriately. It is an abstract notion related to the predictability of correctly observing a signal, where signal is broadly defined. When you talk about something having a finite amount of information, what that tells you is how much information you can store on it. If you have two binary switches, say, you can store 2 bits of information in it. If you have a gas of atoms that you can control extremely well, one can calculate from statistical physics and information theory how many bits of information you can store in it before you run out of physical ways to encode the information. Mathematical axioms are no different than any other piece of information generated by someone. The same bounds would be created if you just wanted to say some binary representation of "Hi!" as many times as possible.
posted by Schismatic at 6:25 AM on June 23, 2009
Isn't mathematics more to do with how our brains work than some physical entity?
posted by mattoxic at 6:28 AM on June 23, 2009
posted by mattoxic at 6:28 AM on June 23, 2009
Response by poster: A recursive relation describing an infinite sequence can neatly pack an infinite amount of numbers in a finite amount of space.
But infinite sequence != infinite amount of information.
As for the "it's all in your head" responses: I think you are falling for the same red herring as my acquaintance. Consider this statement: "Unicorns are horses that have a horn."
Do unicorns really exist? No.
Do unicorns need to be stored somewhere in the universe? No.
Is that statement a piece of information? Yes.
Does that information need to be stored somewhere in the universe? Yes.
It's irrelevant whether the statement was invented by humans or handed down by God. The fact remains that just by the statement existing, it is using up some of the finite information capacity of the universe.
posted by DU at 6:29 AM on June 23, 2009 [1 favorite]
But infinite sequence != infinite amount of information.
As for the "it's all in your head" responses: I think you are falling for the same red herring as my acquaintance. Consider this statement: "Unicorns are horses that have a horn."
Do unicorns really exist? No.
Do unicorns need to be stored somewhere in the universe? No.
Is that statement a piece of information? Yes.
Does that information need to be stored somewhere in the universe? Yes.
It's irrelevant whether the statement was invented by humans or handed down by God. The fact remains that just by the statement existing, it is using up some of the finite information capacity of the universe.
posted by DU at 6:29 AM on June 23, 2009 [1 favorite]
Representations of reality are not reality.
Lets take a simpler version of the concept; pi. I'm in my room here. Lets say I want to write down the length of pi as a decimal number. I will run out paper - and room to store it - before I run out of digits. Does that mean pi cannot exist in my room? If you say that pi only exists in my mind, will it cease to be true once I die from suffocation by paper?
No. Pi exists regardless of whether we write it down or even know about it. But its existance; the ratio of a euclidian circle's circumference to its diameter takes up no physical space at all. Only representing that information in some form, be it paper, in my head, or just drawing a circle takes up space.
Or take newton's laws of motion; they're a pretty good approximation of how mass behaves in certain circumstances, but it's not like you need to carry along extra mass to store the laws in, in order for them to apply to you.
Physics and maths take up no space as they are not mass or energy (which are the same thing anyway), and thus require neither to exist, so we can store an infinite amount of them in a finite mass of universe. Like time; time is not a physical concept, but it definitely exists - so much so we classify it as a dimension.
Or to put it another way; when Jesus is your passenger, that doesn't mean he's physically sitting in your car.
posted by ArkhanJG at 6:30 AM on June 23, 2009 [4 favorites]
Lets take a simpler version of the concept; pi. I'm in my room here. Lets say I want to write down the length of pi as a decimal number. I will run out paper - and room to store it - before I run out of digits. Does that mean pi cannot exist in my room? If you say that pi only exists in my mind, will it cease to be true once I die from suffocation by paper?
No. Pi exists regardless of whether we write it down or even know about it. But its existance; the ratio of a euclidian circle's circumference to its diameter takes up no physical space at all. Only representing that information in some form, be it paper, in my head, or just drawing a circle takes up space.
Or take newton's laws of motion; they're a pretty good approximation of how mass behaves in certain circumstances, but it's not like you need to carry along extra mass to store the laws in, in order for them to apply to you.
Physics and maths take up no space as they are not mass or energy (which are the same thing anyway), and thus require neither to exist, so we can store an infinite amount of them in a finite mass of universe. Like time; time is not a physical concept, but it definitely exists - so much so we classify it as a dimension.
Or to put it another way; when Jesus is your passenger, that doesn't mean he's physically sitting in your car.
posted by ArkhanJG at 6:30 AM on June 23, 2009 [4 favorites]
Ah, you assume the information capacity of the universe is finite. Mass is finite. Energy is finite. Storing information using either of them is finite. The information capacity of the universe is infinite, just as we can store an infinite repeating sequence inside a single symbol, i.e. pi.
posted by ArkhanJG at 6:32 AM on June 23, 2009
posted by ArkhanJG at 6:32 AM on June 23, 2009
DU, you really want to look at Chaitin. Here's a very accessible introduction to his ideas.
Essentially, he would argue that anything that can't fit into the Universe (including Reals!) is about as "real" as Unicorns. So, to answer your questions, no, mathematics cannot exceed the bounds of the Universe - we only believe it can. Also, your imaginary box is bound by physical laws and can only produce a finite amount of information in a finite time - and here we define information in the Kolomgorov sense - as the smallest algorithm which can produce that information.
posted by vacapinta at 6:33 AM on June 23, 2009 [1 favorite]
Essentially, he would argue that anything that can't fit into the Universe (including Reals!) is about as "real" as Unicorns. So, to answer your questions, no, mathematics cannot exceed the bounds of the Universe - we only believe it can. Also, your imaginary box is bound by physical laws and can only produce a finite amount of information in a finite time - and here we define information in the Kolomgorov sense - as the smallest algorithm which can produce that information.
posted by vacapinta at 6:33 AM on June 23, 2009 [1 favorite]
The information capacity of the universe is infinite, just as we can store an infinite repeating sequence inside a single symbol, i.e. pi.
If we can't produce all the digits of pi in the lifetime of the Universe, is it still correct to say it is all really stored in there? I think thats what DU is asking...
posted by vacapinta at 6:35 AM on June 23, 2009 [1 favorite]
If we can't produce all the digits of pi in the lifetime of the Universe, is it still correct to say it is all really stored in there? I think thats what DU is asking...
posted by vacapinta at 6:35 AM on June 23, 2009 [1 favorite]
1st: The first assumption is a big one that many wouldn't necessarily accept.
2nd: Even if the first assuption is accepted, I think your question assumes that "things and concepts that are" have to take up space independent of our ability to conceptualize them. For example, "2 and 2 is 4" takes up a certain amount of space in my head and in the head of everyone whose neurons have organized to record it. There are no neural connections dedicated to "2 and 2" in my cat's head, so it takes up no space in her head, but that doesn't make it less true. If no one had figured out "2 and 2 is 4" then it wouldn't take up any space at all in spite of the fact that 2 things and 2 things would still equal 4 things that no one knew how to count. Similarly, pi takes up a certain amount of space on various calculators and computers and people's neural structures throughout the world to the degree that pi has been calculated. However, it doesn't take up space or fill the universe in any way beyond that even though we know that it does extend in mathematics beyond what we've calculated.
I think this answer is kind of a restating of letourneau's answer above.
Also, Flood's answer could be stated thusly: If there are an infinite number of "mathematics" out there and one were to assume that they were all recorded is some way (a human brain, a group of human brains, computers, etc.) that involved atoms, and if we also assumed that there are a finite number of atoms in the universe then we would have to say the universe isn't big enough for mathematics. But if we don't grant a) a finite universe or b) a physical structure to all the possible mathematics then the universe should have enough room left over to not squish us all.
posted by Quizicalcoatl at 6:39 AM on June 23, 2009
2nd: Even if the first assuption is accepted, I think your question assumes that "things and concepts that are" have to take up space independent of our ability to conceptualize them. For example, "2 and 2 is 4" takes up a certain amount of space in my head and in the head of everyone whose neurons have organized to record it. There are no neural connections dedicated to "2 and 2" in my cat's head, so it takes up no space in her head, but that doesn't make it less true. If no one had figured out "2 and 2 is 4" then it wouldn't take up any space at all in spite of the fact that 2 things and 2 things would still equal 4 things that no one knew how to count. Similarly, pi takes up a certain amount of space on various calculators and computers and people's neural structures throughout the world to the degree that pi has been calculated. However, it doesn't take up space or fill the universe in any way beyond that even though we know that it does extend in mathematics beyond what we've calculated.
I think this answer is kind of a restating of letourneau's answer above.
Also, Flood's answer could be stated thusly: If there are an infinite number of "mathematics" out there and one were to assume that they were all recorded is some way (a human brain, a group of human brains, computers, etc.) that involved atoms, and if we also assumed that there are a finite number of atoms in the universe then we would have to say the universe isn't big enough for mathematics. But if we don't grant a) a finite universe or b) a physical structure to all the possible mathematics then the universe should have enough room left over to not squish us all.
posted by Quizicalcoatl at 6:39 AM on June 23, 2009
Response by poster: I actually did look at Chaitin and a few other places, but they didn't seem to address this question. At least not before page 10....
So, to answer your questions, no, mathematics cannot exceed the bounds of the Universe - we only believe it can.
Right, this was my first reaction too. I figured the universe was non-godelian, so to speak. Just like it was found to be non-euclidian, we might find that the ACTUAL universe couldn't generate an infinite list of axioms.
However, this is looking at the problem from the wrong end. GIVEN that the actual universe can't hold/generate an infinite list, where is the infinite list of Godel's coming from?
...we define information in the Kolomgorov sense - as the smallest algorithm which can produce that information.
I knew there was this definition but didn't know the name, so thanks for adding some facts to the discussion. I can restrict my question down a little bit, maybe: So I have my box, previously described. Inside it are the axioms of mathematics plus Godel. There is some Kolomgorovian "length" to this box, which means it can only produce a finite number of axioms. Yet Godel (shouting from inside) says he proved it can produce an infinite number of axioms. Who is right?
posted by DU at 6:39 AM on June 23, 2009
So, to answer your questions, no, mathematics cannot exceed the bounds of the Universe - we only believe it can.
Right, this was my first reaction too. I figured the universe was non-godelian, so to speak. Just like it was found to be non-euclidian, we might find that the ACTUAL universe couldn't generate an infinite list of axioms.
However, this is looking at the problem from the wrong end. GIVEN that the actual universe can't hold/generate an infinite list, where is the infinite list of Godel's coming from?
...we define information in the Kolomgorov sense - as the smallest algorithm which can produce that information.
I knew there was this definition but didn't know the name, so thanks for adding some facts to the discussion. I can restrict my question down a little bit, maybe: So I have my box, previously described. Inside it are the axioms of mathematics plus Godel. There is some Kolomgorovian "length" to this box, which means it can only produce a finite number of axioms. Yet Godel (shouting from inside) says he proved it can produce an infinite number of axioms. Who is right?
posted by DU at 6:39 AM on June 23, 2009
wait I think i get what you are saying now:
Assume you had a way to write down 'information on every atom in the universe' until they were all written on. (and if the Universe is of finite size then it contains a finite number of atoms say).
if they I uttered a word - I would be bringing more information into the universe. as the utterance is in a sense encoded via sound on atoms of the Universe.
So how does that work?
posted by mary8nne at 6:43 AM on June 23, 2009
Assume you had a way to write down 'information on every atom in the universe' until they were all written on. (and if the Universe is of finite size then it contains a finite number of atoms say).
if they I uttered a word - I would be bringing more information into the universe. as the utterance is in a sense encoded via sound on atoms of the Universe.
So how does that work?
posted by mary8nne at 6:43 AM on June 23, 2009
but mathematics/information is not really an "Object In the Universe". why need it be stored anywhere. I doint' think your question makes sense.
posted by mary8nne at 5:46 AM on June 23
DU's question is phrased poorly, but your answer is not only unhelpful, it betrays your complete lack of knowledge on this matter. Information is a real, tangible thing.
However, DU, I will say that based on the way you put the question, that the information you're referring to literally does not exist. One can always add an axiom, but for it to "take up space," one needs to add it. The uncountable number of possible things (axioms, the names of unicorns) take up no space.
posted by Optimus Chyme at 6:44 AM on June 23, 2009
posted by mary8nne at 5:46 AM on June 23
DU's question is phrased poorly, but your answer is not only unhelpful, it betrays your complete lack of knowledge on this matter. Information is a real, tangible thing.
However, DU, I will say that based on the way you put the question, that the information you're referring to literally does not exist. One can always add an axiom, but for it to "take up space," one needs to add it. The uncountable number of possible things (axioms, the names of unicorns) take up no space.
posted by Optimus Chyme at 6:44 AM on June 23, 2009
Response by poster: One can always add an axiom, but for it to "take up space," one needs to add it.
I don't think that's really true, though. If I have an algorithm that "adds information" the information is already there, compacted within the algorithm. My Godelian Box apparently has an infinite information content, yet by my assumptions above it cannot. Presumably this means my assumptions are false, but which ones and how? Alternatively, is the information coming from outside the universe a la Anathem?
posted by DU at 6:59 AM on June 23, 2009
I don't think that's really true, though. If I have an algorithm that "adds information" the information is already there, compacted within the algorithm. My Godelian Box apparently has an infinite information content, yet by my assumptions above it cannot. Presumably this means my assumptions are false, but which ones and how? Alternatively, is the information coming from outside the universe a la Anathem?
posted by DU at 6:59 AM on June 23, 2009
But infinite sequence != infinite amount of information.
Then why does infinite mathematics == infinite amount of information?
My take on this may be naive, but if all of mathematics is the set of all possible statements conforming to some rules, how is this more infinite than the set of all numbers produced by a different set of rules?
I think your question can be reduced to that of the existance of infinite things. Infinite quantities exist, in the sense that we can describe them and think in a meaningful way about them. Posing a problem in terms of an infinite set is just a convenient way to think about it, one does not need to enumerate every object in the set.
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information.
I think this is were the paradox creeps in. Replace "has" with "can produce" and there is no problem whatsoever.
posted by Dr Dracator at 7:02 AM on June 23, 2009
Then why does infinite mathematics == infinite amount of information?
My take on this may be naive, but if all of mathematics is the set of all possible statements conforming to some rules, how is this more infinite than the set of all numbers produced by a different set of rules?
I think your question can be reduced to that of the existance of infinite things. Infinite quantities exist, in the sense that we can describe them and think in a meaningful way about them. Posing a problem in terms of an infinite set is just a convenient way to think about it, one does not need to enumerate every object in the set.
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information.
I think this is were the paradox creeps in. Replace "has" with "can produce" and there is no problem whatsoever.
posted by Dr Dracator at 7:02 AM on June 23, 2009
But infinite sequence != infinite amount of information.
Precisely. And likewise, infinite number of mathematical statements != infinite amount of information. Also, the statement "an infinite number of mathematical statements could be formulated" is not itself an infinite number of mathematical statements.
Do unicorns really exist? No.
Do unicorns need to be stored somewhere in the universe? No.
Is that statement a piece of information? Yes.
Does that information need to be stored somewhere in the universe?
No. It so happens that the information "unicorns do not exists" is stored in a number of places in this universe (the MetaFilter server now among them), but it does not need to be stored somewhere in the universe. I submit to you that a universe with no sentient life does not store the information "unicorns do not exist." It may contain information about the positions and velocities of numerous subatomic particles, but the labelling of a subset of those particles as "a unicorn" or "not a unicorn" is the product of a sentient mind. A mindless universe (assuming any unicorns therein are not themselves sentient) does not know the difference between "a unicorn" and "a nebula" even if it does have information about the subatomic particles making up each, if they exist in that universe.
The existence of a universe with no unicorns does not imply that the information "unicorns do not exist" exists within that universe.
It's irrelevant whether the statement was invented by humans or handed down by God.
God, being both omnipotent and outside of the universe, can store an infinite amount of information. If you want to include God, all bets are off. Given a godless finite universe, however, an infinite number of statements do not exist.
The fact remains that just by the statement existing
"Unicorns do not exist" does not imply "the statement 'unicorns do not exist' exists."
On preview: the above may not address DU's most recent clarification, so feel free to ignore this entire comment.
posted by DevilsAdvocate at 7:04 AM on June 23, 2009 [1 favorite]
Precisely. And likewise, infinite number of mathematical statements != infinite amount of information. Also, the statement "an infinite number of mathematical statements could be formulated" is not itself an infinite number of mathematical statements.
Do unicorns really exist? No.
Do unicorns need to be stored somewhere in the universe? No.
Is that statement a piece of information? Yes.
Does that information need to be stored somewhere in the universe?
No. It so happens that the information "unicorns do not exists" is stored in a number of places in this universe (the MetaFilter server now among them), but it does not need to be stored somewhere in the universe. I submit to you that a universe with no sentient life does not store the information "unicorns do not exist." It may contain information about the positions and velocities of numerous subatomic particles, but the labelling of a subset of those particles as "a unicorn" or "not a unicorn" is the product of a sentient mind. A mindless universe (assuming any unicorns therein are not themselves sentient) does not know the difference between "a unicorn" and "a nebula" even if it does have information about the subatomic particles making up each, if they exist in that universe.
The existence of a universe with no unicorns does not imply that the information "unicorns do not exist" exists within that universe.
It's irrelevant whether the statement was invented by humans or handed down by God.
God, being both omnipotent and outside of the universe, can store an infinite amount of information. If you want to include God, all bets are off. Given a godless finite universe, however, an infinite number of statements do not exist.
The fact remains that just by the statement existing
"Unicorns do not exist" does not imply "the statement 'unicorns do not exist' exists."
On preview: the above may not address DU's most recent clarification, so feel free to ignore this entire comment.
posted by DevilsAdvocate at 7:04 AM on June 23, 2009 [1 favorite]
DU, are you also making the assumption that the platonist view of mathematics is correct? That is, that mathematical concepts exist independently from the minds of human beings? If not, then there is an out, albeit not a very satisfying one.
To wit: an alternative view of mathematics is the empirical view, that is that so-called abstract ideas like mathematics actually only exist within the physical brains of human beings and certain other animals. Put another way, concepts like numbers, counting, arithmetic, etc only have meaning in our minds. Matter and energy obey physical laws, but ascribing mathematical meaning or interpretation to those behaviors is only something that we do; the meaning has no separate reality.
Obviously there is a finite number of states that may exist within the volume of a human brain or even the collective brains of all humans everywhere. Thus, the empiricist would say that there is a limit to the amount of mathematical information that may exist in the universe.
posted by jedicus at 7:09 AM on June 23, 2009
To wit: an alternative view of mathematics is the empirical view, that is that so-called abstract ideas like mathematics actually only exist within the physical brains of human beings and certain other animals. Put another way, concepts like numbers, counting, arithmetic, etc only have meaning in our minds. Matter and energy obey physical laws, but ascribing mathematical meaning or interpretation to those behaviors is only something that we do; the meaning has no separate reality.
Obviously there is a finite number of states that may exist within the volume of a human brain or even the collective brains of all humans everywhere. Thus, the empiricist would say that there is a limit to the amount of mathematical information that may exist in the universe.
posted by jedicus at 7:09 AM on June 23, 2009
Response by poster: Then why does infinite mathematics == infinite amount of information?
My take on this may be naive, but if all of mathematics is the set of all possible statements conforming to some rules, how is this more infinite than the set of all numbers produced by a different set of rules?
OK, this is a very good point. Perhaps an infinite list of axioms is not an infinite amount of information. I didn't feel too comfortable calling "the reals" an infinite amount of info because they seemed too flat and featureless. But axioms are big and complex, surely they must be information-rich! Perhaps not.
In fact, I'm pretty sure I must have some fundamental misunderstanding of the algorithmic type of information. For instance, each decimal digit of pi must be giving me a little more than 2 bits of information. But a pi-producing algorithm is of finite length and can't produce an infinite amount of information. I cannot be the first person to have thought of that objection, therefore that's not how this works.
posted by DU at 7:10 AM on June 23, 2009
My take on this may be naive, but if all of mathematics is the set of all possible statements conforming to some rules, how is this more infinite than the set of all numbers produced by a different set of rules?
OK, this is a very good point. Perhaps an infinite list of axioms is not an infinite amount of information. I didn't feel too comfortable calling "the reals" an infinite amount of info because they seemed too flat and featureless. But axioms are big and complex, surely they must be information-rich! Perhaps not.
In fact, I'm pretty sure I must have some fundamental misunderstanding of the algorithmic type of information. For instance, each decimal digit of pi must be giving me a little more than 2 bits of information. But a pi-producing algorithm is of finite length and can't produce an infinite amount of information. I cannot be the first person to have thought of that objection, therefore that's not how this works.
posted by DU at 7:10 AM on June 23, 2009
There are different measures of information, Shannon's, Kolmogorov' complexity.
In Kolmogorov 's complexity the amount of information that something contains is the shortest computer program that can generate it. Therefore things like the pi sequence contain only as much information as the computer program used to generate it.
However, if we consider time, then there some computer programs that take an infinite amount of time to answer a question (intractable). Therefore, the universe can not represent the answer to the question they are asking in any finite amount of time.
posted by blueyellow at 7:13 AM on June 23, 2009 [2 favorites]
In Kolmogorov 's complexity the amount of information that something contains is the shortest computer program that can generate it. Therefore things like the pi sequence contain only as much information as the computer program used to generate it.
However, if we consider time, then there some computer programs that take an infinite amount of time to answer a question (intractable). Therefore, the universe can not represent the answer to the question they are asking in any finite amount of time.
posted by blueyellow at 7:13 AM on June 23, 2009 [2 favorites]
Do unicorns really exist? No.
Do unicorns need to be stored somewhere in the universe? No.
Is that statement a piece of information? Yes.
Does that information need to be stored somewhere in the universe? Yes.
I'm frightened to weigh in, because I have a very sketchy grasp of physics and cosmology, but upon reading your clarification, some "logic" sprung into my head. For what it's worth...
Yes, the information has to be stored somewhere: as a pattern in someone's brain. And, of course, that pattern does use up some of the universe's limited resources.
Now, human brains are not like cloud networks (as in Amazon A3). If there's an idea that's too big to store in my brain, I can't spread it over my brain and your brain. It either fits in my brain or I can't store it. True, you and I can each store one-half of the big idea, and we can talk to each other and assemble something from the two halves, but if either one of us is going to hold the big picture in our head, that picture must necessarily be an abbreviation, because neither one of us has the brain capacity to hold the whole thing.
[ You: okay, according to my half, airplanes can fly. My half explains the mechanism behind airplane flight, but I'm not going to bog you down with that. Just take it as a given...
Me: Cool. My half says that IF airplanes can fly, then... ]
So there's no such thing as a space that holds all information. There are just individual brains and storage devices that hold finite amounts of information. If info is combined, the combination must necessarily be abbreviated.
And we're not pulling our information from some magic box where it all already exists. There is no such box. However, there IS a box that holds atomic units that can be combined to create an infinite number of unique bits of info.
For instance, the English alphabet only has 26 letters in it. But those letters can be combined to form an infinite number of words -- in theory. Really, they can't. They can only be combined to form new unique words until all the storage in the universe is filled up. Practically, on Earth, that means that once all the human brains (and hard drives, etc.) are filled with unique combos of letters, no more unique words can exist. All we can say is that IF some more storage somehow got added, we would be able to store more words. But since no more storage can be added, we can't.
Possible words don't exist. They are nowhere. Yes, your unicorn idea exists, but here's something that doesn't exist: some possible animal made by combining parts of two different animals. The IDEA that one could make such an animal DOES exist, but a more specific idea -- detailing what this new animal would look like -- doesn't exist. It doesn't exist in any way, shape or form, because it can't exist until we first specify the two original animals and which parts we're pulling from each. All that exists is the IDEA that one can combine animals. And that's just one idea.
So there are atomic units: existing animals that we know about. And there are a finite number of rules, such as "You can combine parts of two different animals to create a new animal."
Another example: all possible numbers don't exist. I'm not sure what the biggest "thought of" number is these days, but let's say it's a googolplex. If a googleplex exists, does that mean that a googleplex + 1 exists? No! It just means that the idea that you can add a 1 to any number exists.
And that idea is not literally true. It's shorthand for "If you have the storage space to hold the result, you can add one to any number." If all the storage space in the universe is used up, then you CAN'T add a 1. You can see this in the mini-universe of computers. We claim -- in casual conversation -- that computers can add 1 to any number, but they can't. When they reach RAM capacity, they can't handle larger numbers. But they can handle the IDEA of adding 1 to any number.
I'm not sure why you believe there's a platonic box where all ideas already live. Why is this needed. It would be wasteful. All you need are some atomic "letters" and some rules for combining these letters.
posted by grumblebee at 7:14 AM on June 23, 2009
Do unicorns need to be stored somewhere in the universe? No.
Is that statement a piece of information? Yes.
Does that information need to be stored somewhere in the universe? Yes.
I'm frightened to weigh in, because I have a very sketchy grasp of physics and cosmology, but upon reading your clarification, some "logic" sprung into my head. For what it's worth...
Yes, the information has to be stored somewhere: as a pattern in someone's brain. And, of course, that pattern does use up some of the universe's limited resources.
Now, human brains are not like cloud networks (as in Amazon A3). If there's an idea that's too big to store in my brain, I can't spread it over my brain and your brain. It either fits in my brain or I can't store it. True, you and I can each store one-half of the big idea, and we can talk to each other and assemble something from the two halves, but if either one of us is going to hold the big picture in our head, that picture must necessarily be an abbreviation, because neither one of us has the brain capacity to hold the whole thing.
[ You: okay, according to my half, airplanes can fly. My half explains the mechanism behind airplane flight, but I'm not going to bog you down with that. Just take it as a given...
Me: Cool. My half says that IF airplanes can fly, then... ]
So there's no such thing as a space that holds all information. There are just individual brains and storage devices that hold finite amounts of information. If info is combined, the combination must necessarily be abbreviated.
And we're not pulling our information from some magic box where it all already exists. There is no such box. However, there IS a box that holds atomic units that can be combined to create an infinite number of unique bits of info.
For instance, the English alphabet only has 26 letters in it. But those letters can be combined to form an infinite number of words -- in theory. Really, they can't. They can only be combined to form new unique words until all the storage in the universe is filled up. Practically, on Earth, that means that once all the human brains (and hard drives, etc.) are filled with unique combos of letters, no more unique words can exist. All we can say is that IF some more storage somehow got added, we would be able to store more words. But since no more storage can be added, we can't.
Possible words don't exist. They are nowhere. Yes, your unicorn idea exists, but here's something that doesn't exist: some possible animal made by combining parts of two different animals. The IDEA that one could make such an animal DOES exist, but a more specific idea -- detailing what this new animal would look like -- doesn't exist. It doesn't exist in any way, shape or form, because it can't exist until we first specify the two original animals and which parts we're pulling from each. All that exists is the IDEA that one can combine animals. And that's just one idea.
So there are atomic units: existing animals that we know about. And there are a finite number of rules, such as "You can combine parts of two different animals to create a new animal."
Another example: all possible numbers don't exist. I'm not sure what the biggest "thought of" number is these days, but let's say it's a googolplex. If a googleplex exists, does that mean that a googleplex + 1 exists? No! It just means that the idea that you can add a 1 to any number exists.
And that idea is not literally true. It's shorthand for "If you have the storage space to hold the result, you can add one to any number." If all the storage space in the universe is used up, then you CAN'T add a 1. You can see this in the mini-universe of computers. We claim -- in casual conversation -- that computers can add 1 to any number, but they can't. When they reach RAM capacity, they can't handle larger numbers. But they can handle the IDEA of adding 1 to any number.
I'm not sure why you believe there's a platonic box where all ideas already live. Why is this needed. It would be wasteful. All you need are some atomic "letters" and some rules for combining these letters.
posted by grumblebee at 7:14 AM on June 23, 2009
DU, I think you're misunderstanding the definition of information. Information is entirely a signal processing concept, and one that has been generalized to view lots of things as signals. Each digit of pi is not "recorded" anywhere in the universe. Pi is a consequence of euclidean geometry, not something arbitrarily encoded. In fact, given the axioms of geometry, you need zero more information to derive pi. Writing every digit of pi would take an infinite amount of information, but so would writing a string of 1s as long.
But axioms are big and complex, surely they must be information-rich!
This is totally a misnomer. The information contained in them is merely how many bits you have to send to let someone else know the axiom.
posted by Schismatic at 7:22 AM on June 23, 2009 [3 favorites]
But axioms are big and complex, surely they must be information-rich!
This is totally a misnomer. The information contained in them is merely how many bits you have to send to let someone else know the axiom.
posted by Schismatic at 7:22 AM on June 23, 2009 [3 favorites]
Perhaps an infinite list of axioms is not an infinite amount of information.
Actually, I think you've gone too far to the other side and are selling your argument short now. An infinite list of mathematical statements is not necessarily an infinite amount of information. However, an infinite list of axioms (meaning none of them can be derived from any combination of any of the others) would be an infinite amount of information.
But axioms are big and complex, surely they must be information-rich! Perhaps not.
Well, as far as "big and complex and information-rich," not necessarily, depending on how you define "big" and "complex" and "information-rich," but each additional axiom does add some nonzero amount of information. If a new statement added no new information to the axioms you had previously listed, then it could be derived from your previous axioms, and by definition such a statement is not an axiom.
I agree with you that an actual representation of some inifinite Godelian list of axioms cannot exist within a finite universe. The concept "an infinite list of axioms" can exist in a finite universe without such a list itself existing.
posted by DevilsAdvocate at 7:28 AM on June 23, 2009
Actually, I think you've gone too far to the other side and are selling your argument short now. An infinite list of mathematical statements is not necessarily an infinite amount of information. However, an infinite list of axioms (meaning none of them can be derived from any combination of any of the others) would be an infinite amount of information.
But axioms are big and complex, surely they must be information-rich! Perhaps not.
Well, as far as "big and complex and information-rich," not necessarily, depending on how you define "big" and "complex" and "information-rich," but each additional axiom does add some nonzero amount of information. If a new statement added no new information to the axioms you had previously listed, then it could be derived from your previous axioms, and by definition such a statement is not an axiom.
I agree with you that an actual representation of some inifinite Godelian list of axioms cannot exist within a finite universe. The concept "an infinite list of axioms" can exist in a finite universe without such a list itself existing.
posted by DevilsAdvocate at 7:28 AM on June 23, 2009
Response by poster: The information contained in them is merely how many bits you have to send to let someone else know the axiom.
Which is a lot more than the number of bits you need to send to let someone know what is the next number after 41. Therefore axioms are big and complex compared to integers. I didn't mean that axioms were big in an absolute sense but that they were non-zero.
posted by DU at 7:29 AM on June 23, 2009
Which is a lot more than the number of bits you need to send to let someone know what is the next number after 41. Therefore axioms are big and complex compared to integers. I didn't mean that axioms were big in an absolute sense but that they were non-zero.
posted by DU at 7:29 AM on June 23, 2009
Response by poster: I agree with you that an actual representation of some inifinite Godelian list of axioms cannot exist within a finite universe. The concept "an infinite list of axioms" can exist in a finite universe without such a list itself existing.
1) Can a procedure for generating the infinite list exist within a finite universe?
2) Does such a procedure exist within our universe?
3) Is our universe finite?
posted by DU at 7:31 AM on June 23, 2009
1) Can a procedure for generating the infinite list exist within a finite universe?
2) Does such a procedure exist within our universe?
3) Is our universe finite?
posted by DU at 7:31 AM on June 23, 2009
The universe is already holding all of mathematics.
posted by longsleeves at 7:31 AM on June 23, 2009 [2 favorites]
posted by longsleeves at 7:31 AM on June 23, 2009 [2 favorites]
Open a text file, write down your axioms. Save it, look at the size of the file. You now have an upper bound on the information content of an axiom.
posted by Schismatic at 7:34 AM on June 23, 2009
posted by Schismatic at 7:34 AM on June 23, 2009
Mathematics is like your money in the bank; it's never really all there. Only the little bit that you need at the time.
If ever there were a run on numbers, the universe would disappear.
posted by weapons-grade pandemonium at 7:41 AM on June 23, 2009 [1 favorite]
If ever there were a run on numbers, the universe would disappear.
posted by weapons-grade pandemonium at 7:41 AM on June 23, 2009 [1 favorite]
Answer to 1 and 2 is yes in my opinion. e.g. 1st order arithmetic needs an infinite list of axioms to handle induction* and you can generate the list by the following rule:
1. generate string of symbols in your language
2. check if it's a valid string representing a predicate p (this is a finite process)
3. add the axiom "if p(0) and p(n) => p(n+1) then ForAll n p(n)
* you may well believe that the axiom schema is really a single second order axiom quantifying over predicates P (ie ForAll p the following is an axiom...) but that ForAll there hides the fact that it's a much stronger statement than the 1st order version, which only produces axioms for predicates you can define in the first order language. The second order one quantifies over all predicates, whether definable or not. This is relevant to your original question because it's where all the "implicit" information is hiding that's not captured by the 1st order logic.
posted by crocomancer at 7:52 AM on June 23, 2009
1. generate string of symbols in your language
2. check if it's a valid string representing a predicate p (this is a finite process)
3. add the axiom "if p(0) and p(n) => p(n+1) then ForAll n p(n)
* you may well believe that the axiom schema is really a single second order axiom quantifying over predicates P (ie ForAll p the following is an axiom...) but that ForAll there hides the fact that it's a much stronger statement than the 1st order version, which only produces axioms for predicates you can define in the first order language. The second order one quantifies over all predicates, whether definable or not. This is relevant to your original question because it's where all the "implicit" information is hiding that's not captured by the 1st order logic.
posted by crocomancer at 7:52 AM on June 23, 2009
DU, it seems like your original question is premised on a sort of intuitionism in the mathematical sense. From the Wikipedia article:
To claim an object with certain properties exists is, to an intuitionist, to claim to be able to construct a certain object with those properties. Any mathematical object is considered to be a product of a construction of a mind, and therefore, the existence of an object is equivalent to the possibility of its construction.
Posing the question of whether the universe can "contain" all mathematical concepts seems to rest on the notion that mathematical concepts must first be constructed in order to be considered to exist. If that is your assumption, then no, it certainly seems that you cannot construct an infinite number of theorems in finite time and space.
But as you can see from the thread, not everybody shares this opinion of what it means to say a mathematical statement or property "exists."
posted by letourneau at 7:56 AM on June 23, 2009 [2 favorites]
To claim an object with certain properties exists is, to an intuitionist, to claim to be able to construct a certain object with those properties. Any mathematical object is considered to be a product of a construction of a mind, and therefore, the existence of an object is equivalent to the possibility of its construction.
Posing the question of whether the universe can "contain" all mathematical concepts seems to rest on the notion that mathematical concepts must first be constructed in order to be considered to exist. If that is your assumption, then no, it certainly seems that you cannot construct an infinite number of theorems in finite time and space.
But as you can see from the thread, not everybody shares this opinion of what it means to say a mathematical statement or property "exists."
posted by letourneau at 7:56 AM on June 23, 2009 [2 favorites]
Yet Godel (shouting from inside) says he proved it can produce an infinite number of axioms. Who is right?
I think you are forgetting the time dimension. If this discussion is to have anything to do with physical reality, we need to accept that producing an axiom with the box will take a non-zero amount of time. If that is the case, and time is finite, as you specified in your assumption, then the amount of axioms you can produce is finite.
If your box can produce statements in zero time, or if you have infinite time to work with, then all bets are off.
posted by benign at 7:59 AM on June 23, 2009
I think you are forgetting the time dimension. If this discussion is to have anything to do with physical reality, we need to accept that producing an axiom with the box will take a non-zero amount of time. If that is the case, and time is finite, as you specified in your assumption, then the amount of axioms you can produce is finite.
If your box can produce statements in zero time, or if you have infinite time to work with, then all bets are off.
posted by benign at 7:59 AM on June 23, 2009
Your first assumption is very likely wrong.
The rest of your question reads like OTMBH*.
* One Too Many Bong Hits.
posted by wfrgms at 8:00 AM on June 23, 2009 [5 favorites]
The rest of your question reads like OTMBH*.
* One Too Many Bong Hits.
posted by wfrgms at 8:00 AM on June 23, 2009 [5 favorites]
1) Can a procedure for generating the infinite list exist within a finite universe?
I don't believe so. To do so algorithmically, you'd have to be able to do something like the following: suppose you have axioms a1 through an and you want to generate axiom an+1. Let's say you have a proposed statement X. If you could show that X is undecidable given a1 through an, then you could arbitrarily choose either "X is true" or "X is false" as axiom an+1, and you have added additional information. However, it's important to show that X is undecidable given a1 through an first, because if it's not undecidable, then you either add the correct statement (out of "X is true" or "X is false"), which is not axiomatic and adds no new information, or you add the wrong one, and your set of axioms is inconsistent.
However, my understanding of Godel's incompleteness theorem is that not only does any consistent set of axioms imply the existence of at least one undecidable statement (which, if it could be identified, could be used to generate the next axiom in the infinite series, as outlined above), but it is also impossible to prove that the undecidable statement is in fact undecidable, because the undecidable Godel sentence G is a statement asserting its own undecidability, and proving it undecidable would paradoxically show it to be true.
3) Is our universe finite?
To quote a wise MeFite, I honestly don't know and neither do any of you.
posted by DevilsAdvocate at 8:19 AM on June 23, 2009
I don't believe so. To do so algorithmically, you'd have to be able to do something like the following: suppose you have axioms a1 through an and you want to generate axiom an+1. Let's say you have a proposed statement X. If you could show that X is undecidable given a1 through an, then you could arbitrarily choose either "X is true" or "X is false" as axiom an+1, and you have added additional information. However, it's important to show that X is undecidable given a1 through an first, because if it's not undecidable, then you either add the correct statement (out of "X is true" or "X is false"), which is not axiomatic and adds no new information, or you add the wrong one, and your set of axioms is inconsistent.
However, my understanding of Godel's incompleteness theorem is that not only does any consistent set of axioms imply the existence of at least one undecidable statement (which, if it could be identified, could be used to generate the next axiom in the infinite series, as outlined above), but it is also impossible to prove that the undecidable statement is in fact undecidable, because the undecidable Godel sentence G is a statement asserting its own undecidability, and proving it undecidable would paradoxically show it to be true.
3) Is our universe finite?
To quote a wise MeFite, I honestly don't know and neither do any of you.
posted by DevilsAdvocate at 8:19 AM on June 23, 2009
Mathematics is a product of the human mind, a way of understanding objective reality.
Is this really how mathematicians see their profession? Most of the mathematicians I studied under in school were careful to talk about their work as a series of discoveries, rather than inventions.
posted by Blazecock Pileon at 8:20 AM on June 23, 2009
Is this really how mathematicians see their profession? Most of the mathematicians I studied under in school were careful to talk about their work as a series of discoveries, rather than inventions.
posted by Blazecock Pileon at 8:20 AM on June 23, 2009
Response by poster: However, it's important to show that X is undecidable given a1 through an first, because if it's not undecidable, then you either add the correct statement (out of "X is true" or "X is false"), which is not axiomatic and adds no new information, or you add the wrong one, and your set of axioms is inconsistent.
You don't have to show that X is undecidable. You construct it to be undecidable using the diagonal slash.
posted by DU at 8:29 AM on June 23, 2009
You don't have to show that X is undecidable. You construct it to be undecidable using the diagonal slash.
posted by DU at 8:29 AM on June 23, 2009
...there is some maximum amount of information storable in the universe.
This seems perfectly plausible. To "store" something in the sense you're proposing it has to be encoded somewhere, with a physical medium (electricity, atoms, neurons, carbon and tree pulp, etc). Physical media are finite, bounded by the total mass-energy of the universe. So yup, I'll buy that.
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information.
I'd argue with the word "has" here. Mathematics is a logical system that is capable of producing an infinite amount of information, much like many other systems (like the system: "Start writing down the letter A and never stop"). If you were to take a simple formula, say like the following:
Let n = 0; n = n + 1; Repeat step two.
That formula is capable of producing all positive integers as storable information, if you could let it run forever (you can't) and you had an infinite amount of media to record the results on (you don't). So the formula does not contain all positive integers. It represents them. It is a machine for producing them as needed. Or to change metaphors: it's a map, it's not the territory.
posted by rusty at 8:59 AM on June 23, 2009 [1 favorite]
This seems perfectly plausible. To "store" something in the sense you're proposing it has to be encoded somewhere, with a physical medium (electricity, atoms, neurons, carbon and tree pulp, etc). Physical media are finite, bounded by the total mass-energy of the universe. So yup, I'll buy that.
However, it is easy to prove on a number of fronts that mathematics has an infinite amount of information.
I'd argue with the word "has" here. Mathematics is a logical system that is capable of producing an infinite amount of information, much like many other systems (like the system: "Start writing down the letter A and never stop"). If you were to take a simple formula, say like the following:
Let n = 0; n = n + 1; Repeat step two.
That formula is capable of producing all positive integers as storable information, if you could let it run forever (you can't) and you had an infinite amount of media to record the results on (you don't). So the formula does not contain all positive integers. It represents them. It is a machine for producing them as needed. Or to change metaphors: it's a map, it's not the territory.
posted by rusty at 8:59 AM on June 23, 2009 [1 favorite]
Your question isn't silly at all -- or at least, it's no less silly than any of a number of questions that fairly mainstream physicists are getting paid to think about.
I saw a talk a while ago by Craig Hogan arguing, sort of, for the "holographic principle" -- essentially, that what we perceive as a 3-D universe could be entirely described by a 2-D theory on a boundary, in much the same way that a hologram is a 2-D surface that encodes a seemingly 3-D image. If the holographic principle applies to the universe as a whole, then there shouldn't be more information in it than could possibly be encoded on the 2-D surface. You can plausibly limit the amount of information contained on that surface -- basically by saying, more or less as you did above, that there's a smallest possible length on the boundary (which is roughly the planck scale), and you can't pack information on smaller scales than that. This inherent granularity on the boundary in turn implies some larger apparent uncertainty in the (higher-D) volume, in sort of the same way that holograms always look a little fuzzy.
This is all highly speculative, of course, but the interesting bit was that Hogan was claiming that this "holographic uncertainty bound" might actually have been seen already. The GEO 600 gravitational wave detector hasn't seen any gravitational waves, but it has seen a bunch of noise -- more noise than they'd expected. Hogan is arguing that this holographic uncertainty business might actually explain that noise -- i.e. that this holographic uncertainty principle implies an inherent noisiness roughly comparable to what they're seeing. One nice thing about this is that it's at least in principle falsifiable -- i.e., if the GEO 600 team somehow gets their noise down by another order of magnitude, my impression was that this would pose serious problems for the holographic interpretation.
I am mangling some of this stuff -- partly because it is hard to describe, and partly because I don't know all that much about it. But hopefully you get the sense that thinking about the maximal information/entropy content of a finite volume is not a terribly silly thing to do.
(As for your specific question: as others have pointed out, I suspect the resolution is that your notion of information bears little resemblance to the Shannon information/entropy. A statement like "Force = mass x acceleration" contains a whole lot more information in the colloquial sense than many nonsense statements with the same Shannon information.)
posted by chalkbored at 9:28 AM on June 23, 2009
I saw a talk a while ago by Craig Hogan arguing, sort of, for the "holographic principle" -- essentially, that what we perceive as a 3-D universe could be entirely described by a 2-D theory on a boundary, in much the same way that a hologram is a 2-D surface that encodes a seemingly 3-D image. If the holographic principle applies to the universe as a whole, then there shouldn't be more information in it than could possibly be encoded on the 2-D surface. You can plausibly limit the amount of information contained on that surface -- basically by saying, more or less as you did above, that there's a smallest possible length on the boundary (which is roughly the planck scale), and you can't pack information on smaller scales than that. This inherent granularity on the boundary in turn implies some larger apparent uncertainty in the (higher-D) volume, in sort of the same way that holograms always look a little fuzzy.
This is all highly speculative, of course, but the interesting bit was that Hogan was claiming that this "holographic uncertainty bound" might actually have been seen already. The GEO 600 gravitational wave detector hasn't seen any gravitational waves, but it has seen a bunch of noise -- more noise than they'd expected. Hogan is arguing that this holographic uncertainty business might actually explain that noise -- i.e. that this holographic uncertainty principle implies an inherent noisiness roughly comparable to what they're seeing. One nice thing about this is that it's at least in principle falsifiable -- i.e., if the GEO 600 team somehow gets their noise down by another order of magnitude, my impression was that this would pose serious problems for the holographic interpretation.
I am mangling some of this stuff -- partly because it is hard to describe, and partly because I don't know all that much about it. But hopefully you get the sense that thinking about the maximal information/entropy content of a finite volume is not a terribly silly thing to do.
(As for your specific question: as others have pointed out, I suspect the resolution is that your notion of information bears little resemblance to the Shannon information/entropy. A statement like "Force = mass x acceleration" contains a whole lot more information in the colloquial sense than many nonsense statements with the same Shannon information.)
posted by chalkbored at 9:28 AM on June 23, 2009
Mathematics is a product of the human mind, a way of understanding objective reality.
Is this really how mathematicians see their profession?
Perhaps not, but there's some interesting work on the subject by George Lakoff and Rafael Núñez that makes a good case for that claim.
posted by velvet winter at 9:29 AM on June 23, 2009 [1 favorite]
Is this really how mathematicians see their profession?
Perhaps not, but there's some interesting work on the subject by George Lakoff and Rafael Núñez that makes a good case for that claim.
posted by velvet winter at 9:29 AM on June 23, 2009 [1 favorite]
At some point, the universe will be completely packed with information. I crank the handle one more time. And....?
And in cranking the handle and transcribing the result, your muscles burn highly-organized molecules of adenosine triphosphate, trading the information stored there for an axiom encoded in your Planck-scale notation + heat and simpler waste molecules. And since at this point the only thing left to eat is your stack of axioms, there will always be room for more.
posted by nicwolff at 9:45 AM on June 23, 2009
And in cranking the handle and transcribing the result, your muscles burn highly-organized molecules of adenosine triphosphate, trading the information stored there for an axiom encoded in your Planck-scale notation + heat and simpler waste molecules. And since at this point the only thing left to eat is your stack of axioms, there will always be room for more.
posted by nicwolff at 9:45 AM on June 23, 2009
Concepts don't take up space. There may be infinite real numbers, but we conveniently "store" them within the concept of "infinity", which, conveniently, also takes no space to store. I think you're confusing data with concepts. Data must be stored, or it will be lost, and there is a finite amount of data that can be stored in the universe, I suppose. The fundamentals of mathematics, or the concepts we use to understand the world, or concepts in general - do not take up storage space because they are not locatable entities and have no independent existence without human beings to use them. It IS true that the universe exists according to some concepts (laws, theories) that we have discovered - but the universe would continue to exist exactly the same way even if no human being had ever discovered those things.
posted by Cygnet at 10:11 AM on June 23, 2009
posted by Cygnet at 10:11 AM on June 23, 2009
Seconding aught's recommendation above to check out Tegmark. I'll add that you'd probably be interested in his paper "DOES THE UNIVERSE IN FACT CONTAIN ALMOST NO INFORMATION?"
At first sight, an accurate description of the state of the universe appears to require a mind-bogglingly large and perhaps even infinite amount of information, even if we restrict our attention to a small subsystem such as a rabbit. In this paper, it is suggested that most of this information is merely apparent, as seen from our subjective viewpoints, and that the algorithmic information content of the universe as a whole is close to zero. It is argued that if the Schrödinger equation is universally valid, then decoherence together with the standard chaotic behavior of certain non-linear systems will make the universe appear extremely complex to any self-aware subsets that happen to inhabit it now, even if it was in a quite simple state shortly after the big bang. For instance, gravitational instability would amplify the microscopic primordial density fluctuations that are required by the Heisenberg uncertainty principle into quite macroscopic inhomogeneities, forcing the current wavefunction of the universe to contain such Byzantine superpositions as our planet being in many macroscopically different places at once. Since decoherence bars us from experiencing more than one macroscopic reality, we would see seemingly complex constellations of stars etc, even if the initial wavefunction of the universe was perfectly homogeneous and isotropic.
posted by zippy at 10:12 AM on June 23, 2009 [1 favorite]
At first sight, an accurate description of the state of the universe appears to require a mind-bogglingly large and perhaps even infinite amount of information, even if we restrict our attention to a small subsystem such as a rabbit. In this paper, it is suggested that most of this information is merely apparent, as seen from our subjective viewpoints, and that the algorithmic information content of the universe as a whole is close to zero. It is argued that if the Schrödinger equation is universally valid, then decoherence together with the standard chaotic behavior of certain non-linear systems will make the universe appear extremely complex to any self-aware subsets that happen to inhabit it now, even if it was in a quite simple state shortly after the big bang. For instance, gravitational instability would amplify the microscopic primordial density fluctuations that are required by the Heisenberg uncertainty principle into quite macroscopic inhomogeneities, forcing the current wavefunction of the universe to contain such Byzantine superpositions as our planet being in many macroscopically different places at once. Since decoherence bars us from experiencing more than one macroscopic reality, we would see seemingly complex constellations of stars etc, even if the initial wavefunction of the universe was perfectly homogeneous and isotropic.
posted by zippy at 10:12 AM on June 23, 2009 [1 favorite]
er, there is a finite amount of data that can be stored *assuming a finite universe*, I mean.
posted by Cygnet at 10:12 AM on June 23, 2009
posted by Cygnet at 10:12 AM on June 23, 2009
You construct it to be undecidable using the diagonal slash.
I'm not sure I follow—could you elaborate?
Admittedly, my previous analysis has a flaw, in that it only considers the undecidable Godelian statement G which asserts its own undecidability. It may be that there are other undecidable statements which can non-paradoxically be proved to be undecidable within a given axiom system (by "proved" here I mean to include both those first conceived and then shown to be undecidable, and those constructed in such a way that they are necessarily undecidable, if such a thing is possible).
If it's possible to algorithmically generate a provably undecidable statement for any given set of axioms (or even more weakly, for axioms a1 through an as described above), then we would seem to have a paradox: the information is both finite (because it can be encoded in a finite algorithm) and infinite (because each undecidable statement in turn can be converted to an axiom, which adds more information).
posted by DevilsAdvocate at 10:14 AM on June 23, 2009
I'm not sure I follow—could you elaborate?
Admittedly, my previous analysis has a flaw, in that it only considers the undecidable Godelian statement G which asserts its own undecidability. It may be that there are other undecidable statements which can non-paradoxically be proved to be undecidable within a given axiom system (by "proved" here I mean to include both those first conceived and then shown to be undecidable, and those constructed in such a way that they are necessarily undecidable, if such a thing is possible).
If it's possible to algorithmically generate a provably undecidable statement for any given set of axioms (or even more weakly, for axioms a1 through an as described above), then we would seem to have a paradox: the information is both finite (because it can be encoded in a finite algorithm) and infinite (because each undecidable statement in turn can be converted to an axiom, which adds more information).
posted by DevilsAdvocate at 10:14 AM on June 23, 2009
Response by poster: If it's possible to algorithmically generate a provably undecidable statement for any given set of axioms...
I thought that's exactly what Godel did. It's certainly what Turing did. You assign/encode all the axioms (or reals or Turing machines) as a number. Line them up, Cantor slash them and you are left with something not on the list. Add it and repeat.
posted by DU at 10:21 AM on June 23, 2009
I thought that's exactly what Godel did. It's certainly what Turing did. You assign/encode all the axioms (or reals or Turing machines) as a number. Line them up, Cantor slash them and you are left with something not on the list. Add it and repeat.
posted by DU at 10:21 AM on June 23, 2009
DU: Maybe I'm not correctly understanding the diagonalization step of Godel's incompleteness theorem, but I thought the diagonalization had to be applied not merely to all axioms, but to all provable statements. Since the set of all provable statements is infinite, actually constructing the Cantor slash requires an infinite number of steps. The diagonalization shows that a statement of the sort Godel wants exists; it does not show how to construct such a statement in finite time, which is key to this discussion.
vernondalhart: I am not disputing whether undecidable propositions exist. I am questioning whether it is possible to algorithmically (in a finite time) generate an undecidable proposition under a set of axioms, given that set of axioms.
posted by DevilsAdvocate at 11:49 AM on June 23, 2009
vernondalhart: I am not disputing whether undecidable propositions exist. I am questioning whether it is possible to algorithmically (in a finite time) generate an undecidable proposition under a set of axioms, given that set of axioms.
posted by DevilsAdvocate at 11:49 AM on June 23, 2009
Response by poster: It is certainly possible that I have the details of Godel hopelessly confused. However, Godel in particular is not really necessary to my question. It can be stated more generally, although therefore less concretely, thus:
a) The universe seems to be able to contain a finite amount of information.
b) Mathematics, which is generally assumed to exist within the universe, seems to be capable of generating an infinite amount of information.
c) Things that can generate an infinite amount of information ARE an infinite amount of information.
Conclusion: What's going on?
The rest of your question reads like OTMBH*.
* One Too Many Bong Hits.
Check the tags.
posted by DU at 12:19 PM on June 23, 2009
a) The universe seems to be able to contain a finite amount of information.
b) Mathematics, which is generally assumed to exist within the universe, seems to be capable of generating an infinite amount of information.
c) Things that can generate an infinite amount of information ARE an infinite amount of information.
Conclusion: What's going on?
The rest of your question reads like OTMBH*.
* One Too Many Bong Hits.
Check the tags.
posted by DU at 12:19 PM on June 23, 2009
Things that can generate an infinite amount of information ARE an infinite amount of information.
I'm not sure I follow your last point. These things are just symbols for representing an abstract idea, not the idea's actual implementation ("generation").
We cannot store a countably infinite set of natural numbers in our head, but this does not stop us from conceptualizing that set as the inductive construction {1, (1+1), (1+(1+1)), ... }, giving it the label ℕ, and using it to solve problems.
We could have a grammar that generates an uncountably infinite language through an infinite number of words, or no upper bound on the length of a sentence. But the grammar itself can be a finite set of rules for generating that infinite language.
posted by Blazecock Pileon at 12:38 PM on June 23, 2009
I'm not sure I follow your last point. These things are just symbols for representing an abstract idea, not the idea's actual implementation ("generation").
We cannot store a countably infinite set of natural numbers in our head, but this does not stop us from conceptualizing that set as the inductive construction {1, (1+1), (1+(1+1)), ... }, giving it the label ℕ, and using it to solve problems.
We could have a grammar that generates an uncountably infinite language through an infinite number of words, or no upper bound on the length of a sentence. But the grammar itself can be a finite set of rules for generating that infinite language.
posted by Blazecock Pileon at 12:38 PM on June 23, 2009
I had an answer deleted before, I think unfairly, so I'll repost it with an explanation, because I think it was perfectly on topic:
Voila! I have just represented an infinite amount of information
my response: "ceci, n'est pas une infinite amount of information"
extended explanation: that was obviously a reference to Magritte's famous painting of a pipe. The caption on the painting means "this is not a pipe". It highlights the fact that a representation of something is not the thing itself.
Now, mathematics is all about representing "information" in abstracted form. In the example I was responding to, it was a finite way of abstractly encoding an infinite series. We do this kind of thing precisely so that we don't have to deal with the infinite series itself, because that would be impossible. This is exactly what abstraction is all about; not only in mathematics, but in any logical discipline, and in fact, in all of our manipulation of language & ideas, because we are almost always using universal types to represent particular tokens.
Recursively, the statement "ceci, n'est pas une infinite amount of information" was deliberately, and in & of itself, a self-referential example of that very same process. For anybody who got the reference (which is a central meme in the cultural currency of the modern West), the jump between the encoded "information" (the phrase) and the extended meaning (the blurb above) should have been reasonably clear; and, in fact, could potentially have given rise to many, many more sophomoric words than the hundred or two that I wrote just above.
Which brings me to this: "seems to be capable of generating an infinite amount of information" does not mean that it actually does generate an infinite amount of information, unless people put their minds to it. Potentiality is not the same as actuality, and the amount of information represented (not generated) will only be equal to the amount that particular, finite people represent - mathematics is not some kind of self-replicating, living entity constantly spewing forwards new formulae & information autonomously & independent of human thought.
And even if some obscure mathematician is creating new representations of information in a dusty garret somewhere, if nobody ever reads or understands his scrawlings, well, that's probably a situation of a tree falling in the forest with nobody around, isn't it?
that last bit was inserted specifically to cater for those bong hits
Personally, I preferred the original answer - it had an understated, recursive elegance.
posted by UbuRoivas at 12:41 PM on June 23, 2009 [2 favorites]
Voila! I have just represented an infinite amount of information
my response: "ceci, n'est pas une infinite amount of information"
extended explanation: that was obviously a reference to Magritte's famous painting of a pipe. The caption on the painting means "this is not a pipe". It highlights the fact that a representation of something is not the thing itself.
Now, mathematics is all about representing "information" in abstracted form. In the example I was responding to, it was a finite way of abstractly encoding an infinite series. We do this kind of thing precisely so that we don't have to deal with the infinite series itself, because that would be impossible. This is exactly what abstraction is all about; not only in mathematics, but in any logical discipline, and in fact, in all of our manipulation of language & ideas, because we are almost always using universal types to represent particular tokens.
Recursively, the statement "ceci, n'est pas une infinite amount of information" was deliberately, and in & of itself, a self-referential example of that very same process. For anybody who got the reference (which is a central meme in the cultural currency of the modern West), the jump between the encoded "information" (the phrase) and the extended meaning (the blurb above) should have been reasonably clear; and, in fact, could potentially have given rise to many, many more sophomoric words than the hundred or two that I wrote just above.
Which brings me to this: "seems to be capable of generating an infinite amount of information" does not mean that it actually does generate an infinite amount of information, unless people put their minds to it. Potentiality is not the same as actuality, and the amount of information represented (not generated) will only be equal to the amount that particular, finite people represent - mathematics is not some kind of self-replicating, living entity constantly spewing forwards new formulae & information autonomously & independent of human thought.
And even if some obscure mathematician is creating new representations of information in a dusty garret somewhere, if nobody ever reads or understands his scrawlings, well, that's probably a situation of a tree falling in the forest with nobody around, isn't it?
that last bit was inserted specifically to cater for those bong hits
Personally, I preferred the original answer - it had an understated, recursive elegance.
posted by UbuRoivas at 12:41 PM on June 23, 2009 [2 favorites]
a) The universe seems to be able to contain a finite amount of information.
b) Mathematics, which is generally assumed to exist within the universe, seems to be capable of generating an infinite amount of information.
c) Things that can generate an infinite amount of information ARE an infinite amount of information.
If by "mathematics" you mean something roughly like "standard mathematics," I don't agree with (b).
I think you've kind of got (c) backwards, in a way. Well, actually (c) is correct, but only if you carefully interpret "information" in the Shannon information theory way. It's not true if you mean "information" in a colloquial sort of "list of facts" kind of way, and if you want to think of "information" in that way, it's probably better to think of the reverse of (c): Things that can be generated from a finite amount of information are a finite amount of information. The digits of pi, though themselves infinite, constitute only a finite amount of information because a computer program of finite length can be written to calculate them. Standard mathematics proceeds from a finite set of axioms and a finite set of rules, so all of standard mathematics is a finite amount of information (in the Shannon sense).
Suppose you have a list of the axioms and rules of mathematics, and maybe also some of the statements which are derivable from these. Now, you derive an additional statement from these which is not already on the list (let's say, "24*5=120"), and add it to the list. Although this new statement might be additional "information" in a colloquial sense, it is not new information in a formalized, Shannon sense. Since it is derivable from the axioms and rules of standard mathematics, it was already implicitly encoded within those axioms and rules, but that (along with an infinite number of derivable statements) is only a finite amount of information in the formalized sense (even though it may seem to be an infinite amount of information in a common-language sense).
Godel got brought in because you correctly noted that some statements are undecidable under the axioms and rules of standard mathematics. Let's call the axioms and rules (and by implication, all statements derivable from them) of standard mathematics M. Let's also say that G1 is a statement which is undecidable under M. Now let's consider a system which has all the axioms and rules of M, but which also accepts G1 as an axiom: M+G1. Because G1 could not be derived from M alone, M+G1 does have more information than M alone. However, M+G1 is not "standard mathematics." Thus my objection to your statement (b).
posted by DevilsAdvocate at 1:39 PM on June 23, 2009
b) Mathematics, which is generally assumed to exist within the universe, seems to be capable of generating an infinite amount of information.
c) Things that can generate an infinite amount of information ARE an infinite amount of information.
If by "mathematics" you mean something roughly like "standard mathematics," I don't agree with (b).
I think you've kind of got (c) backwards, in a way. Well, actually (c) is correct, but only if you carefully interpret "information" in the Shannon information theory way. It's not true if you mean "information" in a colloquial sort of "list of facts" kind of way, and if you want to think of "information" in that way, it's probably better to think of the reverse of (c): Things that can be generated from a finite amount of information are a finite amount of information. The digits of pi, though themselves infinite, constitute only a finite amount of information because a computer program of finite length can be written to calculate them. Standard mathematics proceeds from a finite set of axioms and a finite set of rules, so all of standard mathematics is a finite amount of information (in the Shannon sense).
Suppose you have a list of the axioms and rules of mathematics, and maybe also some of the statements which are derivable from these. Now, you derive an additional statement from these which is not already on the list (let's say, "24*5=120"), and add it to the list. Although this new statement might be additional "information" in a colloquial sense, it is not new information in a formalized, Shannon sense. Since it is derivable from the axioms and rules of standard mathematics, it was already implicitly encoded within those axioms and rules, but that (along with an infinite number of derivable statements) is only a finite amount of information in the formalized sense (even though it may seem to be an infinite amount of information in a common-language sense).
Godel got brought in because you correctly noted that some statements are undecidable under the axioms and rules of standard mathematics. Let's call the axioms and rules (and by implication, all statements derivable from them) of standard mathematics M. Let's also say that G1 is a statement which is undecidable under M. Now let's consider a system which has all the axioms and rules of M, but which also accepts G1 as an axiom: M+G1. Because G1 could not be derived from M alone, M+G1 does have more information than M alone. However, M+G1 is not "standard mathematics." Thus my objection to your statement (b).
posted by DevilsAdvocate at 1:39 PM on June 23, 2009
I had an answer deleted before, I think unfairly, so I'll repost it with an explanation, because I think it was perfectly on topic:
Voila! I have just represented an infinite amount of information
my response: "ceci, n'est pas une infinite amount of information"
I had seen your response, and thought it was on topic (and yes, I recognized the allusion). I was surprised and disappointed to see it deleted. I had also posted a response to it, in turn, which was deleted along with it.
I don't recall the exact wording of my response, but its meaning (perhaps less snarkily than I put it the first time) was that my earlier statement (let's see it in full here, and perhaps get a better idea of the context): "Voila! I have just represented an infinite amount of information (for one sense of "information"), not just within the universe, but within a handful of bytes!"
My scare quotes around the second "information," absurd "Voila!" and excessive exclamation points were intended to convey irony: I was not actually arguing that "a·∞" was an infinite amount of information. I had hoped the rest of my response below that had made that clear, but my apologies if it did not.
However (upon seeing your lengthier response, so this bit was not in my earlier deleted response), I do not think the distinction between the representation and the actuality that you are attempting to make with your Magritte reference is correct here: I think that an actual string consisting of an infinite number of repetitions of the letter a also conveys only a finite amount of information. I agree with you that "a·∞" carries only a finite amount of information; I disagree with you that there is a difference between the information carried between the potentiality and the information which would be carried by the actuality, should someone manage to construct it.
posted by DevilsAdvocate at 1:52 PM on June 23, 2009
Voila! I have just represented an infinite amount of information
my response: "ceci, n'est pas une infinite amount of information"
I had seen your response, and thought it was on topic (and yes, I recognized the allusion). I was surprised and disappointed to see it deleted. I had also posted a response to it, in turn, which was deleted along with it.
I don't recall the exact wording of my response, but its meaning (perhaps less snarkily than I put it the first time) was that my earlier statement (let's see it in full here, and perhaps get a better idea of the context): "Voila! I have just represented an infinite amount of information (for one sense of "information"), not just within the universe, but within a handful of bytes!"
My scare quotes around the second "information," absurd "Voila!" and excessive exclamation points were intended to convey irony: I was not actually arguing that "a·∞" was an infinite amount of information. I had hoped the rest of my response below that had made that clear, but my apologies if it did not.
However (upon seeing your lengthier response, so this bit was not in my earlier deleted response), I do not think the distinction between the representation and the actuality that you are attempting to make with your Magritte reference is correct here: I think that an actual string consisting of an infinite number of repetitions of the letter a also conveys only a finite amount of information. I agree with you that "a·∞" carries only a finite amount of information; I disagree with you that there is a difference between the information carried between the potentiality and the information which would be carried by the actuality, should someone manage to construct it.
posted by DevilsAdvocate at 1:52 PM on June 23, 2009
I don't recall the exact wording of my response, but its meaning... was that my earlier statement...
Sorry, I never completed that sentence and just left it hanging. It should end "...was intended ironically."
posted by DevilsAdvocate at 1:55 PM on June 23, 2009
Sorry, I never completed that sentence and just left it hanging. It should end "...was intended ironically."
posted by DevilsAdvocate at 1:55 PM on June 23, 2009
DevilsAdvocate: Yes, I recognised that the "Voila!" statement was meant ironically; it also conveniently & satirically paraphrased (for me, at least) the premise behind the entire question - ie that because mathematics can express infinitely things, that it is also itself infinitely large.
posted by UbuRoivas at 3:09 PM on June 23, 2009
posted by UbuRoivas at 3:09 PM on June 23, 2009
This reminds me a bit of Anselm's ontological argument for the existence of God.
The flaw in that is that existence is not a predicate.
So maybe the flaw here is that a predicate does not possess existence.
posted by TheophileEscargot at 3:25 PM on June 23, 2009
The flaw in that is that existence is not a predicate.
So maybe the flaw here is that a predicate does not possess existence.
posted by TheophileEscargot at 3:25 PM on June 23, 2009
Response by poster: We cannot store a countably infinite set of natural numbers in our head, but this does not stop us from conceptualizing that set as the inductive construction {1, (1+1), (1+(1+1)), ... }, giving it the label ℕ, and using it to solve problems.
An infinite series does not necessarily contain an infinite amount of information. That's why I've avoided using "the integers" or "the reals" has my example of infinite information, preferring instead to use axioms.
"seems to be capable of generating an infinite amount of information" does not mean that it actually does generate an infinite amount of information
No, but I think it's clear this entire discussion could be translated into the language of limits: The universe has a finite upper bound on information content (is the assumption). Godel proved that no matter how long your finite list of axioms is, you can always add another. Therefore, for any upper bound you choose, you can always grow the information content of the list of axioms to be greater than that bound. In particular, you can grow it beyond the bound of the universe.
Whether this is a contradiction or a revelation depends on the reader...
Now let's consider a system which has all the axioms and rules of M, but which also accepts G1 as an axiom: M+G1. Because G1 could not be derived from M alone, M+G1 does have more information than M alone. However, M+G1 is not "standard mathematics."
So? I'm not the one who added the word "standard" in the first place. And even if I had, the fact remains that you have a system, standard mathematical or otherwise, for creating a pile of information greater than any given upper bound.
posted by DU at 5:05 PM on June 23, 2009
An infinite series does not necessarily contain an infinite amount of information. That's why I've avoided using "the integers" or "the reals" has my example of infinite information, preferring instead to use axioms.
"seems to be capable of generating an infinite amount of information" does not mean that it actually does generate an infinite amount of information
No, but I think it's clear this entire discussion could be translated into the language of limits: The universe has a finite upper bound on information content (is the assumption). Godel proved that no matter how long your finite list of axioms is, you can always add another. Therefore, for any upper bound you choose, you can always grow the information content of the list of axioms to be greater than that bound. In particular, you can grow it beyond the bound of the universe.
Whether this is a contradiction or a revelation depends on the reader...
Now let's consider a system which has all the axioms and rules of M, but which also accepts G1 as an axiom: M+G1. Because G1 could not be derived from M alone, M+G1 does have more information than M alone. However, M+G1 is not "standard mathematics."
So? I'm not the one who added the word "standard" in the first place. And even if I had, the fact remains that you have a system, standard mathematical or otherwise, for creating a pile of information greater than any given upper bound.
posted by DU at 5:05 PM on June 23, 2009
And even if I had, the fact remains that you have a system, standard mathematical or otherwise, for creating a pile of information greater than any given upper bound.
You have a means of showing that G1, G2, G3, etc., exist. I still do not see that you have "a system... for creating" G1, G2, G3, etc., within a finite space and time, nor even in infinite time with an algorithm of finite length.
posted by DevilsAdvocate at 5:21 PM on June 23, 2009
You have a means of showing that G1, G2, G3, etc., exist. I still do not see that you have "a system... for creating" G1, G2, G3, etc., within a finite space and time, nor even in infinite time with an algorithm of finite length.
posted by DevilsAdvocate at 5:21 PM on June 23, 2009
Response by poster: You have a means of showing that G1, G2, G3, etc., exist. I still do not see that you have "a system... for creating" G1, G2, G3, etc., within a finite space and time
Godel's proof depended on creating G, because he had to have it say something specific ("G cannot be proved in formal system S"). But perhaps G2, which says "G2 cannot be proved in formal system S+G" is "the same as" G in some way and doesn't count as new information. I'd say this is a pretty thin hook on which to hang a defense of the informational integrity of the universe. And in any case, it doesn't seem like an insurmountable barrier.
posted by DU at 5:31 PM on June 23, 2009
Godel's proof depended on creating G, because he had to have it say something specific ("G cannot be proved in formal system S"). But perhaps G2, which says "G2 cannot be proved in formal system S+G" is "the same as" G in some way and doesn't count as new information. I'd say this is a pretty thin hook on which to hang a defense of the informational integrity of the universe. And in any case, it doesn't seem like an insurmountable barrier.
posted by DU at 5:31 PM on June 23, 2009
Godel's proof depended on creating G, because he had to have it say something specific
It's not enough to create G alone, for S+G also constitutes a finite amount of information. You have to be able to create G, G2, G3, G4... ad infinitum. Constructing any finite subset of this G series results only in S+G+G2+G3+...+Gn, which is only a finite amount of information. You need to be able to actually construct (not merely show the existence of) the entire infinite series (not just one or a finite subset of). Per the previous discussion, a finite (in length but not runtime) algorithm which could construct the entire infinite series would be equivalent, in informational content, to the series itself. At the moment, I do not believe such an algorithm exists. Although I can't prove it beyond noting that it would lead to what appears to me to be a contradiction, that S plus the infinite G series would simultaneously contain a finite and an infinite amount of information, but perhaps there's some way out of that paradox that I don't see.
But perhaps G2, which says "G2 cannot be proved in formal system S+G" is "the same as" G in some way and doesn't count as new information.
No, I'm on your side on that part of it: I agree that G2 is distinct from G, and that S+G+G2 contains more information than S+G.
posted by DevilsAdvocate at 5:49 PM on June 23, 2009
It's not enough to create G alone, for S+G also constitutes a finite amount of information. You have to be able to create G, G2, G3, G4... ad infinitum. Constructing any finite subset of this G series results only in S+G+G2+G3+...+Gn, which is only a finite amount of information. You need to be able to actually construct (not merely show the existence of) the entire infinite series (not just one or a finite subset of). Per the previous discussion, a finite (in length but not runtime) algorithm which could construct the entire infinite series would be equivalent, in informational content, to the series itself. At the moment, I do not believe such an algorithm exists. Although I can't prove it beyond noting that it would lead to what appears to me to be a contradiction, that S plus the infinite G series would simultaneously contain a finite and an infinite amount of information, but perhaps there's some way out of that paradox that I don't see.
But perhaps G2, which says "G2 cannot be proved in formal system S+G" is "the same as" G in some way and doesn't count as new information.
No, I'm on your side on that part of it: I agree that G2 is distinct from G, and that S+G+G2 contains more information than S+G.
posted by DevilsAdvocate at 5:49 PM on June 23, 2009
Response by poster: You need to be able to actually construct (not merely show the existence of) the entire infinite series (not just one or a finite subset of).
No, as stated previously, I just need to actually construct enough to fill the universe.
posted by DU at 5:53 PM on June 23, 2009
No, as stated previously, I just need to actually construct enough to fill the universe.
posted by DU at 5:53 PM on June 23, 2009
No, as stated previously, I just need to actually construct enough to fill the universe.
Agreed (if I'm understanding your meaning correctly). If, let's say, the information in S+G+G2+...Ggoogol equals the maximum theoretical information content of the finite universe, than constructing (again, not merely proving the existence of) G through G(googol+1) shows that information theory as we know it fails.
How do you propose to construct G2...G(googol+1)?
If there's a universal finite algorithm that, given S+G...Gn, can construct Gn+1, then you've got what you're looking for, but the distinction between "infinite" and "finite but larger than the universe" becomes unnecessary, as that algorithm could produce the entire infinite series anyway, even if you don't need it to go that far.
OTOH, if you need one algorithm for G2, and a totally different one for G3, and a still totally different one for G4, and so on for each G you're looking for, I dispute that the entire series of algorithms necessary, though admittedly finite, could themselves exist within the finite universe. (By "totally different" I mean roughly "not generalizable in any significant way.")
posted by DevilsAdvocate at 6:15 PM on June 23, 2009
Agreed (if I'm understanding your meaning correctly). If, let's say, the information in S+G+G2+...Ggoogol equals the maximum theoretical information content of the finite universe, than constructing (again, not merely proving the existence of) G through G(googol+1) shows that information theory as we know it fails.
How do you propose to construct G2...G(googol+1)?
If there's a universal finite algorithm that, given S+G...Gn, can construct Gn+1, then you've got what you're looking for, but the distinction between "infinite" and "finite but larger than the universe" becomes unnecessary, as that algorithm could produce the entire infinite series anyway, even if you don't need it to go that far.
OTOH, if you need one algorithm for G2, and a totally different one for G3, and a still totally different one for G4, and so on for each G you're looking for, I dispute that the entire series of algorithms necessary, though admittedly finite, could themselves exist within the finite universe. (By "totally different" I mean roughly "not generalizable in any significant way.")
posted by DevilsAdvocate at 6:15 PM on June 23, 2009
Response by poster: I dispute that the entire series of algorithms necessary, though admittedly finite, could themselves exist within the finite universe.
But then haven't you proved my point? You've shown that something exists (FSVO "exists") but cannot be held within the universe.
posted by DU at 6:21 PM on June 23, 2009
But then haven't you proved my point? You've shown that something exists (FSVO "exists") but cannot be held within the universe.
posted by DU at 6:21 PM on June 23, 2009
Therefore, for any upper bound you choose, you can always grow the information content of the list of axioms to be greater than that bound. In particular, you can grow it beyond the bound of the universe.
Sure, but where do you propose to find this army of monkeys to first, reach the upper bound with their enormous list of axioms, and then second, cross it by adding more?
posted by UbuRoivas at 6:31 PM on June 23, 2009
Sure, but where do you propose to find this army of monkeys to first, reach the upper bound with their enormous list of axioms, and then second, cross it by adding more?
posted by UbuRoivas at 6:31 PM on June 23, 2009
Response by poster: MetaFilter: an army of monkeys to reach the upper bound with their enormous list of axioms...and then cross it by adding more!
posted by DU at 6:35 PM on June 23, 2009
posted by DU at 6:35 PM on June 23, 2009
But then haven't you proved my point? You've shown that something exists (FSVO "exists") but cannot be held within the universe.
Not for any meaningful value of "exists." Until it's actually constructed, it exists only in the same sense that Borges' infinite library exists. Just because you can generally describe some of the properties of an infinite library or a finite-but-too-large-for-the-universe set of algorithms does not mean that either exists beyond a necessarily incomplete conception in the human imagination.
posted by DevilsAdvocate at 8:34 PM on June 23, 2009
Not for any meaningful value of "exists." Until it's actually constructed, it exists only in the same sense that Borges' infinite library exists. Just because you can generally describe some of the properties of an infinite library or a finite-but-too-large-for-the-universe set of algorithms does not mean that either exists beyond a necessarily incomplete conception in the human imagination.
posted by DevilsAdvocate at 8:34 PM on June 23, 2009
Coming in to this thread a bit late, so apologies if I've completely missed the point or previous posts saying the same thing.
Surely all of the "information" that would be contained in the infinite list of all mathematical axioms is originally "stored" in the fundamental structure and workings of the universe? All the seeming extra information in axioms is really just explaining the same rules that govern any part of the universe in a way more easily understandable to humans.
For example, if you had a universe the size of a small room, but with the same physical laws as our universe, you could still sit in there and work out all of the same things from first principles.
In other words, you don't need an infinite amount of universe to store this infinite amount of information, because any arbitrarily tiny "piece" of the universe also stores the exact same information within its form and properties.
posted by lucidium at 3:49 AM on June 24, 2009
Surely all of the "information" that would be contained in the infinite list of all mathematical axioms is originally "stored" in the fundamental structure and workings of the universe? All the seeming extra information in axioms is really just explaining the same rules that govern any part of the universe in a way more easily understandable to humans.
For example, if you had a universe the size of a small room, but with the same physical laws as our universe, you could still sit in there and work out all of the same things from first principles.
In other words, you don't need an infinite amount of universe to store this infinite amount of information, because any arbitrarily tiny "piece" of the universe also stores the exact same information within its form and properties.
posted by lucidium at 3:49 AM on June 24, 2009
Response by poster: Let's come at this from the other direction. First of all, if a sequence is generated by an algorithm, the sequence cannot have any more information content than the algorithm. (Because say the sequence must use A bits and the algorithm only uses B (<>
Second, we are still under the assumption that the universe has a finite information content.
Third, we can consider the entire universe to be in some sense "one big algorithm".
10 BANG(BIGLY)
20 EXPAND(FABRIC_OF(SPACETIME))
30 FORM(STARS)
...
10000000 GIVE_BIRTH_TO(GODEL)
etc
The output of this big algorithm must have a finite information content (less than or equal to that of the universe).
However, Godel's claim is that the Big Algorithm can generate unlimited mathematical axioms. So either he is wrong (i.e. the universe is non-godelian and there is something that prevents further axioms from being created even in his non-physical toy system) or our assumption of the finite information content of the universe is wrong.
posted by DU at 4:43 AM on June 24, 2009
Second, we are still under the assumption that the universe has a finite information content.
Third, we can consider the entire universe to be in some sense "one big algorithm".
10 BANG(BIGLY)
20 EXPAND(FABRIC_OF(SPACETIME))
30 FORM(STARS)
...
10000000 GIVE_BIRTH_TO(GODEL)
etc
The output of this big algorithm must have a finite information content (less than or equal to that of the universe).
However, Godel's claim is that the Big Algorithm can generate unlimited mathematical axioms. So either he is wrong (i.e. the universe is non-godelian and there is something that prevents further axioms from being created even in his non-physical toy system) or our assumption of the finite information content of the universe is wrong.
posted by DU at 4:43 AM on June 24, 2009
Until it's actually constructed, it exists only in the same sense that Borges' infinite library exists.
Here's a better analogy: G2, G3, ... G(googol), G(googol+1) exist in the same way that "a prime larger than the largest known prime" exists. I.e., there is a mathematical proof of their "existence," in a platonic mathematical sense. However, this sort of existence is not the sort of existence for which information theory requires that that information is represented within the information capacity of the universe.
----------
For example, if you had a universe the size of a small room, but with the same physical laws as our universe, you could still sit in there and work out all of the same things from first principles.
No, I don't believe you could. Computer-assisted proofs are becoming more and more common in mathematics—proofs in which a very large number of cases need to be checked, too large to be practical to be done by hand. One of the first was the proof of the four-color theorem in 1976. Given the advances in computing between 1976 and today, you could probably do that particular proof on a cell phone today, but more general programs have been written for proving algorithms, but the power of these to prove a particular algorithm depends in part on the computer's available memory. We can imagine proofs which require many many orders of magnitude more computing power and memory than the four-color theorem did.
Now while Moore's law and other similar laws show exponential increases in memory density and computing speed over time, it is widely agreed that these cannot continue indefinitely. How much longer these exponential advances can continue is disputed, but it's generally agreed that there is some upper limit. Thus, the capacity of a computer which can fit in your small-room universe is finite, and in turn this means the things which can be derived in your small-room universe are limited—and particularly, more limited than they would be in a larger universe, which could hold a larger computer.
posted by DevilsAdvocate at 4:44 AM on June 24, 2009
Here's a better analogy: G2, G3, ... G(googol), G(googol+1) exist in the same way that "a prime larger than the largest known prime" exists. I.e., there is a mathematical proof of their "existence," in a platonic mathematical sense. However, this sort of existence is not the sort of existence for which information theory requires that that information is represented within the information capacity of the universe.
----------
For example, if you had a universe the size of a small room, but with the same physical laws as our universe, you could still sit in there and work out all of the same things from first principles.
No, I don't believe you could. Computer-assisted proofs are becoming more and more common in mathematics—proofs in which a very large number of cases need to be checked, too large to be practical to be done by hand. One of the first was the proof of the four-color theorem in 1976. Given the advances in computing between 1976 and today, you could probably do that particular proof on a cell phone today, but more general programs have been written for proving algorithms, but the power of these to prove a particular algorithm depends in part on the computer's available memory. We can imagine proofs which require many many orders of magnitude more computing power and memory than the four-color theorem did.
Now while Moore's law and other similar laws show exponential increases in memory density and computing speed over time, it is widely agreed that these cannot continue indefinitely. How much longer these exponential advances can continue is disputed, but it's generally agreed that there is some upper limit. Thus, the capacity of a computer which can fit in your small-room universe is finite, and in turn this means the things which can be derived in your small-room universe are limited—and particularly, more limited than they would be in a larger universe, which could hold a larger computer.
posted by DevilsAdvocate at 4:44 AM on June 24, 2009
Response by poster: Thanks, HTML!
The truncated proof, rewritten and clarified:
Let's say your sequence S was generated by algorithm A. A can be represented in B bits. Assume S can only be represented in Z (greater than B) bits, i.e. we think S has more information than the algorithm that produced it. But anywhere I have S, I can substitute in A and A only takes B bits.
For instance, many comments have mentioned the natural numbers. But I can represent the natural numbers up to N very simply:
10 I = 0
20 I = I + 1
30 PRINT I
40 IF I <>
That's only around 50-100 bytes. Therefore the natural numbers up to N cannot contain more than 50-100 bytes.
posted by DU at 4:51 AM on June 24, 2009
The truncated proof, rewritten and clarified:
Let's say your sequence S was generated by algorithm A. A can be represented in B bits. Assume S can only be represented in Z (greater than B) bits, i.e. we think S has more information than the algorithm that produced it. But anywhere I have S, I can substitute in A and A only takes B bits.
For instance, many comments have mentioned the natural numbers. But I can represent the natural numbers up to N very simply:
10 I = 0
20 I = I + 1
30 PRINT I
40 IF I <>
That's only around 50-100 bytes. Therefore the natural numbers up to N cannot contain more than 50-100 bytes.
posted by DU at 4:51 AM on June 24, 2009
...the capacity of a computer which can fit in your small-room universe is finite, and in turn this means the things which can be derived in your small-room universe are limited—and particularly, more limited than they would be in a larger universe, which could hold a larger computer.
Wait, that doesn't make sense to me. Just because one can't work something out within limited space and time doesn't mean it's not true or doesn't exist. If you had a small-room universe and only enough time in it to sit down and work out either axiom A or axiom B, they're both still "there", encoded in the workings of that universe.
posted by lucidium at 5:46 AM on June 24, 2009
Wait, that doesn't make sense to me. Just because one can't work something out within limited space and time doesn't mean it's not true or doesn't exist. If you had a small-room universe and only enough time in it to sit down and work out either axiom A or axiom B, they're both still "there", encoded in the workings of that universe.
posted by lucidium at 5:46 AM on June 24, 2009
Godel's claim is that the Big Algorithm can generate unlimited mathematical axioms
I do not see that Godel is claiming this. Godel claims that unlimited mathematical axioms exist (in the same sense that an infinite number of primes exist), not that those unlimited axioms can be generated within a finite universe.
FWIW, I agree with everything you say in this comment. (Or what I believe you meant to say, if the HTML had worked out like you intended.)
We can take it a bit farther:
Each axiom in the G, G2, G3... series added to our system adds at least one bit of information. (Not because one bit is a quantum of information; information theory allows fractional bits of information. Rather, because each addition is a choice between [at least] two arbitrary choices: G is undecidable within S, so we could add either G or ~G as an axiom to S, and an arbitrary selection between two possibilities constitutes one bit of information. The same applies for each subsequent addition of another axiom.) Thus, information theory requires that G...Gn requires at least n bits to represent.
If you can find an algorithm to generate G...Gn, which algorithm can be encoded in fewer than n bits, then you have broken information theory (at least as I understand it). I do not see that either you or Godel have yet described such an algorithm.
posted by DevilsAdvocate at 5:46 AM on June 24, 2009
I do not see that Godel is claiming this. Godel claims that unlimited mathematical axioms exist (in the same sense that an infinite number of primes exist), not that those unlimited axioms can be generated within a finite universe.
FWIW, I agree with everything you say in this comment. (Or what I believe you meant to say, if the HTML had worked out like you intended.)
We can take it a bit farther:
Each axiom in the G, G2, G3... series added to our system adds at least one bit of information. (Not because one bit is a quantum of information; information theory allows fractional bits of information. Rather, because each addition is a choice between [at least] two arbitrary choices: G is undecidable within S, so we could add either G or ~G as an axiom to S, and an arbitrary selection between two possibilities constitutes one bit of information. The same applies for each subsequent addition of another axiom.) Thus, information theory requires that G...Gn requires at least n bits to represent.
If you can find an algorithm to generate G...Gn, which algorithm can be encoded in fewer than n bits, then you have broken information theory (at least as I understand it). I do not see that either you or Godel have yet described such an algorithm.
posted by DevilsAdvocate at 5:46 AM on June 24, 2009
Just because one can't work something out within limited space and time doesn't mean it's not true or doesn't exist.
It exists in a platonic mathematical sense (the same sense in which an infinite number of primes exist). It does not exist in an information theoretical sense (which talks about the space and time and matter and energy needed to encode a certain amount of information, if "information" is defined in a suitable way, and the way in which "information" is defined in information theory does not include things which are merely known to exist in the platonic mathematical sense).
posted by DevilsAdvocate at 5:51 AM on June 24, 2009
It exists in a platonic mathematical sense (the same sense in which an infinite number of primes exist). It does not exist in an information theoretical sense (which talks about the space and time and matter and energy needed to encode a certain amount of information, if "information" is defined in a suitable way, and the way in which "information" is defined in information theory does not include things which are merely known to exist in the platonic mathematical sense).
posted by DevilsAdvocate at 5:51 AM on June 24, 2009
DU, your algorithm has to contain its stopping point, N, which has a complexity of N. The information entropy (the size of your program in bits) goes like the logarithm of the complexity.
You really need to read more about Chaitin complexity.
posted by fantabulous timewaster at 5:53 AM on June 24, 2009
You really need to read more about Chaitin complexity.
posted by fantabulous timewaster at 5:53 AM on June 24, 2009
Response by poster: If you can find an algorithm to generate G...Gn, which algorithm can be encoded in fewer than n bits
I'm saying that Godel claims to have such an algorithm. Actually, he claims that that the entire universe, including himself, is that algorithm. In 1934, the Big Algorithm constructed G. G is an actual statement consisting of a finite sequence of actual integers that has been written on really real paper. It exists. There does not seem to be any reason that G2, G3, etc could not also be constructed using the same method (possibly with a human in the loop, but they are part of the Big Algorithm). I.e., they don't have to be infinitely long or anything crazy like that.
I realize the difference you are trying to draw between existence and construction. I'm not so sure the difference is relevant to the information content of the axiom. But even setting that aside, I think you are making things unfairly hard by requiring ACTUAL construction rather than just a proof that construction is possible.
I'm not actually trying to explode the universe from the inside and spew bits everywhere. I'm saying that if the potential output of an algorithm exceeds the algorithm itself, something is wrong. Or put another way, the size of the algorithm is the size of the potential output. If the potential output is infinite, then the algorithm must be infinite.
posted by DU at 6:06 AM on June 24, 2009
I'm saying that Godel claims to have such an algorithm. Actually, he claims that that the entire universe, including himself, is that algorithm. In 1934, the Big Algorithm constructed G. G is an actual statement consisting of a finite sequence of actual integers that has been written on really real paper. It exists. There does not seem to be any reason that G2, G3, etc could not also be constructed using the same method (possibly with a human in the loop, but they are part of the Big Algorithm). I.e., they don't have to be infinitely long or anything crazy like that.
I realize the difference you are trying to draw between existence and construction. I'm not so sure the difference is relevant to the information content of the axiom. But even setting that aside, I think you are making things unfairly hard by requiring ACTUAL construction rather than just a proof that construction is possible.
I'm not actually trying to explode the universe from the inside and spew bits everywhere. I'm saying that if the potential output of an algorithm exceeds the algorithm itself, something is wrong. Or put another way, the size of the algorithm is the size of the potential output. If the potential output is infinite, then the algorithm must be infinite.
posted by DU at 6:06 AM on June 24, 2009
Sorry DevilsAdvocate, I'm coming at this as a layman so bear with me if I'm being completely dense. I'm not sure what's meant by something existing in a platonic mathematical sense. Is it saying that, yes this thing is true, it's just not physically written down?
Going back to the original question, "Can the Universe hold all of mathematics?", I'm thinking that the answer is "Yes, it does hold all of mathematics, simply in its fundamental structure". In the same way that all of the laws of physics we may one day discover are already "encoded" in the universe.
In other words, while we could prove an infinite number of individual laws about the way the universe behaves, every one of them is just one way of describing some small feature of the universe. All of that "information" is still originally encoded in the actual universe itself.
I mean, the information about the state of a single particle would take far more than that single particle to encode in any way we could understand, but that information is still there within the very existence of the particle.
posted by lucidium at 6:15 AM on June 24, 2009
Going back to the original question, "Can the Universe hold all of mathematics?", I'm thinking that the answer is "Yes, it does hold all of mathematics, simply in its fundamental structure". In the same way that all of the laws of physics we may one day discover are already "encoded" in the universe.
In other words, while we could prove an infinite number of individual laws about the way the universe behaves, every one of them is just one way of describing some small feature of the universe. All of that "information" is still originally encoded in the actual universe itself.
I mean, the information about the state of a single particle would take far more than that single particle to encode in any way we could understand, but that information is still there within the very existence of the particle.
posted by lucidium at 6:15 AM on June 24, 2009
Technical nitpick, which admittedly does not change your underlying point:
That's only around 50-100 bytes.
You need to include not just the bytes in the overt program itself, but also the bytes in its interpreter/compiler/etc. in establishing an upper bound for the information content. If you're using a standard BASIC interpreter, that adds quite a bit more than 50-100 bytes. Of course, you could make a very stripped-down interpreter for executing this program specifically, which would be much smaller than a standard BASIC interpreter, but you still have to include the interpreter in your byte count.
Here's a thought experiment: consider the programming language TOW. TOW has only a single command,
The program is only five bytes long. Yet, I think we would agree that the text of the Treaty of Westphalia contains more than five bytes of information. The apparent paradox is resolved by noting that the text of the Treaty of Westphalia must be encoded somewhere withinin the TOW interpreter/compiler, and the combined length of the program plus the length of the interpreter/compiler must be at least as great as the information content of the Treaty of Westphalia.
Which does not change your underlying point that, for sufficiently large N, the natural numbers between 1 and N contain far fewer than N bits of information (probably something on the order of log N, I'm guessing).
posted by DevilsAdvocate at 6:30 AM on June 24, 2009
10 I = 0
20 I = I + 1
30 PRINT I
40 IF I <> That's only around 50-100 bytes.
You need to include not just the bytes in the overt program itself, but also the bytes in its interpreter/compiler/etc. in establishing an upper bound for the information content. If you're using a standard BASIC interpreter, that adds quite a bit more than 50-100 bytes. Of course, you could make a very stripped-down interpreter for executing this program specifically, which would be much smaller than a standard BASIC interpreter, but you still have to include the interpreter in your byte count.
Here's a thought experiment: consider the programming language TOW. TOW has only a single command,
print. print takes no arguments. The effect of print is to send the text of the Treaty of Westphalia to the standard output. Now, consider the TOW programprintThe program is only five bytes long. Yet, I think we would agree that the text of the Treaty of Westphalia contains more than five bytes of information. The apparent paradox is resolved by noting that the text of the Treaty of Westphalia must be encoded somewhere withinin the TOW interpreter/compiler, and the combined length of the program plus the length of the interpreter/compiler must be at least as great as the information content of the Treaty of Westphalia.
Which does not change your underlying point that, for sufficiently large N, the natural numbers between 1 and N contain far fewer than N bits of information (probably something on the order of log N, I'm guessing).
posted by DevilsAdvocate at 6:30 AM on June 24, 2009
I'm saying that Godel claims to have such an algorithm. Actually, he claims that that the entire universe, including himself, is that algorithm.
I am still not convinced that this is correct. Could you point me to something that would support that?
G is an actual statement consisting of a finite sequence of actual integers that has been written on really real paper. It exists.
No dispute with you there.
There does not seem to be any reason that G2, G3, etc could not also be constructed using the same method
I admit I'm don't understand the construction of G well enough to evaluate whether this is correct or not.
I'm saying that if the potential output of an algorithm exceeds the algorithm itself, something is wrong. Or put another way, the size of the algorithm is the size of the potential output. If the potential output is infinite, then the algorithm must be infinite.
I agree with all of this as well. If there is indeed a finite algorithm (which may or may not include a human, as long as the instructions are unambiguous and do not require any "leaps of insight" on the part of the human) which generates the infinite G series, then either information theory is incorrect, or my understanding of information theory is incorrect.
Basically, I see three possibilities (of which at least one, but possibly more than one, must be true):
1) There is no algorithm shorter than n bits which can generate G1...Gn.
2) Information theory is incorrect.
3) My understanding of information theory is incorrect.
I currently believe (1), but admit that this may be a result of my incomplete understanding of the method used to generate G, and whether that same method could also be used to generate G2, etc. If I could be convinced that (1) is false, I would be forced to conclude that either (2) or (3), or possibly both, are true. (Probably (3)).
posted by DevilsAdvocate at 6:48 AM on June 24, 2009
I am still not convinced that this is correct. Could you point me to something that would support that?
G is an actual statement consisting of a finite sequence of actual integers that has been written on really real paper. It exists.
No dispute with you there.
There does not seem to be any reason that G2, G3, etc could not also be constructed using the same method
I admit I'm don't understand the construction of G well enough to evaluate whether this is correct or not.
I'm saying that if the potential output of an algorithm exceeds the algorithm itself, something is wrong. Or put another way, the size of the algorithm is the size of the potential output. If the potential output is infinite, then the algorithm must be infinite.
I agree with all of this as well. If there is indeed a finite algorithm (which may or may not include a human, as long as the instructions are unambiguous and do not require any "leaps of insight" on the part of the human) which generates the infinite G series, then either information theory is incorrect, or my understanding of information theory is incorrect.
Basically, I see three possibilities (of which at least one, but possibly more than one, must be true):
1) There is no algorithm shorter than n bits which can generate G1...Gn.
2) Information theory is incorrect.
3) My understanding of information theory is incorrect.
I currently believe (1), but admit that this may be a result of my incomplete understanding of the method used to generate G, and whether that same method could also be used to generate G2, etc. If I could be convinced that (1) is false, I would be forced to conclude that either (2) or (3), or possibly both, are true. (Probably (3)).
posted by DevilsAdvocate at 6:48 AM on June 24, 2009
I'm not sure what's meant by something existing in a platonic mathematical sense. Is it saying that, yes this thing is true, it's just not physically written down?
Not so much physically "written down" (in a way that humans could understand it) but "physically represented within the universe." For example, let me go out of sequence and take your last paragraph:
I mean, the information about the state of a single particle would take far more than that single particle to encode in any way we could understand, but that information is still there within the very existence of the particle.
Yes, this I agree with, even in the information theoretical sense of "information." It has a physical representation within the universe. However:
Going back to the original question, "Can the Universe hold all of mathematics?", I'm thinking that the answer is "Yes, it does hold all of mathematics, simply in its fundamental structure".
I think that depends on what you mean by "hold." Let me propose a few questions to get a better idea of what you mean by "hold":
Do you believe the universe holds all possible strings of characters? (And why or why not?) If you do, some of those strings represent mathematical statements. Some of them represent true mathematical statements; some represent false mathematical statements. Do you believe, then, that the universe also holds all false mathematical statements?
More generally, what is "true" or "false" in mathematics depends on the system of axioms and rules chosen, and different systems of mathematics generates different truth values for some statements. For example, even though the universe itself appears to follow a non-Euclidean geometry, we can still conceive of, and reason about, and make statements about Euclidean geometry. Does the universe "hold" Euclidean geometry?
OTOH, if you argue that the universe does not hold all possible strings of characters, how do you reconcile that with the fact that it is trivial to construct an algorithm which could generate all possible strings of characters, given infinite time?
In other words, while we could prove an infinite number of individual laws about the way the universe behaves
I think maybe we're playing too loose with the distinction between physical laws and mathematics here. While we can discover physical laws that control the universe, that's not the same as mathematics, which I see as pure abstraction. For example, we can agree on E=mc2 as a physical law which describes the conversion of mass to energy or vice versa if E represents energy, m represents mass, and c represents the speed of light in a vacuum, all physical quantities. If we have a purely mathematical statement (a2+b2=c2), that's a mathematical abstraction, and I'm not convinced that the mathematical abstraction is true or false in any way which is "held" within the universe. Now, if we interpret a, b, and c to be actual physical quantities which exist within the universe, the statement then becomes a physical law, but it may be true for one set of physical quantities a, b, and c, and false for a different a, b, and c. And if you want to say that physical law (the true one, at least) is represented in the universe, I'd probably agree with you. But I'm not so sure about the pure underlying mathematical abstraction.
posted by DevilsAdvocate at 7:15 AM on June 24, 2009
Not so much physically "written down" (in a way that humans could understand it) but "physically represented within the universe." For example, let me go out of sequence and take your last paragraph:
I mean, the information about the state of a single particle would take far more than that single particle to encode in any way we could understand, but that information is still there within the very existence of the particle.
Yes, this I agree with, even in the information theoretical sense of "information." It has a physical representation within the universe. However:
Going back to the original question, "Can the Universe hold all of mathematics?", I'm thinking that the answer is "Yes, it does hold all of mathematics, simply in its fundamental structure".
I think that depends on what you mean by "hold." Let me propose a few questions to get a better idea of what you mean by "hold":
Do you believe the universe holds all possible strings of characters? (And why or why not?) If you do, some of those strings represent mathematical statements. Some of them represent true mathematical statements; some represent false mathematical statements. Do you believe, then, that the universe also holds all false mathematical statements?
More generally, what is "true" or "false" in mathematics depends on the system of axioms and rules chosen, and different systems of mathematics generates different truth values for some statements. For example, even though the universe itself appears to follow a non-Euclidean geometry, we can still conceive of, and reason about, and make statements about Euclidean geometry. Does the universe "hold" Euclidean geometry?
OTOH, if you argue that the universe does not hold all possible strings of characters, how do you reconcile that with the fact that it is trivial to construct an algorithm which could generate all possible strings of characters, given infinite time?
In other words, while we could prove an infinite number of individual laws about the way the universe behaves
I think maybe we're playing too loose with the distinction between physical laws and mathematics here. While we can discover physical laws that control the universe, that's not the same as mathematics, which I see as pure abstraction. For example, we can agree on E=mc2 as a physical law which describes the conversion of mass to energy or vice versa if E represents energy, m represents mass, and c represents the speed of light in a vacuum, all physical quantities. If we have a purely mathematical statement (a2+b2=c2), that's a mathematical abstraction, and I'm not convinced that the mathematical abstraction is true or false in any way which is "held" within the universe. Now, if we interpret a, b, and c to be actual physical quantities which exist within the universe, the statement then becomes a physical law, but it may be true for one set of physical quantities a, b, and c, and false for a different a, b, and c. And if you want to say that physical law (the true one, at least) is represented in the universe, I'd probably agree with you. But I'm not so sure about the pure underlying mathematical abstraction.
posted by DevilsAdvocate at 7:15 AM on June 24, 2009
DU, I'm not sure why you view a sequence of objects (like the natural numbers) which is generated by a finite list of axioms (the Peano axioms) as any different from a sequence of axioms (Gödel's business) which is generated by a finite list of axioms (specificially, ZFC).
In each case, I'm taking the initial segment of my sequence and saying "That's not enough, let's add on another in a very specific way."
posted by TypographicalError at 7:46 AM on June 24, 2009
In each case, I'm taking the initial segment of my sequence and saying "That's not enough, let's add on another in a very specific way."
posted by TypographicalError at 7:46 AM on June 24, 2009
by a finite list of axioms (specificially, ZFC)
Although, there is the issue of the axiom schemata as well. Even in very basic set theory, you have to start with a (sorta) infinite set of axioms.
posted by TypographicalError at 7:49 AM on June 24, 2009
Although, there is the issue of the axiom schemata as well. Even in very basic set theory, you have to start with a (sorta) infinite set of axioms.
posted by TypographicalError at 7:49 AM on June 24, 2009
Response by poster: I'm not sure why you view a sequence of objects (like the natural numbers) which is generated by a finite list of axioms (the Peano axioms) as any different from a sequence of axioms (Gödel's business) which is generated by a finite list of axioms (specificially, ZFC)
As I said upthread somewhere, I'm probably being blinded by the "complexity" (in regular English usage) of axioms vs plain integers.
So. 11 am. Restate assumptions. The universe is finite. The universe can generate as many axioms as it wants. Therefore these axioms are information-free (or at least the sum of all the information converges on a finite amount).
It seems strange to me that you could discover something that nobody ever knew and it wouldn't contain any actual "information". But again, I'm likely blinded by English and ignorance.
posted by DU at 7:58 AM on June 24, 2009
As I said upthread somewhere, I'm probably being blinded by the "complexity" (in regular English usage) of axioms vs plain integers.
So. 11 am. Restate assumptions. The universe is finite. The universe can generate as many axioms as it wants. Therefore these axioms are information-free (or at least the sum of all the information converges on a finite amount).
It seems strange to me that you could discover something that nobody ever knew and it wouldn't contain any actual "information". But again, I'm likely blinded by English and ignorance.
posted by DU at 7:58 AM on June 24, 2009
Although, there is the issue of the axiom schemata as well. Even in very basic set theory, you have to start with a (sorta) infinite set of axioms.
But if that's the case, aren't you starting with an infinite amount of information? There's no paradox in generating statements representing an infinite amount of information, if you had an infinite amount of information to start with.
Unless you're doing it within a finite universe, and then, you've simply sidestepped the question of how an infinite amount of information got into a finite universe in the first place, in apparent contradiction to information theory.
----------
It seems strange to me that you could discover something that nobody ever knew and it wouldn't contain any actual "information".
I think that's getting back to the confusion between colloquial common-sense information and formalized information theory-type information. On August 23, 2008, it was discovered that 243112609-1 was prime. No human ever knew that before August 23, 2008. So in a colloquial common-sense definition of information, it's new information. In a formalized sense of information, it's not, since it was provable from the axioms and rules of standard mathematics, so it was already included in the information content of that system, even though no one knew it before August 23, 2008. Why should we have a formalized definition that doesn't entirely match the common-sense definition at all? Because the formalized definition has useful real-world applications.
posted by DevilsAdvocate at 8:16 AM on June 24, 2009
But if that's the case, aren't you starting with an infinite amount of information? There's no paradox in generating statements representing an infinite amount of information, if you had an infinite amount of information to start with.
Unless you're doing it within a finite universe, and then, you've simply sidestepped the question of how an infinite amount of information got into a finite universe in the first place, in apparent contradiction to information theory.
----------
It seems strange to me that you could discover something that nobody ever knew and it wouldn't contain any actual "information".
I think that's getting back to the confusion between colloquial common-sense information and formalized information theory-type information. On August 23, 2008, it was discovered that 243112609-1 was prime. No human ever knew that before August 23, 2008. So in a colloquial common-sense definition of information, it's new information. In a formalized sense of information, it's not, since it was provable from the axioms and rules of standard mathematics, so it was already included in the information content of that system, even though no one knew it before August 23, 2008. Why should we have a formalized definition that doesn't entirely match the common-sense definition at all? Because the formalized definition has useful real-world applications.
posted by DevilsAdvocate at 8:16 AM on June 24, 2009
Thanks for taking the time to reply DevilsAdvocate. I'll try and explain my thinking without rambling too much.
I'm a bit confused by your question "Do you believe the universe holds all possible strings of characters?" and the questions to do with that.
I think I'm right in saying that characters are completely meaningless things on their own, without an "interpreter" or person who understands the language. So any meaningful statements that come out of a sequence generator are a function of the reader, not the writer. I wouldn't say the universe "holds" all possible strings any more than it "holds" all possible configurations of atoms. All possible configurations could happen, and that set of possibilities is derived from the laws of the universe, but that seems unrelated to the existence of conceptual things and meaning.
You make a good point about the distinction between physical laws and mathematics. I think we agree that physical laws that humans write down are representations of the behaviour of the universe itself, and so whatever information we have about physics was already there, or "held" in the universe.
The more I think about it the less sure I am, but originally my thinking about mathematics was that:
- The systems of mathematics we're talking about here must be logical, otherwise they are meaningless, and a meaningless thing is informationless(?).
- The laws of logic come from the behaviour of the universe.
- All of mathematics can be looked at as facets of a system, so even as we discover and produce new branches of mathematics, we're not creating any actual new "information".
- So just like physics, all of mathematics is simply describing and representing the underlying universe it exists it.
So I guess what I'm ultimately assuming is that even purely conceptual mathematics relies on some fundamental things that are defined by the universe, and that it's impossible to have a system that is completely unconnected to the workings of the universe.
posted by lucidium at 8:36 AM on June 24, 2009
I'm a bit confused by your question "Do you believe the universe holds all possible strings of characters?" and the questions to do with that.
I think I'm right in saying that characters are completely meaningless things on their own, without an "interpreter" or person who understands the language. So any meaningful statements that come out of a sequence generator are a function of the reader, not the writer. I wouldn't say the universe "holds" all possible strings any more than it "holds" all possible configurations of atoms. All possible configurations could happen, and that set of possibilities is derived from the laws of the universe, but that seems unrelated to the existence of conceptual things and meaning.
You make a good point about the distinction between physical laws and mathematics. I think we agree that physical laws that humans write down are representations of the behaviour of the universe itself, and so whatever information we have about physics was already there, or "held" in the universe.
The more I think about it the less sure I am, but originally my thinking about mathematics was that:
- The systems of mathematics we're talking about here must be logical, otherwise they are meaningless, and a meaningless thing is informationless(?).
- The laws of logic come from the behaviour of the universe.
- All of mathematics can be looked at as facets of a system, so even as we discover and produce new branches of mathematics, we're not creating any actual new "information".
- So just like physics, all of mathematics is simply describing and representing the underlying universe it exists it.
So I guess what I'm ultimately assuming is that even purely conceptual mathematics relies on some fundamental things that are defined by the universe, and that it's impossible to have a system that is completely unconnected to the workings of the universe.
posted by lucidium at 8:36 AM on June 24, 2009
Thanks for your response, lucidium. It clarifies your position for me quite a bit. I agree with most of what you say, but I'd like to address just a few points where we disagree:
The laws of logic come from the behaviour of the universe.
I don't agree with that, but I'm not sure I can make a strong argument against it, either. Would you say that a different universe might have different laws of logic? (After all, it is not difficult to imagine that a different universe would have different physical laws, but it is difficult to imagine a universe with different logical laws. Admittedly, my inability to imagine something is not proof of its impossibility.)
So just like physics, all of mathematics is simply describing and representing the underlying universe it exists it.
Except that some branches mathematics don't describe or represent the underlying universe. Euclidean geometry, for one (except as an approximation, under certain circumstances). Yet no one says that Euclidean geometry is not a branch of mathematics, simply because it does not describe the universe as we know it. Does the universe "hold" Euclidean geometry? Or does it only hold those parts of mathematics which are relevant to its operation?
posted by DevilsAdvocate at 9:16 AM on June 24, 2009
The laws of logic come from the behaviour of the universe.
I don't agree with that, but I'm not sure I can make a strong argument against it, either. Would you say that a different universe might have different laws of logic? (After all, it is not difficult to imagine that a different universe would have different physical laws, but it is difficult to imagine a universe with different logical laws. Admittedly, my inability to imagine something is not proof of its impossibility.)
So just like physics, all of mathematics is simply describing and representing the underlying universe it exists it.
Except that some branches mathematics don't describe or represent the underlying universe. Euclidean geometry, for one (except as an approximation, under certain circumstances). Yet no one says that Euclidean geometry is not a branch of mathematics, simply because it does not describe the universe as we know it. Does the universe "hold" Euclidean geometry? Or does it only hold those parts of mathematics which are relevant to its operation?
posted by DevilsAdvocate at 9:16 AM on June 24, 2009
I think you've nailed it with those two points.
I assume that the laws of logic depend on the universe, but I can't make a great argument either way for that either. I just feel like if there are possible alternate physical laws there could be alternate logical laws. I could suggest a universe where causality doesn't hold, and A is not A, but that's more nonsensical word salad than anything, and I can't get my head around an actual example.
Also with your example of Euclidean geometry, I'm just assuming that for any system to be meaningful it has to follow some fundamental rules of the universe. But again, this is just a feeling I have.
posted by lucidium at 9:41 AM on June 24, 2009
I assume that the laws of logic depend on the universe, but I can't make a great argument either way for that either. I just feel like if there are possible alternate physical laws there could be alternate logical laws. I could suggest a universe where causality doesn't hold, and A is not A, but that's more nonsensical word salad than anything, and I can't get my head around an actual example.
Also with your example of Euclidean geometry, I'm just assuming that for any system to be meaningful it has to follow some fundamental rules of the universe. But again, this is just a feeling I have.
posted by lucidium at 9:41 AM on June 24, 2009
DevilsAdvocate: "But if that's the case, aren't you starting with an infinite amount of information? There's no paradox in generating statements representing an infinite amount of information, if you had an infinite amount of information to start with."
It doesn't seem so to me. Here's why I think not:
Let's say I set up a booth where I'll give you a box for each new item you bring in. So, if you bring in 10 things, I'll deposit them in 10 boxes. This is all well and good as long as you only bring in a finite number of things, but when you bring in an infinite number of things, then I need to have an infinite number of boxes.*
In the same way, if you start with a finite amount of things to put in the schemata, then necessarily you only get finitely many axioms.
* Incidentally, the treatment of infinity in this discussion has had a very nonmathematical handwavy feel to it, and I expect that this may be a not insignificant problem.
posted by TypographicalError at 9:51 AM on June 24, 2009
It doesn't seem so to me. Here's why I think not:
Let's say I set up a booth where I'll give you a box for each new item you bring in. So, if you bring in 10 things, I'll deposit them in 10 boxes. This is all well and good as long as you only bring in a finite number of things, but when you bring in an infinite number of things, then I need to have an infinite number of boxes.*
In the same way, if you start with a finite amount of things to put in the schemata, then necessarily you only get finitely many axioms.
* Incidentally, the treatment of infinity in this discussion has had a very nonmathematical handwavy feel to it, and I expect that this may be a not insignificant problem.
posted by TypographicalError at 9:51 AM on June 24, 2009
In the same way, if you start with a finite amount of things to put in the schemata, then necessarily you only get finitely many axioms.
You've lost me there, I think. Are you saying that although the schemata is potentially infinite, for any particular application of ZFC we only consider the subset, possibly (necessarily?) finite, of those axioms necessary to show whatever it is we want to show?
In any case, I'm not sure it matters. DU and I seem to agree that Peano+G+G2+G3... comprise an infinite amount of information. (Where G is an undecidable proposition under Peano, G2 is an undecidable proposition under Peano+G, etc.) You seem to believe that Peano+G+G2+G3... comprises only a finite amount of information, as it can be derived from ZFC. (Or possibly some subset thereof?)
Then, my question to you is: does ZFC (or whatever subset is necessary) comprise a finite or an infinite amount of information?
If it comprises an infinite amount of information, it is not a contradiction to say that other statements which may be derived from it (notably: Peano+G+G2+G3...) also comprise an infinite amount of information.
If it comprises a finite amount of information, we can just re-create DU's dilemma starting with ZFC (or subset thereof) instead of with Peano, since Godel's incompleteness theorem applies to ZFC just as well as it does to Peano. Namely: there exists an undecidable statement under ZFC. Let's find one and call it H. Now we can add H (or ~H, I don't care) to ZFC, and ZFC+H contains more information than ZFC. Specifically, at least one bit more information, per my argument here. Godel says there exists an undecidable statement under ZFC+H; call it H2. ZFC+H+H2 has at least one bit more information than ZFC+H. Repeat ad infinitum, and you have an infinite amount of information.
Incidentally, the treatment of infinity in this discussion has had a very nonmathematical handwavy feel to it, and I expect that this may be a not insignificant problem.
It's certainly possible. If there's a particular place you see it causing a problem, by all means enlighten us.
posted by DevilsAdvocate at 10:29 AM on June 24, 2009
You've lost me there, I think. Are you saying that although the schemata is potentially infinite, for any particular application of ZFC we only consider the subset, possibly (necessarily?) finite, of those axioms necessary to show whatever it is we want to show?
In any case, I'm not sure it matters. DU and I seem to agree that Peano+G+G2+G3... comprise an infinite amount of information. (Where G is an undecidable proposition under Peano, G2 is an undecidable proposition under Peano+G, etc.) You seem to believe that Peano+G+G2+G3... comprises only a finite amount of information, as it can be derived from ZFC. (Or possibly some subset thereof?)
Then, my question to you is: does ZFC (or whatever subset is necessary) comprise a finite or an infinite amount of information?
If it comprises an infinite amount of information, it is not a contradiction to say that other statements which may be derived from it (notably: Peano+G+G2+G3...) also comprise an infinite amount of information.
If it comprises a finite amount of information, we can just re-create DU's dilemma starting with ZFC (or subset thereof) instead of with Peano, since Godel's incompleteness theorem applies to ZFC just as well as it does to Peano. Namely: there exists an undecidable statement under ZFC. Let's find one and call it H. Now we can add H (or ~H, I don't care) to ZFC, and ZFC+H contains more information than ZFC. Specifically, at least one bit more information, per my argument here. Godel says there exists an undecidable statement under ZFC+H; call it H2. ZFC+H+H2 has at least one bit more information than ZFC+H. Repeat ad infinitum, and you have an infinite amount of information.
Incidentally, the treatment of infinity in this discussion has had a very nonmathematical handwavy feel to it, and I expect that this may be a not insignificant problem.
It's certainly possible. If there's a particular place you see it causing a problem, by all means enlighten us.
posted by DevilsAdvocate at 10:29 AM on June 24, 2009
Response by poster: I think DA had a good point a while ago when he said that each Godel statement Gi was at least one bit of information, which was whether you were accepting Gi or !Gi. Each Gi is a blank spot I need set to 0 or 1. Therefore I can run through N Gis and get at least N bits of information, where I chose N to be larger than the universe's capacity.
However, I need some scheme to choose the 0 or the 1, right? Let's say I just choose 0 all the time. But a huge string of N 0s isn't really N bits of information. Likewise, if I say "choose 0 for the evens and 1 for the odds" I still don't have N bits. I'd have to choose them randomly somehow.
But I can't do that either, because I'm trapped inside the Big Algorithm. I'm forced to be predictable, even if to predict my responses you'd have to simulate the entire universe. So that bit string can't have more information than the universe does.
posted by DU at 10:32 AM on June 24, 2009
However, I need some scheme to choose the 0 or the 1, right? Let's say I just choose 0 all the time. But a huge string of N 0s isn't really N bits of information. Likewise, if I say "choose 0 for the evens and 1 for the odds" I still don't have N bits. I'd have to choose them randomly somehow.
But I can't do that either, because I'm trapped inside the Big Algorithm. I'm forced to be predictable, even if to predict my responses you'd have to simulate the entire universe. So that bit string can't have more information than the universe does.
posted by DU at 10:32 AM on June 24, 2009
Good point, DU. I had originally pointed out that each statement adds at least one bit to exclude the possibility that the entire infinite series of G statements might contribute only a finite amount of information, but I hadn't considered that implication of it. I think you've found the way out of the dilemma. (Although you could reinstate it if you could show, for example, that each G statement contributes 2 bits of information. Then you could choose 2N to be larger than the universe's capacity, but it would still take only N bits to make the necessary choices. It's hard to imagine that each additional G statement would add only one bit of new information, but I can't prove otherwise.)
posted by DevilsAdvocate at 11:01 AM on June 24, 2009
posted by DevilsAdvocate at 11:01 AM on June 24, 2009
Response by poster: One potential problem is that I'm not sure you could predict my responses by simulating the entire universe. What if I hook up the G Truthiness Assigner Machine to a radioactive sample? Apparently (and I find this hard to credit, but there it is) there are hidden variables and this stuff isn't just hard to predict, it is actually, mathematically *impossible*. So then my string should be truly random and therefore have a good amount of information?
posted by DU at 11:07 AM on June 24, 2009
posted by DU at 11:07 AM on June 24, 2009
I don't think it matters: the maximum information content of a finite universe is the maximum information content of that universe, regardless of whether the information is generated "predictably" or not. A universe with an information capacity of 1000 bits simply cannot contain a radioactive sample capable of generating 1001 bits. If a universe has a radioactive sample capable of generating 1001 bits, that universe by definition has an information capacity of at least 1001 bits.
posted by DevilsAdvocate at 11:27 AM on June 24, 2009
posted by DevilsAdvocate at 11:27 AM on June 24, 2009
There's a quantitative question that I alluded to above, but is worth emphasizing since it seems to be leading to some confusion:
Not that it's never possible to find an encoding for n smaller than log2 n bits: a good example is 3333, which would take a terabyte to store fully. But trying to find the shortest representation for an arbitrary number opens Gödel- and Turing-type problems. For example, there are a finite number of words in English, so all the English phrases of a given length can only describe a finite number of the integers. But it's not a set that you can compute. For instance, the smallest number not describable in English in fewer than thirteen words has a twelve-word description: "the smallest number not describable in English in fewer than thirteen words." This is exactly analogous to Gödel's construction of a statement labeled S that says "the statement labeled S is false."
I stand by my earlier answer to your overall question: the universe can contain more of mathematics than the collective human intellect.
Books: Warmth Disperses and Time Passes by von Bayer for thermodynamic and information entropy; I first learned about Chaitin complexity in this biography of Gödel.
posted by fantabulous timewaster at 5:38 AM on June 25, 2009
If you can find an algorithm to generate G...Gn, which algorithm can be encoded in fewer than n bitsThis is NOT HARD. What's hard (impossible, I think) is encoding it in less than log2 n bits, which is the minimum space needed to encode n.
Not that it's never possible to find an encoding for n smaller than log2 n bits: a good example is 3333, which would take a terabyte to store fully. But trying to find the shortest representation for an arbitrary number opens Gödel- and Turing-type problems. For example, there are a finite number of words in English, so all the English phrases of a given length can only describe a finite number of the integers. But it's not a set that you can compute. For instance, the smallest number not describable in English in fewer than thirteen words has a twelve-word description: "the smallest number not describable in English in fewer than thirteen words." This is exactly analogous to Gödel's construction of a statement labeled S that says "the statement labeled S is false."
I stand by my earlier answer to your overall question: the universe can contain more of mathematics than the collective human intellect.
Books: Warmth Disperses and Time Passes by von Bayer for thermodynamic and information entropy; I first learned about Chaitin complexity in this biography of Gödel.
posted by fantabulous timewaster at 5:38 AM on June 25, 2009
If you can find an algorithm to generate G...Gn, which algorithm can be encoded in fewer than n bits
This is NOT HARD.
I think you're misunderstanding my statement. I'm not talking about encoding the integers 1...n in fewer than n bits (I agree, that would be easy). I'm talking about encoding the Godel statements G1...Gn we've been discussing in fewer than n bits. Where G1 is a statement that's undecidable under a suitable system (S) of axioms (e.g., the Peano axioms); G2 is a statement that's undecidable under S+G1; G3 is a statement that's undecidable under S+G1+G2; etc.
posted by DevilsAdvocate at 6:17 AM on June 25, 2009
This is NOT HARD.
I think you're misunderstanding my statement. I'm not talking about encoding the integers 1...n in fewer than n bits (I agree, that would be easy). I'm talking about encoding the Godel statements G1...Gn we've been discussing in fewer than n bits. Where G1 is a statement that's undecidable under a suitable system (S) of axioms (e.g., the Peano axioms); G2 is a statement that's undecidable under S+G1; G3 is a statement that's undecidable under S+G1+G2; etc.
posted by DevilsAdvocate at 6:17 AM on June 25, 2009
Response by poster: Warmth Disperses and Time Passes by von Bayer
I looked at this in the library just now. I'm really looking for something more mathematical. I actually owned, and read through, this at one point but now I can't find it. Just as well, I guess, since it didn't cover algorithmic representation anyway.
I've checked Chaitin out more than once but he's so self-congratulatory that I find him too hard to read.
posted by DU at 6:54 AM on June 25, 2009
I looked at this in the library just now. I'm really looking for something more mathematical. I actually owned, and read through, this at one point but now I can't find it. Just as well, I guess, since it didn't cover algorithmic representation anyway.
I've checked Chaitin out more than once but he's so self-congratulatory that I find him too hard to read.
posted by DU at 6:54 AM on June 25, 2009
DevilsAdvocate, if you have an algorithm for producing axioms in order, I think they are isomorphic to the natural numbers. So the information bound to produce n axioms is log2 n bits. This is possible to beat for any n, but it's not possible to beat for an arbitrary n (unless you can wait forever for your encoding to finish).
I'm not sure I believe there's an algorithm for producing multiple Gödel statements anyway. I thought that including the Gödel statement as an axiom makes the overall collection of axioms inconsistent (so that any statement can be proven or disproven) while excluding it shows that there exist true statement which can't be proven within that framework.
DU: I've heard that Shannon's original paper is a pretty accessible classic, but I haven't read it.
posted by fantabulous timewaster at 8:02 AM on June 26, 2009
I'm not sure I believe there's an algorithm for producing multiple Gödel statements anyway. I thought that including the Gödel statement as an axiom makes the overall collection of axioms inconsistent (so that any statement can be proven or disproven) while excluding it shows that there exist true statement which can't be proven within that framework.
DU: I've heard that Shannon's original paper is a pretty accessible classic, but I haven't read it.
posted by fantabulous timewaster at 8:02 AM on June 26, 2009
Response by poster: Very late response:
I'm not sure why you view a sequence of objects (like the natural numbers) which is generated by a finite list of axioms (the Peano axioms) as any different from a sequence of axioms (Gödel's business) which is generated by a finite list of axioms (specificially, ZFC).
Because new axioms have to have a decision made about them. There's no question that 100001 comes after 100000, but when we have a new axiom we have to decide whether to accept it. We have an infinitely long list of axioms, each of which is marked with a 0 or a 1. If I could do that marking randomly, I'd have an infinite amount of information.
Which leads me to a slight problem with my solution: Let's make Big Algorithm For Adding New Axioms be this: The value is 1 if the axiom is actually true in the real universe and 0 if it isn't.
This list of 0's and 1's must not be random, which is to say that some bits must be determinable from other bits. But each 0 or 1 is a truth value placed on a statement that was constructed to be indeterminable from the other 0's and 1's.
posted by DU at 7:45 AM on December 29, 2009
I'm not sure why you view a sequence of objects (like the natural numbers) which is generated by a finite list of axioms (the Peano axioms) as any different from a sequence of axioms (Gödel's business) which is generated by a finite list of axioms (specificially, ZFC).
Because new axioms have to have a decision made about them. There's no question that 100001 comes after 100000, but when we have a new axiom we have to decide whether to accept it. We have an infinitely long list of axioms, each of which is marked with a 0 or a 1. If I could do that marking randomly, I'd have an infinite amount of information.
Which leads me to a slight problem with my solution: Let's make Big Algorithm For Adding New Axioms be this: The value is 1 if the axiom is actually true in the real universe and 0 if it isn't.
This list of 0's and 1's must not be random, which is to say that some bits must be determinable from other bits. But each 0 or 1 is a truth value placed on a statement that was constructed to be indeterminable from the other 0's and 1's.
posted by DU at 7:45 AM on December 29, 2009
This thread is closed to new comments.
posted by DU at 5:36 AM on June 23, 2009