Monday, August 08, 2005

The Use and Abuse of Godel's Theorem

I just finished a first reading of Gödel's Theorem: An Incomplete Guide to its Use and Abuse by Torkel Franzén.

Gödel's theorem has a habit of appearing in all sorts of literature. Hofstadter makes it a central part of his discussion of AI in the classic Gödel, Escher, Bach. Penrose uses it to argue for the specialness of human brains. Chaitin uses it as part of various discussions about irreducible complexity. It has been invoked by theologists and literary critics. And yet, it's hard to find work on Gödel's theorem that deals with these issues and yet is written by a logician with a good grasp of the subject. This book fills that gap. It looks closely at the various ways people have abused the theorem. And I say 'abused' because all of the extra-mathematical accounts he quote are abuses.

One of the ways in which the theorem is abused is the way it is applied to all kinds of formal and non-formal systems regardless of applicability. Gödel's theorem is explicitly about formal systems that are capable of formalizing 'part of arithmetic'. It's not about complexity. As Franzén points out, there are very complex systems that are incapable of being used for arithmetic and yet there are also some very simple systems that can be used for it. Additionally, Gödel's thoerem deals only with the arithmetic component of such systems. For example if we find a way to axiomatise physics it is likely we will be able to use some of those axioms for doing arithmetic. As a result the entire system will be incomplete. Freeman Dyson has been using this to argue that physics is 'inexhaustible'. But the incompleteness might only be a feature of the arithmetic part of this system and have nothing to do with the physical part. Interestingly Dyson conceded this point when it was raised by Solomon Feferman in the New York Review of Books.

Franzén makes some very simple statements that show the falsity of some of the claims made about the theorem. For example if G is undecidable in formal system P then clearly it can be proved in P+G. So statements like "Godel's theorem demonstrates the existence of unprovable propositions" that abound in the literature are shown to be trivially false. He similarly dismisses some statements about the complexity of axiom systems made by Gregory Chaitin. Chaitin has done some great work, in particular he has a beautiful proof of Gödel's theorem using Kolmogorov complexity. But a quick visit to his web site reveals that he has a slight problem with understanding the importance of his own work. Franzén does a great job of trying to understand which parts of Chaitin's work really are significant.

Importantly Franzén is pedantic in just the right measure. When working in logic it is important to be clear about details. For example it's easy to make mistakes keeping track of which formal systems we have used to prove which results and we often need to make clear whether we use the word 'proof' to mean a string of symbols or something that convinces a mathematician (or both). But Franzén also understands that many people use Gödel's theorem, not literally, but as a metaphor or inspiration in other fields.

Franzén also devotes a good amount of space to the issue of Gödel's theorem and mathematical skepticism. He shows that the theorem can do nothing to help skeptical arguments. After all, if a formal system were able to prove its own consistency would we trust it more?

There's a reason why I mention "first reading" above. Among the statements about Gödel's theorem that Franzén dismantles are statements that I myself have been making [1]. So I now feel less confident of my understanding of the theorem than before I started the book. This is definitely not an easy book for non-specialists who really want to make sure they understand every statement made in it and it is going to require repeated readings. But any book that I immediately want to reread on completing it can't be all that bad.

[1] I've always understood Gödel's theorem as requiring a step outside of the formal system in which we interpret the symbols of a formal system as a tool for making predictions about what happens when we manipulate symbols, allowing us to turn a formal system in on itself. Franzén explicitly argues that this view is incorrect. This has left me a littlle confused.

No comments:

Blog Archive