Издательство Cambridge University Press, 2005, -173 pp.
In 1931, the young Kurt G?del published his First and Second Incompleteness Theorems; very often, these are simply referred to as ‘G?del’s Theorems’. His startling results settled (or at least, seemed to settle) some of the crucial questions of the day conceing the foundations of mathematics. They remain of the greatest significance for the philosophy of mathematics – though just what that significance is continues to be debated. It has also frequently been claimed that G?del’s Theorems have a much wider impact on very general issues about language, truth and the mind. This book gives outline proofs of the Theorems, puts them in a more general formal context, and discusses their implications. I originally intended to write a shorter book, leaving rather more of the formal details to be filled in from elsewhere. But while that plan might have suited some readers, I very soon decided that it would seriously irritate others to be sent hither and thither to consult a variety of text books with different terminology and different notations. So in the end, I have given more or less fully worked out proofs of most key results.
However, my original plan still shows through in two ways. First, some proofs are only sketched in, and some other proofs are still omitted entirely. Second, I try to make it plain which of the proofs I do give can be skipped without too much loss of understanding. My overall aim – rather as in a good lecture course with accompanying hand-outs – is to highlight as clearly as I can the key formal results and proof-strategies, provide details when these are important enough, and give references where more can be found.1 Later in the book, I range over a number of intriguing formal themes and variations that take us a little beyond the content of most introductory texts.
As we go through, there is also an amount of broadly philosophical commentary. I follow G?del in believing that our formal investigations and our general reflections on foundational matters should illuminate and guide each other. So I hope that the more philosophical discussions (though certainly not uncontentious) will be reasonably accessible to any thoughtful mathematician. Likewise, most of the formal parts of the book should be accessible even if you start from a relatively modest background in logic.2 Though don’t worry if you find yourself skimming to the ends of proofs – marked ‘?’ – on a first reading: I do that all the time when tackling a new mathematics text.
Writing a book like this presents a problem of organization. For example, at various points we will need to call upon some background ideas from general logical theory. Do we explain them all at once, up front? Or do we introduce them as we go along, when needed? Another example: we will also need to call upon some ideas from the general theory of computation – we will make use of both the notion of a ‘primitive recursive function’ and the more general notion of a ‘recursive function’. Again, do we explain these together? Or do we give the explanations many chapters apart, when the respective notions first get put to work?
I’ve adopted the second policy, introducing new ideas as and when needed. This has its costs, but I think that there is a major compensating benefit, namely that the way the book is organized makes it a lot clearer just what depends on what. It also reflects something of the historical order in which ideas emerged (a little more of the history emerges in footnotes).
What G?del’s First Theorem Says
The Idea of an Axiomatized Formal Theory
Capturing Numerical Properties
Sufficiently Strong Arithmetics
Three Formalized Arithmetics
Primitive Recursive Functions
More on Functions and P.R. Adequacy
G?del’s Proof: The Headlines
Q is P.R. Adequate
The Arithmetization of Syntax
The First Incompleteness Theorem
Extending G?del’s First Theorem
The Second Incompleteness Theorem
?-Recursive and Partial Recursive Functions
Turing Machines
Turing Computability and Recursiveness
Universal Turing Machines
In 1931, the young Kurt G?del published his First and Second Incompleteness Theorems; very often, these are simply referred to as ‘G?del’s Theorems’. His startling results settled (or at least, seemed to settle) some of the crucial questions of the day conceing the foundations of mathematics. They remain of the greatest significance for the philosophy of mathematics – though just what that significance is continues to be debated. It has also frequently been claimed that G?del’s Theorems have a much wider impact on very general issues about language, truth and the mind. This book gives outline proofs of the Theorems, puts them in a more general formal context, and discusses their implications. I originally intended to write a shorter book, leaving rather more of the formal details to be filled in from elsewhere. But while that plan might have suited some readers, I very soon decided that it would seriously irritate others to be sent hither and thither to consult a variety of text books with different terminology and different notations. So in the end, I have given more or less fully worked out proofs of most key results.
However, my original plan still shows through in two ways. First, some proofs are only sketched in, and some other proofs are still omitted entirely. Second, I try to make it plain which of the proofs I do give can be skipped without too much loss of understanding. My overall aim – rather as in a good lecture course with accompanying hand-outs – is to highlight as clearly as I can the key formal results and proof-strategies, provide details when these are important enough, and give references where more can be found.1 Later in the book, I range over a number of intriguing formal themes and variations that take us a little beyond the content of most introductory texts.
As we go through, there is also an amount of broadly philosophical commentary. I follow G?del in believing that our formal investigations and our general reflections on foundational matters should illuminate and guide each other. So I hope that the more philosophical discussions (though certainly not uncontentious) will be reasonably accessible to any thoughtful mathematician. Likewise, most of the formal parts of the book should be accessible even if you start from a relatively modest background in logic.2 Though don’t worry if you find yourself skimming to the ends of proofs – marked ‘?’ – on a first reading: I do that all the time when tackling a new mathematics text.
Writing a book like this presents a problem of organization. For example, at various points we will need to call upon some background ideas from general logical theory. Do we explain them all at once, up front? Or do we introduce them as we go along, when needed? Another example: we will also need to call upon some ideas from the general theory of computation – we will make use of both the notion of a ‘primitive recursive function’ and the more general notion of a ‘recursive function’. Again, do we explain these together? Or do we give the explanations many chapters apart, when the respective notions first get put to work?
I’ve adopted the second policy, introducing new ideas as and when needed. This has its costs, but I think that there is a major compensating benefit, namely that the way the book is organized makes it a lot clearer just what depends on what. It also reflects something of the historical order in which ideas emerged (a little more of the history emerges in footnotes).
What G?del’s First Theorem Says
The Idea of an Axiomatized Formal Theory
Capturing Numerical Properties
Sufficiently Strong Arithmetics
Three Formalized Arithmetics
Primitive Recursive Functions
More on Functions and P.R. Adequacy
G?del’s Proof: The Headlines
Q is P.R. Adequate
The Arithmetization of Syntax
The First Incompleteness Theorem
Extending G?del’s First Theorem
The Second Incompleteness Theorem
?-Recursive and Partial Recursive Functions
Turing Machines
Turing Computability and Recursiveness
Universal Turing Machines