So I've been reinstalled in my chateau at scenic W&M, bought most of my books, and now await only the beginning of classes. Joy.
Since I'm back early for job training, I have yet to actually see anyone. Instead, I've been hanging out with my parents for the day, and sitting around my room bored. So I figured I'd blather about what's been occupying my thoughts recently. But first, some background.
About four, maybe five years ago, I picked up this book called Gödel, Escher, Bach: An Eternal Golden Braid, written by a very sharp guy named Douglas Hofstadter. About a week ago I finished reading it. Now, before you laugh, let me explain the reason it took so long. You see, Hofstadter goes to great lengths to make his book accessible, but when you're a high school kid trying to read about propositional calculus, well, it can be pretty dry. So I ended up setting the book down to read something else for a while, and then just never picked it back up until a couple of months ago. Turns out, stuff like that is a lot easier to understand after you've spent two years taking classes that cover the same material. Go figure. So I burned through the rest of it, and let me just say, that book is the most interesting work of information synthesis I've ever seen. If you've got the determination to trundle through the boring parts, it's really worth your time.
Hofstadter talks about subjects ranging from molecular biology to music in his book, but he himself is a mathematician, and the most detailed and interesting parts of his book were the parts dealing with an important mathematical result of the last century called the Incompleteness Theorem. It was proven by Kurt Gödel, a contemporary of Einstein, and it’s the deepest and most interesting result of math I have ever learned. Here's my attempt at an explanation of what it is and why it's important: First off, I’m betting that a few people out there aren’t as huge math dorks as I am, so here’s a quick rundown of some stuff. In theoretical math, there’s a set of symbols that mathematicians use to talk about things. For example, there’s a symbol that means “There exists such a number,” and there’s one that means “For every number,” and so on and so forth. A string of these symbols is known as a string (and that’s the easiest thing you’ll ever learn about math), but of course if you just randomly throw some symbols together, the string might end up meaning something like “8 + For every number or 27.” In other words, just putting symbols together does not mean that the resulting string will have any meaning. Strings that do make sense are called statements of number theory. That’s point one: strings are strings of number-theory symbols, and statements are strings that are grammatically correct, so to speak. An example of a statement might be, “For every number a, there exists a number b such that b = a + 1,” which is an important theorem when you’re talking about natural numbers. Now, theorems are simply statements that can be proven true, and they’re what theoretical mathematicians are generally trying to discover. So the hierarchy goes: Strings > Statements > Theorms
The Incompleteness Theorem deals with statements, so I’d like to quickly tell you a few more things about those. Here's the important part: if it is possible to prove a statement true or false, then that statement is known as a decidable statement of number theory (and it’s also a theorem if it can be proven true). If it is not possible to do this, then the statement is called undecidable. Next, step back and think about the number theory system as a whole. If it is the case that every statement of number theory is decidable, then the system is called complete. Otherwise, the system is incomplete, which would mean that there is at least one well-formed, meaningful statement of number theory which is impossible to prove true or false. If you think about it for a minute, you can see that even just trying to figure out if a given statement is decidable is not necessarily going to be easy or straightforward. Consider something like this: “There exist two prime numbers such that their product is divisible by their sum.” You can try to find such a pair just by guessing, of course, but there are an infinite number of primes, and you could never exhaust all the possibilities just by guessing and checking. It certainly could be the case that there is some other clever way of approaching the problem to prove the statement true or false, but as you can see, this would be no simple thing.
Prior to this century, it was sort of tacitly assumed by most mathematicians that number theory was a complete system and that every well-formed statement was either true or false and could be proven so. This does make intuitive sense; after all, number theory is a completely theoretical construct that obeys clear, unambiguous laws that we have defined. It's entirely reasonable to assume that, if we were clever enough, we could prove the theoremhood or falsity of every statement. But, in case the name "Gödel's Incompleteness Theorem" hasn't set off any warning lights for you yet, it turns out that this is not the situation.
When mathematicians prove theorems, they do so by starting with another proven theorem, or with an axiom, and then use the rules of logic and other theorems or axioms to arrive at a new result. When people talk about 'number theory,' they're usually referring to the whole system, theorems and objects and all. The Incompleteness Theorem is different from most other theorems of number theory because of this: theorems generally say something about the properties of a certain mathematical object, as in "Two odd numbers add to an even number," "The order of any cyclic group is prime," and so on. This is not true of the Incompleteness Theorem. It states a property about the number theory system itself. What I mean is that, instead of saying something about how prime numbers work, or giving a property of a field, or something like that, the Incompleteness Theorem actually says something about the kinds of theorems that can be proven in the number theory system, and what is says is this:
Any formal axiomatic system is incomplete.
That's paraphrased, of course, since the original's in German and involves a lot of notation I can't even begin to understand, but the gist of it is right there. Number theory contains well-formed statements that can not ever be proven true or false. It's impossible to do so. Gödel managed to prove this by actually constructing such a statement. I'm not going to try to explain the details of how he did it, since I don't understand them myself very well and this is already really long. However, in a nutshell, what he did was formulate the Epimenides paradox as a statement of number theory ("This sentence is false"). This is not as easy as it seems; the crucial point of the Epimenides paradox is that the English language has very powerful self-referential capabilities, and so when he says "This sentence" we know that he means the one we are currently reading. For a long time it was not at all clear that number theory had the same capability. Gödel's genius lies in finding a way to essentially duplicate this construction within the constraints of number theory. And in doing so he created a statement which cannot be true or false, because to be either would imply it is not.
Of course, it is feasible to either adopt this statement as an axiom or reject it as a falsity and work from there, but the Gödel construction can immediately produce an equivalent statement in the new system, so trying to "patch" the hole in number theory is a fruitless exercise. What's particularly interesting about the situation is that this construction does not work on extremely simple systems. As parts of logic problems or exercises, it's very common to see systems that use a relatively small number of symbols that can be manipulated by simple rules, and such simple systems are in fact complete. They are not, however, interesting, and cannot prove any useful theorems about mathematical objects. In fact, it's been found that as soon as a formal system reaches a level of complexity that would allow it to prove useful and interesting statements, it becomes subject to the Gödel construction; it seems that having the ability to be self-referential is an essential part of such systems.
So now that I've spent God knows how long explaining this obscure bit of theoretical math, let me try to explain why it's struck me so deeply. The Incompleteness Theorem stands, in my mind, as a kind of counterpart to the Heisenberg Uncertainty Principle. Heisenberg discovered that, no matter how clever we are about it, it will not ever, ever, ever in a trillion years be possible for us to precisely measure things down on an atomic level. There's always going to be a bit of uncertainty in any measurements we make, which means that the physical world we live in will always remain a basically unpredictable and wonderfully surprising place. And it turns out that the same sort of thing is true in math. Even in a system which exists only abstractly and can be divorced from any real or practical basis, even in a system that has been entirely defined by our minds and operates strictly according to our rules, its behavior is not entirely predictable. Despite the rigidity of its definition, such a system still holds surprises, and we can never achieve perfect knowledge of it, just as we can never achieve perfect knowledge of the physical world.
The Incompleteness Theorem demonstrates that no matter how far our civilization advances, there will always be holes in our understanding. As long as our race continues to think, there will be things to discover.
