Monday, April 21, 2008
Godel's Proof
I somewhat randomly read Godel's Proof by Ernest Nagel and James Newman. It's a short book trying to explain Godel's Proof to non-math majors. Since the book sort of speeds through things in 100 pages it is tough to summarize in a blog post. But basically some people wanted to be able to take a set of axioms about number theory and using formal mathematics be able to prove if the axioms are consistent (can't derive two theorems that contradict each other) and complete (there are no true theorems within the system that cannot be derived from the axioms). Godel proved that this cannot be done. So in some sense he proved that there are some statements that cannot be proved true or false (before anyone tries to apply this too generally - it only applies to a somewhat specific set of circumstances - but even so was quite revolutionary for mathematics). I think the proof looks a lot like the halting problem from computer science (although I'm sure there's some subtle difference that would cause a mathematician to scream) - or more generally it's kinda sorta "if you can prove this statement is true then it is false and if you can prove it is false then it is true, but if you can't prove it either way then it is true". One major aspect of the proof that I find really cool is how he turns logic into math. You can take logical statements and turn them into logic symbols. Well you assign a number to each symbol then you can create a rule to combine those values to get a unique number for each statement. You can then extend the rule so you get a unique number for each series of statements. Then you can perform arithmetic on logic statements. This is the tool Godel used to create the statement which cannot be proved true or false.
Subscribe to:
Post Comments (Atom)
1 comment:
Wireless still boggles my mind. Like the first time someone told me about wireless speakers back in 2006, I was like "no waaaaay! unreeeaaaaal!"
And then there's the whole connection between math and the physical, like the way the standard model of particles was completed- the existence of some of the particles was predicted using symmetry/group theory. Plato was a kook with his worship of numbers, but he understood what the writer of that article and so many others who blow off science as cold or too stamped with realism don't. Even in the 21st century, though, we get kind of a Plato-like manicness going on with the whole numbers thing:
http://arxiv.org/abs/0704.0646
in it, he- astrophysicist Max Tegmark- argues "that our physical world is an abstract mathematical structure"
Who knows??? And they say modern science has no imagination!
That's cool that you read this book! I've only ever read about the proof and not the proof itself.
Post a Comment