Missing Things

29 March 2010

Waiting for Gödel


This is the part where things start getting complicated, because set theory can, in fact, be defined in terms of itself. You see, any mathematical theory can be defined as a set of statements - some of which are unproven and assumed, and called axioms, and others of which are called theorems because they are implied by the axioms.

For example: The axioms of the basic arithmetic we all learn in school are as follows.
- Every number is equal to itself. If one number is equal to a second number, that number must be equal to the first. If a third number is equal to the second, it must also be equal to the first. But only a number can be equal to a number. (Equality defined!)
- 0 is a "natural" number, and adding one to any natural number yields another natural number. (Addition permitted!)
- If you have two numbers and add one to both of them, and get the same result, the two numbers must themselves be equal. (Subtraction permitted!)
- If you define some set of numbers such that if it contains some natural number then it must also contain that number plus one, and define it to contain 0, then that set contains all natural numbers. (The principle of induction!)

Arithmetic theorems include 1+1=2; 1+2=3; 2+2=4; and so on. It should be clear that there are an infinite number of these, even though there are some distinct limits - this arithmetic system doesn't even allow for multiplication yet, let alone fractions, irrational numbers, negatives, and more complicated ideas! But such concepts can be incorporated, by adding more axioms to get a larger system that still contains arithmetic.

For centuries, mathematicians have held two dreams. On the one hand, that it would be eventually possible to extend arithmetic logic - that is, the logic that underlies how we experience the universe on an everyday basis - to the point that it would contain all possible true statements. The day was dreamed of when two philosophers in a dispute would, instead of saying "let us argue", would say "let us calculate"; and then sit down and work out the equations underlying the properties of the soul, or the top quark, or God - a system both eminently powerful, and eminently practical.

On the other hand, there was the fear that mathematics is itself broken in some way, that one day someone would calculate some grotesque and immense equation, prove it true beyond all possible doubt or inherent limitation, and then realize that you could apply it in such away that 0=1. A waste of millennia of research and imagination and rigor, and the seed of a potential existential crisis among the entirety of the sciences and philosophies, which rely so heavily on the idea that human reason can understand the cosmos to begin with.

The dream and the nightmare are fundamentally in opposition to each other, and either would precipitate a tremendous shift in human understanding.
And Kurt Godel was the man who proved both were impossible.

The First Incompleteness Theorem: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.

In simpler terms, any theory that includes the axioms discussed above - which we know to be true - either contains false statements, or it excludes true statements.

Let me repeat that. If a theory can be made to contain all truth, then it also contains at least one statement that's false. If you can fix it to kick out that one statement, you also have to kick out at least one statement that's true.

This is the strongest argument for agnosticism that could ever possibly be made, and it is provably true based on everything we understand about logic and mathematics. And if you think that's bad, it gets worse.

The Second Incompleteness Theorem: For any formal effectively generated theory T including basic arithmetical truths, and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.

That is, one of those statements you can never prove is that you're right. And if your theory can prove that all the statements it implies are true, they aren't.

Funny thing is, we can still define the "universal set" of all statements that are true. There's just no theory that can tell us what all those statements are. Sure, we can identify a "Godelian statement" for every theory we come up with, and add an axiom to the theory to account for it. We can splice a couple of mutually-cohesive theories together to cover even more ground. But these just make a bigger theory, and we already proved every consistent theory has a true statement outside it. We can make infinite theories, but the thing about eternity is, there's always more of it.

We can mark off a section of the Library of Babel that contains all the books we can prove to be true, but there's always another secret just beyond the horizon and we'll have to fight through a bunch of lies to get to it - and if you should find a lie in your own head, well, you'll have to throw it out, with all the ones relying on it that you thought you'd already proven.

Sound perilous? If you care about what you think, it's the only choice you've got. The quest for knowledge is an unending struggle against infinite odds. Besides, they say an inconvenience is only an adventure wrongly considered.

Bring me that horizon.

25 March 2010

I am being lax

At this rate, I might as well change my name to "Once a Month".

Not done explaining Godel yet, sorry. But I highly encourage you to go check out this essay, as it is pretty awesome.