- Wed Aug 26, 2015 8:21 pm
#194918
So was thinking: Computer mathematics, currently, mostly functions as a brute-force method of checking things, but even that can be groundbreaking. And I started thinking, what would be the most groundbreaking thing that a brute-force search could find? And then I decided.
One thing most people don't realize about being a mathematician is that you have to live with some sense of existential angst. Why is that? Well, as my professor put it, "the foundations of math are a little shaky." That's something that every mathematician knows, and has to deal with. And one of the biggest shaky pillars of mathematics is represented by Gödel's theorem: that no system of mathematics can ever prove all theorems. Why? In a nutshell, it works like this.
Formally, we can represent a system of mathematics with a bunch of symbols and rules for manipulating them, something that we call a "formal system". The symbols, when put together in a particular order in what we call a "string", are isomorphic to mathematical statements—that is, they represent them. As long, of course, as the symbols are put in an order where they can be interpreted meaningfully (in formal terms, the string is well-formed). Starting with axioms (simple mathematical statements that are too basic to be proven) and a set of rules that represent the rules of mathematics, we produce theorems—that is, strings that we derive and that represent, ideally, true statements of mathematics. This includes everything from "1+1=2" to "there are infinitely many prime numbers" to "there is no rational square root of 2". The rules are entirely typographical, and can be applied to any string—well, to any string to which the rules say they're applicable! Since the entire system consists of typographically manipulated strings of symbols, each individual rule, and even a chain of them, can be applied with relative ease, although knowing which rules to apply to get where you want is harder. In fact, it's so simple, it can be done by a computer! Back to that later.
Now, I said earlier that a formal system should ideally "represent true statements of mathematics". While giving us a watertight and way to produce theorems is one of the main reasons it's useful to us (along with being a fascinating object of study in it's own right), it isn't quite true that it's the main goal of creating an ideal formal system. There are two properties that an ideal formal system should have.
1. Consistency. Now, this is different than "truth", and there's a reason why we have this instead (and I'll explain exactly what it is in a minute). Say my formal system produces a string that, when interpreted, gives me the theorem "1+1=0". Uh-oh, we're in trouble, right? Well, sort of, but not really. After all, remember that this is simply the way in which I choose to interpret it. All I need to do is change my interpretation to fit the model of mathematics that I'm using. So, if I'm using standard arithmetic, perhaps I'm interpreting a symbol as "0" when I should interpret it as "2". Or perhaps I'm interpreting one as "=" when I should be interpreting it (at least for my purposes), as "does not equal". And so on. And when I've altered my interpretation, voila! I have a functioning formal system. But what if I have two different theorems, one of which is interpreted as "1+1=0" and the other as "1+1 does NOT equal 0"? Well, then I'm in trouble. I can differently interpret it all I want, but short of changing my interpretation of the symbol meaning "does not" (which would mess up the rules of logic itself and severely weaken my system), there's nothing I can do. No matter what I do, I'll have a contradiction. And, lest I consider simply trying to contain it, that's not just a problem for those two statements. Because of the rules of logic, an inconsistencyof this sort spreads like a cancer, because it allows the derivation of absolutely anything. Needless to say, that renders the system completely useless. Consistency means that there are no two derivable statements that are exact opposites of each other.
2. Completeness. If consistency says "I can't derive any false theorems," completeness says "I can derive every true theorem." If 1+1=2, I can derive that (or rather, a string that represents it under my interpretation). If there are infinitely many primes, I can derive that. And so on. Slightly more formally, we'd say that for every well-formed string, either it's a theorem, or it's opposite is. A formal system both consistent and complete would include all true theorems, and exclude all false ones. It's a formalist mathematician's paradise. Unfortunately, those mathematicians have to dwell in—well, not in hell, but in purgatory. Why? I'll get to that in a moment.
So the perfect formal system would be both consistent and complete. And in 1913, Alfred North Whitehead and Bertrand Russel believed that they had created that system in their three-volume leviathan of a system, Principia Mathematica. Then in came a logician called Kurt Gödel and ruined everything. Well, not exactly. He ruined everything in the manner of the polite hacker who exploits a flaw in your system, not to destroy it, but just to point out that it's there, you can't do anything about it, and you should really stop trying to use the computer. Or any computer, actually. Because Gödel's theorem doesn't just apply to Principia Mathematica; it applies to any formal system powerful enough that we could ever even think of calling it complete. It does this because of it's essential simplicity. In a nutshell, it works like this.
So here's Whitehead and Russel, making all their rules. So many rules, and so many symbols, all of which are (presumably) necessary for the system. And Gödel realized something about those symbols that Russel and Whitehead didn't: they could be represented as numbers. And that simple realization paved the path to his groundbreaking theorem. Because if symbols can be represented as numbers, the purely typographical rules can be represented as arithmetic operations. And how can we represent arithmetic operations? That's right—in a formal system! Any sufficiently powerful system can represent ITSELF. And, through a somewhat complex process (of which the details aren't particularly necessary in this discussion) Gödel constructed a string G with the following meaning: "I am not a theorem of Principia Mathematica."
Well, from there it's onto logic. Is G or is it not a theorem of Principia Mathematica, and what does that mean for the formal system? (And every other sufficiently powerful formal system as well, since Gödel's method applies to all of them.) Well, if it IS a theorem, that means it's false, because it says it's not. But that would mean that it's opposite, not-G (which states "G is a theorem of Principia Mathematica"), is true, and if our system is complete, then not-G must then be a theorem. But if G and not-G are both theorems, that means that our formal system is inconsistent. And we KNOW that it's consistent, since we built it that way. So that can't be the case.
Well, if it's NOT a theorem, that means that it IS true. But wait—how can our system be complete if that's the case? After all, not-G would be false, so it wouldn't be a theorem, and since neither G nor not-G are theorems, that means that G is undecidable—that is, neither it nor its opposite are theorems. But this is the only logically consistent option, therefore it must be true. Therefore, Principia Mathematica (along with every other formal system) is essentially incomplete.
And thus goes the life of a mathematician, for this doesn't apply exclusively to completely formal systems, but to any system that can be formalized—which is essentially every branch of mathematics. Every mathematician goes through their day knowing that there are true theorems that are forever out of their reach. One famous example is the theory that the infinity consisting of the set of all real numbers is equal to a set called Aleph-1. Georg Cantor, the father of set theory, spent his life obsessing over this, but died unable to prove it. Hilbert sought the same thing, but, unlike Cantor, he lived long enough to see that the dream of completeness was not only out of his reach, but also out of the reach of every set theorist in the future, and indeed, to humanity in general.
Does Gödel's theorem mean that formal systems are useless? Certainly not. But it means that the Holy Grail of absolute completeness is forever out of reach. Right? Well...
There's a third option, albeit one that's quite unorthodox. See, we've been assuming that not-G is false. Well, of course it is—it asserts that its opposite is a theorem! Well, more specifically, it says that its opposite is provable. And as it happens, there's a consistent way to interpret that: that there IS a proof for G, but it has infinitely many steps, so we'll never reach it. This both resolves the incompleteness problem and opens the door to a new set of numbers known as "supernatural numbers" (or "generalized natural numbers"). I'm not very familiar with them, but they're essentially various infinite numbers (not sets, which separates them from Cantor's Alephs—don't ask me what separates them from his transfinite Omegas, because I don't know).
Gödel never proved that not-G is false and/or not a theorem, but most mathematicians assume that this is the case. But what if it's not? What if not-G is provable, and we're not living in a world of shaky foundations after all? That would be a revelation that would sweep all of mathematics! But how could we find this out?
Well, standard intuitive and formal proofs aside, what do we have that the people of Gödel's time didn't? Oh, yeah. Computers. Pretty powerful ones, too. Oh, don't get me wrong. It's ridiculously unlikely that a brute-force repeated application of rules to just create more and more and more and more and more theorems would yield any fruit on this matter, simply because it would take too long due to our computers not being powerful enough. But they're getting more and more powerful every day. And if, one day, a computer programmed with Principia Mathematica, or Douglas Hofstadter's Typographical Number theory, should pop-out not-G—well, I'd say that would be a groundbreaking result well-worth the title.
(Credit for a great deal of this information goes to both Kurt Gödel, author of the famous Incompleteness Theorem, and to Douglas Hofstadter, author of the fantastic book Gödel, Escher, Bach: an Eternal Golden Braid. Go read it!)
~dlgn
One thing most people don't realize about being a mathematician is that you have to live with some sense of existential angst. Why is that? Well, as my professor put it, "the foundations of math are a little shaky." That's something that every mathematician knows, and has to deal with. And one of the biggest shaky pillars of mathematics is represented by Gödel's theorem: that no system of mathematics can ever prove all theorems. Why? In a nutshell, it works like this.
Formally, we can represent a system of mathematics with a bunch of symbols and rules for manipulating them, something that we call a "formal system". The symbols, when put together in a particular order in what we call a "string", are isomorphic to mathematical statements—that is, they represent them. As long, of course, as the symbols are put in an order where they can be interpreted meaningfully (in formal terms, the string is well-formed). Starting with axioms (simple mathematical statements that are too basic to be proven) and a set of rules that represent the rules of mathematics, we produce theorems—that is, strings that we derive and that represent, ideally, true statements of mathematics. This includes everything from "1+1=2" to "there are infinitely many prime numbers" to "there is no rational square root of 2". The rules are entirely typographical, and can be applied to any string—well, to any string to which the rules say they're applicable! Since the entire system consists of typographically manipulated strings of symbols, each individual rule, and even a chain of them, can be applied with relative ease, although knowing which rules to apply to get where you want is harder. In fact, it's so simple, it can be done by a computer! Back to that later.
Now, I said earlier that a formal system should ideally "represent true statements of mathematics". While giving us a watertight and way to produce theorems is one of the main reasons it's useful to us (along with being a fascinating object of study in it's own right), it isn't quite true that it's the main goal of creating an ideal formal system. There are two properties that an ideal formal system should have.
1. Consistency. Now, this is different than "truth", and there's a reason why we have this instead (and I'll explain exactly what it is in a minute). Say my formal system produces a string that, when interpreted, gives me the theorem "1+1=0". Uh-oh, we're in trouble, right? Well, sort of, but not really. After all, remember that this is simply the way in which I choose to interpret it. All I need to do is change my interpretation to fit the model of mathematics that I'm using. So, if I'm using standard arithmetic, perhaps I'm interpreting a symbol as "0" when I should interpret it as "2". Or perhaps I'm interpreting one as "=" when I should be interpreting it (at least for my purposes), as "does not equal". And so on. And when I've altered my interpretation, voila! I have a functioning formal system. But what if I have two different theorems, one of which is interpreted as "1+1=0" and the other as "1+1 does NOT equal 0"? Well, then I'm in trouble. I can differently interpret it all I want, but short of changing my interpretation of the symbol meaning "does not" (which would mess up the rules of logic itself and severely weaken my system), there's nothing I can do. No matter what I do, I'll have a contradiction. And, lest I consider simply trying to contain it, that's not just a problem for those two statements. Because of the rules of logic, an inconsistencyof this sort spreads like a cancer, because it allows the derivation of absolutely anything. Needless to say, that renders the system completely useless. Consistency means that there are no two derivable statements that are exact opposites of each other.
2. Completeness. If consistency says "I can't derive any false theorems," completeness says "I can derive every true theorem." If 1+1=2, I can derive that (or rather, a string that represents it under my interpretation). If there are infinitely many primes, I can derive that. And so on. Slightly more formally, we'd say that for every well-formed string, either it's a theorem, or it's opposite is. A formal system both consistent and complete would include all true theorems, and exclude all false ones. It's a formalist mathematician's paradise. Unfortunately, those mathematicians have to dwell in—well, not in hell, but in purgatory. Why? I'll get to that in a moment.
So the perfect formal system would be both consistent and complete. And in 1913, Alfred North Whitehead and Bertrand Russel believed that they had created that system in their three-volume leviathan of a system, Principia Mathematica. Then in came a logician called Kurt Gödel and ruined everything. Well, not exactly. He ruined everything in the manner of the polite hacker who exploits a flaw in your system, not to destroy it, but just to point out that it's there, you can't do anything about it, and you should really stop trying to use the computer. Or any computer, actually. Because Gödel's theorem doesn't just apply to Principia Mathematica; it applies to any formal system powerful enough that we could ever even think of calling it complete. It does this because of it's essential simplicity. In a nutshell, it works like this.
So here's Whitehead and Russel, making all their rules. So many rules, and so many symbols, all of which are (presumably) necessary for the system. And Gödel realized something about those symbols that Russel and Whitehead didn't: they could be represented as numbers. And that simple realization paved the path to his groundbreaking theorem. Because if symbols can be represented as numbers, the purely typographical rules can be represented as arithmetic operations. And how can we represent arithmetic operations? That's right—in a formal system! Any sufficiently powerful system can represent ITSELF. And, through a somewhat complex process (of which the details aren't particularly necessary in this discussion) Gödel constructed a string G with the following meaning: "I am not a theorem of Principia Mathematica."
Well, from there it's onto logic. Is G or is it not a theorem of Principia Mathematica, and what does that mean for the formal system? (And every other sufficiently powerful formal system as well, since Gödel's method applies to all of them.) Well, if it IS a theorem, that means it's false, because it says it's not. But that would mean that it's opposite, not-G (which states "G is a theorem of Principia Mathematica"), is true, and if our system is complete, then not-G must then be a theorem. But if G and not-G are both theorems, that means that our formal system is inconsistent. And we KNOW that it's consistent, since we built it that way. So that can't be the case.
Well, if it's NOT a theorem, that means that it IS true. But wait—how can our system be complete if that's the case? After all, not-G would be false, so it wouldn't be a theorem, and since neither G nor not-G are theorems, that means that G is undecidable—that is, neither it nor its opposite are theorems. But this is the only logically consistent option, therefore it must be true. Therefore, Principia Mathematica (along with every other formal system) is essentially incomplete.
And thus goes the life of a mathematician, for this doesn't apply exclusively to completely formal systems, but to any system that can be formalized—which is essentially every branch of mathematics. Every mathematician goes through their day knowing that there are true theorems that are forever out of their reach. One famous example is the theory that the infinity consisting of the set of all real numbers is equal to a set called Aleph-1. Georg Cantor, the father of set theory, spent his life obsessing over this, but died unable to prove it. Hilbert sought the same thing, but, unlike Cantor, he lived long enough to see that the dream of completeness was not only out of his reach, but also out of the reach of every set theorist in the future, and indeed, to humanity in general.
Does Gödel's theorem mean that formal systems are useless? Certainly not. But it means that the Holy Grail of absolute completeness is forever out of reach. Right? Well...
There's a third option, albeit one that's quite unorthodox. See, we've been assuming that not-G is false. Well, of course it is—it asserts that its opposite is a theorem! Well, more specifically, it says that its opposite is provable. And as it happens, there's a consistent way to interpret that: that there IS a proof for G, but it has infinitely many steps, so we'll never reach it. This both resolves the incompleteness problem and opens the door to a new set of numbers known as "supernatural numbers" (or "generalized natural numbers"). I'm not very familiar with them, but they're essentially various infinite numbers (not sets, which separates them from Cantor's Alephs—don't ask me what separates them from his transfinite Omegas, because I don't know).
Gödel never proved that not-G is false and/or not a theorem, but most mathematicians assume that this is the case. But what if it's not? What if not-G is provable, and we're not living in a world of shaky foundations after all? That would be a revelation that would sweep all of mathematics! But how could we find this out?
Well, standard intuitive and formal proofs aside, what do we have that the people of Gödel's time didn't? Oh, yeah. Computers. Pretty powerful ones, too. Oh, don't get me wrong. It's ridiculously unlikely that a brute-force repeated application of rules to just create more and more and more and more and more theorems would yield any fruit on this matter, simply because it would take too long due to our computers not being powerful enough. But they're getting more and more powerful every day. And if, one day, a computer programmed with Principia Mathematica, or Douglas Hofstadter's Typographical Number theory, should pop-out not-G—well, I'd say that would be a groundbreaking result well-worth the title.
(Credit for a great deal of this information goes to both Kurt Gödel, author of the famous Incompleteness Theorem, and to Douglas Hofstadter, author of the fantastic book Gödel, Escher, Bach: an Eternal Golden Braid. Go read it!)
~dlgn
I am the whirring thing past the corner. I am the darker patch under the bed. I am the tapping on your window; the extra steps on the sidewalk; the voice whispering your name. I am Stalkerbot, and I am watching you.
