I have a very contrarian take on Gödel’s Incompleteness Theorem, which is that it’s widely misunderstood, most things people conclude from it are false, and it’s actually largely irrelevant. This is why I was excited to read a review of this book I’ve heard so much fuss about, to see if it would change my mind.
Well, it didn’t. Sam himself doesn’t think the second half of the book (where we talk about conclusions) is all that strong, and I agree. So as an exploration of what to do with the theorem, this review isn’t that useful; it’s more of a negative example. But, as a distillation (of both the theorem and its proof), it’s quite good. Sam manages to simplify the formalism significantly while leaving all the core ideas intact, and with math this complex, that’s not easy. I don’t know how much of the credit should go to Sam vs. the book, but either way, the result is excellent. In the future, this post will be the first thing I’ll recommend for people who want to understand the theorem.
However, as-is, my recommendation will come with one caveat. Sam acknowledges that Truth is relative to interpretation whereas Provability is not, but he doesn’t quite spell out what that means. Namely, given an arbitrary sentence S in a formal language, if S isn’t provable (and hence the language is incomplete), that’s always a good thing—because it means S is false under at least one interpretation. If S were provable, that would be a disaster! It would violate soundness and thus make the entire thing useless. Hence I think this sentence:
A formal system which is able to prove all of its truths is called “complete.” So Gödel’s theorem says that every sufficiently rich formal system is incomplete – there will always be unprovable truths.
is misleading because the “unprovable truths” are only sometimes true, which means they better not be provable! This is precisely the point that I think leads to people misjudging the theorem’s importance, and it’s my only real gripe with this post.
I have a very contrarian take on Gödel’s Incompleteness Theorem, which is that it’s widely misunderstood, most things people conclude from it are false
This might be a contrarian position here. I’m not sure (I don’t fully understand what Eliezer said in his posts about it).
About your caveat, I don’t understand it, and would like to. I don’t really know how to articulate my confusion about it though.. If you can elaborate or explain it differently I’d be glad.
Ok, here’s an attempt. There are formal languages. They have many interpretations. You can add axioms to reduce the number of interpretations (as in, if you only count those that make all axioms true). If you add enough, there’s only one interpretation left. This is always possible, but it may require an uncomputable set of axioms. In fact, there’s a result which we could call the difficulty-of-restricting-interpretations-with-axioms-theorem that says that some languages always require uncomputable sets of axioms.
Put like this, it sounds like a pretty boring result, at least to me. But everything about the above description is accurate! The “Incompleteness” theorem is just a result about how many axioms you need to restrict the set of interpretations. Maybe there is a reason why this is important, but the post doesn’t explain this, and I maintain that the sentence “there will always be unprovable truths” (which was the sentence I complained about) is heavily misleading. It’s like a language trick; it sounds impressive because we usually think of truth as being absolute, but here it’s relative. If we did use truth as being absolute (i.e., only call sentences true that are true under every interpretation), the claim is false; in fact, then every true statement is provable—that’s Gödel’s Completeness Theorem.
I have a very contrarian take on Gödel’s Incompleteness Theorem, which is that it’s widely misunderstood, most things people conclude from it are false, and it’s actually largely irrelevant. This is why I was excited to read a review of this book I’ve heard so much fuss about, to see if it would change my mind.
Well, it didn’t. Sam himself doesn’t think the second half of the book (where we talk about conclusions) is all that strong, and I agree. So as an exploration of what to do with the theorem, this review isn’t that useful; it’s more of a negative example. But, as a distillation (of both the theorem and its proof), it’s quite good. Sam manages to simplify the formalism significantly while leaving all the core ideas intact, and with math this complex, that’s not easy. I don’t know how much of the credit should go to Sam vs. the book, but either way, the result is excellent. In the future, this post will be the first thing I’ll recommend for people who want to understand the theorem.
However, as-is, my recommendation will come with one caveat. Sam acknowledges that Truth is relative to interpretation whereas Provability is not, but he doesn’t quite spell out what that means. Namely, given an arbitrary sentence S in a formal language, if S isn’t provable (and hence the language is incomplete), that’s always a good thing—because it means S is false under at least one interpretation. If S were provable, that would be a disaster! It would violate soundness and thus make the entire thing useless. Hence I think this sentence:
is misleading because the “unprovable truths” are only sometimes true, which means they better not be provable! This is precisely the point that I think leads to people misjudging the theorem’s importance, and it’s my only real gripe with this post.
That’s not very contrarian on LessWrong. This point has been made a lot, including by Eliezer in Highly Advanced Epistemology 101 for Beginners
This might be a contrarian position here. I’m not sure (I don’t fully understand what Eliezer said in his posts about it).
About your caveat, I don’t understand it, and would like to. I don’t really know how to articulate my confusion about it though.. If you can elaborate or explain it differently I’d be glad.
Ok, here’s an attempt. There are formal languages. They have many interpretations. You can add axioms to reduce the number of interpretations (as in, if you only count those that make all axioms true). If you add enough, there’s only one interpretation left. This is always possible, but it may require an uncomputable set of axioms. In fact, there’s a result which we could call the difficulty-of-restricting-interpretations-with-axioms-theorem that says that some languages always require uncomputable sets of axioms.
Put like this, it sounds like a pretty boring result, at least to me. But everything about the above description is accurate! The “Incompleteness” theorem is just a result about how many axioms you need to restrict the set of interpretations. Maybe there is a reason why this is important, but the post doesn’t explain this, and I maintain that the sentence “there will always be unprovable truths” (which was the sentence I complained about) is heavily misleading. It’s like a language trick; it sounds impressive because we usually think of truth as being absolute, but here it’s relative. If we did use truth as being absolute (i.e., only call sentences true that are true under every interpretation), the claim is false; in fact, then every true statement is provable—that’s Gödel’s Completeness Theorem.