I recently finished Rebecca Goldstein's book "Incompleteness: The Proof and Paradox of Kurt Gödel" (Swedish translation (which I read): "Ofullständighet: Kurt Gödels bevis och paradox"). For those of you who aren't familiar with Gödel (I hardly was before I read this book), he was a logician, by many people though of as the greatest thinker of the last century along with Albert Einstein. This book tries to explain why, but often gets stuck in its vivid description of this somewhat strange and esoteric character. The fact that Kurt Gödel died of malnutrition due to paranoid delusions maybe explains why there's a lot of intresting anecdotes about this strange man well worth brought up, but it sometimes feel that the author is more excited about Gödels odd life than what he actually accomplished. With that said, the book is, in my opinion, a great and captivating introduction to his work.
The fact that everything isn't centered on hard scientific facts all the time makes this book a pretty easy and convenient read. More speculative philosophical discussions are blended with stories of Gödels life and his own ideas in respect to his logical claims. In the middle, there is a pretty technical, although pretty talkative, presentation of the work that made him almost immortal. The reader who wishes to really dig down into Gödels theorems - and at the same time spare oneself from those vauge discussions on different implications of it - will probably be pretty disapointed by this book though. However, if you know that you wouldn't last more than a couple of pages reading a book filled page up and page down with stringent logical arrangements, but still wants to grasp the main idea about Gödels theorems, look no further. This book will probably get you intrested enough to go on to the last page.
The fascinating thing about this book is how it's almost structured as good detective story. In the beginning, intresting implications of Gödels work is suggested, and when your half way through the book, you could recite all the passages about how great and novel his theorems was, without having read a single conclusive description about it. Sort of like this review.
Well, I feel I can't publish this post without at least taking a shot at trying to explain what Gödel's pioneering results were. This attempt, sprung from my megalomania, shouldn't be taken too seriously though. Ok, here we go.
Gödels proof of incompletness is really based on the old liar paradox. It goes something like this (there's countless different versions of it):
If you look at it, it soon becomes clear why it's a paradox. If the sentence is false as it claims, the statement that it's false is true, which makes the sentence true and hence contradicts itself. If the sentence is true then the statement that it's false isn't true, hence the sentence is false, which contradicts the fact that we said that is was true. As you can see, it becomes pretty complex, but the main idea should be pretty easy to grasp.
What Gödel does is to expand this paradox into the domain of mathematics. First, he construct a system, that translates logical statements to aritmetic statements. In this way, he can represent every logical statement with a specific number. Let's say for example that the statement "If A then B" in this system is represented by 10230. It doesn't really matter what the actual system is (although If it did, I couldn't give an account of it) but the important part is this. What is demanded from the system is that it is isomorphic with standard logic (which Gödel, a couple of years before his incompleteness theorem, prooved was complete). What this means is that there have to be a given set of rules to combine different numbers, depending on what rellation you want them to have to eachother, so that the output produces the correct logical statement. Let me try to illustrate this (since I don't know Gödels system, and since I don't really think I have the time nor the knowledge to create a coherent one myself, you have to ignore that this example is taking some liberties).
Let's say I want to make this series of statements (this is a so called syllogism):
(A) If A then B.
(B) A is true.
-----------------
(C) B is true.
Let's say that (A)=1, (B)=2 and (C)=3 after the translation. What we now want to do is to find some rule that we can use whenever we have two statements and want to know what the consequenses of those statements are. Well, in this example it's pretty easy. 1+2=3. So let's say that plus holds that function. The trick with Gödels system is to work out something that always is interchangeable with simple logic. In this case, you could clearly see that my model doesn't get very far. Let's try to state:
(A) If A then B.
(A) If A then B.
What's the result? 1+1=2. In other words:
(A) If A then B.
(A) If A then B.
-----------------
(B) A is true.
Hopefully not true. Well, let's move on.
Why did Gödel go through all this fuzz then? Well, his goal was to create an aritmetic system that could make claims about itself. If you can represent every logical statement with a number, then you can say something about the aritmetic system and then translate it into a number being part of an aritmetic system, hence make it say something about itself. It's almost like if you, everytime you said something about a pig, was turned in to one, and therefore said something about yourself (anyone who's ever been told by a parent that he or she eats like a pig, and witty responded that pigs usually have pigs for parents, know what I mean).
So, what's the point of doing this then (we're soon home free)? Well, this takes us back to the liars paradox. The reason why it is so effective is that it says something about itself. "This statement is false" get problematic because it refers back to itself, creating somewhat of an infinate loop (Yes, I'll get to "Gödel, Escher, Bach" in future posts).
Gödel now make this statement:
He then translates this statement into a number and get something like, well, let's say:
Yes, I just made that up. What the numbers above now is saying is this:
So, what follows of all this? Well, when we construct a formal system, we don't want it to be able to contradict itself. That's really the worst thing that can happend. We can't have a system that says that 1+1 is 1 and that 1+1 is 2. That would mean that 1=2, which would make it possible to prove any kind of statement. 3+3=8? Sure.
Since 1 and 2 are interchangeable at the same time as they have different meaning, we can prove whatever we want. We can't have that. Our only option is to accept the other outcome. There are true statements in formal systems capable of aritmetics that can't be proven. This made a huge impact on the mathematical world (to the extent that mathematicans were willing to accept it) when Gödel presented it in the the 30's. Untill then, the general idea was that every true statement in mathematics could be proved. That was by many though of the very analytic meaning of true. That it could be proven. Gödel showed that that wasn't the case.
Gödel's incompletness theorem spawns a lot of different implications in respect to how you choose to see it. From platonism to conscioussness, people have tried to apply Gödels famous work in a lot of different areas. I'll definitly come back to this topic in the future, but this will be all for now.
If anyone have any objections against how I've presented Gödels incompletness theorem, please tell me. I'm eager to improve.
For a kind of halfly vauge parallel to Gödels theorem, see my post titled "The epistemology of consciousness". What I try illustrate there is a (hypotetic) true statement that cannot be proved, although this one is not within a formal system. In you are a sceptic, you could come up with countless of examples of situations were this holds. I'll get to this too in due time.
The fact that everything isn't centered on hard scientific facts all the time makes this book a pretty easy and convenient read. More speculative philosophical discussions are blended with stories of Gödels life and his own ideas in respect to his logical claims. In the middle, there is a pretty technical, although pretty talkative, presentation of the work that made him almost immortal. The reader who wishes to really dig down into Gödels theorems - and at the same time spare oneself from those vauge discussions on different implications of it - will probably be pretty disapointed by this book though. However, if you know that you wouldn't last more than a couple of pages reading a book filled page up and page down with stringent logical arrangements, but still wants to grasp the main idea about Gödels theorems, look no further. This book will probably get you intrested enough to go on to the last page.
The fascinating thing about this book is how it's almost structured as good detective story. In the beginning, intresting implications of Gödels work is suggested, and when your half way through the book, you could recite all the passages about how great and novel his theorems was, without having read a single conclusive description about it. Sort of like this review.
***
Well, I feel I can't publish this post without at least taking a shot at trying to explain what Gödel's pioneering results were. This attempt, sprung from my megalomania, shouldn't be taken too seriously though. Ok, here we go.
Gödels proof of incompletness is really based on the old liar paradox. It goes something like this (there's countless different versions of it):
This sentence is false.
If you look at it, it soon becomes clear why it's a paradox. If the sentence is false as it claims, the statement that it's false is true, which makes the sentence true and hence contradicts itself. If the sentence is true then the statement that it's false isn't true, hence the sentence is false, which contradicts the fact that we said that is was true. As you can see, it becomes pretty complex, but the main idea should be pretty easy to grasp.
What Gödel does is to expand this paradox into the domain of mathematics. First, he construct a system, that translates logical statements to aritmetic statements. In this way, he can represent every logical statement with a specific number. Let's say for example that the statement "If A then B" in this system is represented by 10230. It doesn't really matter what the actual system is (although If it did, I couldn't give an account of it) but the important part is this. What is demanded from the system is that it is isomorphic with standard logic (which Gödel, a couple of years before his incompleteness theorem, prooved was complete). What this means is that there have to be a given set of rules to combine different numbers, depending on what rellation you want them to have to eachother, so that the output produces the correct logical statement. Let me try to illustrate this (since I don't know Gödels system, and since I don't really think I have the time nor the knowledge to create a coherent one myself, you have to ignore that this example is taking some liberties).
Let's say I want to make this series of statements (this is a so called syllogism):
(A) If A then B.
(B) A is true.
-----------------
(C) B is true.
Let's say that (A)=1, (B)=2 and (C)=3 after the translation. What we now want to do is to find some rule that we can use whenever we have two statements and want to know what the consequenses of those statements are. Well, in this example it's pretty easy. 1+2=3. So let's say that plus holds that function. The trick with Gödels system is to work out something that always is interchangeable with simple logic. In this case, you could clearly see that my model doesn't get very far. Let's try to state:
(A) If A then B.
(A) If A then B.
What's the result? 1+1=2. In other words:
(A) If A then B.
(A) If A then B.
-----------------
(B) A is true.
Hopefully not true. Well, let's move on.
Why did Gödel go through all this fuzz then? Well, his goal was to create an aritmetic system that could make claims about itself. If you can represent every logical statement with a number, then you can say something about the aritmetic system and then translate it into a number being part of an aritmetic system, hence make it say something about itself. It's almost like if you, everytime you said something about a pig, was turned in to one, and therefore said something about yourself (anyone who's ever been told by a parent that he or she eats like a pig, and witty responded that pigs usually have pigs for parents, know what I mean).
So, what's the point of doing this then (we're soon home free)? Well, this takes us back to the liars paradox. The reason why it is so effective is that it says something about itself. "This statement is false" get problematic because it refers back to itself, creating somewhat of an infinate loop (Yes, I'll get to "Gödel, Escher, Bach" in future posts).
Gödel now make this statement:
This statement is impossible to prove in an formal system capable of aritmetics.
He then translates this statement into a number and get something like, well, let's say:
52352359875239823987609238765987234987587237865982309589723
Yes, I just made that up. What the numbers above now is saying is this:
This statement is impossible to prove in a formal system capable of aritmetics (and this is a statement in a formal system capable of aritmetics).
What this statements says, given that it's true, is that there is true statements within a formal system capable of aritmetic, that still are impossible to prove. And what it says given that it's false, is that it actually can be proven. But since the statement is false, it could possible be proven, hence we have a contradiction.So, what follows of all this? Well, when we construct a formal system, we don't want it to be able to contradict itself. That's really the worst thing that can happend. We can't have a system that says that 1+1 is 1 and that 1+1 is 2. That would mean that 1=2, which would make it possible to prove any kind of statement. 3+3=8? Sure.
1+1+1=3--->3*2+2=8--->3*1+2=8--->3*1+2+1-1=8--->
3+2+2-1=8--->3+2+1=8--->3+3=8
3+2+2-1=8--->3+2+1=8--->3+3=8
Since 1 and 2 are interchangeable at the same time as they have different meaning, we can prove whatever we want. We can't have that. Our only option is to accept the other outcome. There are true statements in formal systems capable of aritmetics that can't be proven. This made a huge impact on the mathematical world (to the extent that mathematicans were willing to accept it) when Gödel presented it in the the 30's. Untill then, the general idea was that every true statement in mathematics could be proved. That was by many though of the very analytic meaning of true. That it could be proven. Gödel showed that that wasn't the case.
***
Gödel's incompletness theorem spawns a lot of different implications in respect to how you choose to see it. From platonism to conscioussness, people have tried to apply Gödels famous work in a lot of different areas. I'll definitly come back to this topic in the future, but this will be all for now.
If anyone have any objections against how I've presented Gödels incompletness theorem, please tell me. I'm eager to improve.
For a kind of halfly vauge parallel to Gödels theorem, see my post titled "The epistemology of consciousness". What I try illustrate there is a (hypotetic) true statement that cannot be proved, although this one is not within a formal system. In you are a sceptic, you could come up with countless of examples of situations were this holds. I'll get to this too in due time.
2 comments:
hi~what a beautiful blog, a lot of usefull info here, i will be back soon to see what new update
Hi gns2!
Fun to hear that you like it. Stay tuned for more :)
Post a Comment