A layman's guide to the mechanics of Gödel's proof together with a lucid discussion of the issues which it raises. Includes an essay discussing the significance of Gödel's work in the light of Wittgenstein's criticisms.

A layman's guide to the mechanics of Gödel's proof together with a lucid discussion of the issues which it raises. Includes an essay discussing the significance of Gödel's work in the light of Wittgenstein's criticisms.

Gödel's Theorem is often used in arguments against machine intelligence, suggesting humans are not bound by the rules of any formal system. However, Gödelian arguments can be used to support AI, provided we extend our notion of computation to include devices incorporating random number generators. A complete description scheme can be given for integer functions, by which nonalgorithmic functions are shown to be partly random. Not being restricted to algorithms can be accounted for by the availability of an arbitrary random (...) function. Humans, then, might not be rule-bound, but Gödelian arguments also suggest how the relevant sort of nonalgorithmicity may be trivially made available to machines. (shrink)

In his paper on the incompleteness theorems, Gödel seemed to say that a direct way of constructing a formula that says of itself that it is unprovable might involve a faulty circularity. In this note, it is proved that ‘direct’ self-reference can actually be used to prove his result.

In 1931, the young Kurt Gödel published his First Incompleteness Theorem, which tells us that, for any sufficiently rich theory of arithmetic, there are some arithmetical truths the theory cannot prove. This remarkable result is among the most intriguing in logic. Gödel also outlined an equally significant Second Incompleteness Theorem. How are these Theorems established, and why do they matter? Peter Smith answers these questions by presenting an unusual variety of proofs for the First Theorem, showing how to prove the (...) Second Theorem, and exploring a family of related results. The formal explanations are interwoven with discussions of the wider significance of the two Theorems. This book will be accessible to philosophy students with a limited formal background. It is equally suitable for mathematics students taking a first course in mathematical logic. (shrink)

This paper discusses lower bounds for proof length, especially as measured by number of steps (inferences). We give the first publicly known proof of Gödel's claim that there is superrecursive (in fact. unbounded) proof speedup of (i + 1)st-order arithmetic over ith-order arithmetic, where arithmetic is formalized in Hilbert-style calculi with + and · as function symbols or with the language of PRA. The same results are established for any weakly schematic formalization of higher-order logic: this allows all tautologies as (...) axioms and allows all generalizations of axioms as axioms. Our first proof of Gödel's claim is based on self-referential sentences: we give a second proof that avoids the use of self-reference based loosely on a method of Statman. (shrink)

G¨odel’s a theorem concerns an arithmetical statement and the truth of this statement does not depend on self-reference; nevertheless its interpretation is of tremendous interest. G¨odel’s theorem allows one to conclude that formal arithmetic is not axiomatizable. But there is another very interesting logico-philosophical result: the possibility of a statement to exist such that it is improvable in the object-theory and at the same time its truth is provable in the metatheory. It seems that in the real history G¨odel’s theorem (...) was absolutely unexpected, and even in retrospect, now it is difficult to point out logico-philosophical reasons for the above possibility. In my opinion though it was still conceivable at that time, but unfortunately the philosophers and logicians missed to notice it. In the terms of recursive arithmetic Hilbert’s programme can be formulated as follows: Build a decidable, complete, consistent logical system such that the class of derivable statements coincides with the class of the mathematical statements which are intuitively true; prove this equivalence by means of an arithmetization of the theory in the framework of the recursive arithmetic! Now, if the system is so strong as to admit the construction of the classical mathematics, then in particular it will contain the classical arithmetic. But Hilbert’s requirements reduce to a proof with the means of the recursive arithmetic, by arithmetization. So, on one hand the system will contain the arithmetic and, on the other hand it will be expressible in it, in order words the system will include its own syntax, as well as its own semantics. Now it is clear that Hilbert’s programme contains a possibility of a situation similar to some well known semantic antinomies, situations of self-reference. (shrink)

Here’s one version G¨ odel’s 1931 First Incompleteness Theorem: If T is a nice, sound theory of arithmetic, then it is incomplete, i.e. there are arithmetical sentences ϕ such that T proves neither ϕ nor ¬ϕ. There are three things here to explain straight away.

This short book has two main purposes. The first is to explain Kurt Gödel's first and second incompleteness theorems in informal terms accessible to a layperson, or at least a non-logician. The author claims that, to follow this part of the book, a reader need only be familiar with the mathematics taught in secondary school. I am not sure if this is sufficient. A grasp of the incompleteness theorems, even at the level of ‘the big picture’, might require some experience (...) with the rigor of mathematical proof. Moreover, since the incompleteness theorems concern formal deductive systems, it would help for a potential reader of this book to have some familiarity with at least elementary logic.There are, of course, a number of informal expositions of the incompleteness theorems. I do not see the need to engage in a comparative study. The second, and more important, goal of the present book is to discuss some alleged consequences of the incompleteness theorems and, in particular, to debunk thoroughly claims in philosophy, religion, and literary criticism that are supposed to be established, or at least bolstered, by incompleteness. The execution of this part of the book is masterly. The arguments are clear and compelling.The book has eight chapters, each between eight and twenty-eight pages. The opening chapter gives a very brief account of the incompleteness theorems and a sketch of Gödel's life and work. Chapter 2 gives the main overview of the incompleteness theorems, plus …. (shrink)

In “Minds, Machines, and Gödel”, J. R. Lucas claims that Goedel's incompleteness theorem constitutes a proof “that Mechanism is false, that is, that minds cannot be explained as machines”. He claims further that “if the proof of the falsity of mechanism is valid, it is of the greatest consequence for the whole of philosophy”. It seems to me that both of these claims are exaggerated. It is true that no minds can be explained as machines. But it is not true (...) that Goedel's theorem proves this. At most, Goedel's theorem proves that not all minds can be explained as machines. Since this is so, Goedel's theorem cannot be expected to throw much light on why minds are different from machines. Lucas overestimates the importance of Goedel's theorem for the topic of mechanism, I believe, because he presumes falsely that being unable to follow any but mechanical procedures in mathematics makes something a machine. (shrink)

Mathematical instrumentalism construes some parts of mathematics, typically the abstract ones, as an instrument for establishing statements in other parts of mathematics, typically the elementary ones. Gödel’s second incompleteness theorem seems to show that one cannot prove the consistency of all of mathematics from within elementary mathematics. It is therefore generally thought to defeat instrumentalisms that insist on a proof of the consistency of abstract mathematics from within the elementary portion. This article argues that though some versions of mathematical instrumentalism (...) are defeated by Gödel’s theorem, not all are. By considering inductive reasons in mathematics, we show that some mathematical instrumentalisms survive the theorem. (shrink)

Lucas introduces this paper by an account of how he began to be interested to questions about Materialism and Mechanism. Then he suggests a simple version of the Incompleteness theorem of Gödel, showing how this theorem proposes a version of the Epimenides’ paradox able to avoid the circularity of this paradox by means of the possibility to express meta-mathematics in terms of arithmetical propositions and by substituting questions concerning truth by questions concerning provability.

Dialetheism is the view that there exists a true contradiction. This paper ventures to suggest that Priest’s argument for Dialetheism from Gödel’s theorem is unconvincing as the lesson of Gödel’s proof (or Rosser’s proof) is that any sufficiently strong theories of arithmetic cannot be both complete and consistent. In addition, a contradiction is derivable in Priest’s inconsistent and complete arithmetic. An alternative argument for Dialetheism is given by applying Gödel sentence to the inconsistent and complete theory of arithmetic. We argue, (...) however, that the alternative argument raises a circularity problem. In sum, Gödel’s and its related theorem merely show the relation between a complete and a consistent theory. A contradiction derived by the application of Gödel sentence has the value of true sentences, i.e. the both-value, only under the inconsistent models for arithmetic. Without having the assumption of inconsistency or completeness, a true contradiction is not derivable from the application of Gödel sentence. Hence, Gödel’s and its related theorem never can be a ground for Dialetheism. (shrink)

Gödel's two incompleteness theorems are among the most important results in modern logic, and have deep implications for various issues. They concern the limits of provability in formal axiomatic theories. The first incompleteness theorem states that in any consistent formal system F within which a certain amount of arithmetic can be carried out, there are statements of the language of F which can neither be proved nor disproved in F. According to the second incompleteness theorem, such a formal system cannot (...) prove that the system itself is consistent (assuming it is indeed consistent). These results have had a great impact on the philosophy of mathematics and logic. There have been attempts to apply the results also in other areas of philosophy such as the philosophy of mind, but these attempted applications are more controversial. The present entry surveys the two incompleteness theorems and various issues surrounding them. (shrink)

Let me start with a disclaimer. I am not going to be primarily concerned with the Gödelian argument against mechanism, although that is what I am primarily associated with in the public mind. Not that I don't stand by it. Although there have been many criticisms, some of them ill informed and evidently based on not having read what I had actually written, the critics had a strong tendency to disagree with one another more than they did with me, or (...) later with Roger Penrose. At first I tried to answer critical arguments, but became somewhat bored with having to make the same points over and over again. I often wondered what Gödel himself thought, having a strong sense of his being in sympathy with my general line of argument. In fact he had expressed his views in a lecture on Boxing Day, 1951, which was finally published in the third volume of his Collected Works in 1995. Gödel argues for a disjunction: an Either/Or, with the strong suggestion that the second disjunct is untenable, and hence by Modus Tollendo Ponens that the first disjunct must be true. (shrink)

In Michael Dummett's celebrated essay on Gödel's theorem he considers the threat posed by the theorem to the idea that meaning is use and argues that this threat can be annulled. In my essay I try to show that the threat is even less serious than Dummett makes it out to be. Dummett argues, in effect, that Gödel's theorem does not prevent us from "capturing" the truths of arithmetic; I argue that the idea that meaning is use does not require (...) that we be able to "capture" these truths anyway. Towards the end of my essay I relate what I have been arguing first to Dummett's concept of indefinite extensibility and then to some of Wittgenstein's remarks on Gödel's theorem. (shrink)

Wilfried Sieg. Formal Systems, Church Turing Thesis, and Gödel's Theorems: Three Contributions to The MIT Encyclopedias of Cognitive Science.

Textbook on Gödel’s incompleteness theorems and computability theory, based on the Open Logic Project. Covers recursive function theory, arithmetization of syntax, the first and second incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus.

A Husserlian phenomenological approach to logic treats concepts in terms of their experiential meaning rather than in terms of reference, sets of individuals, and sentences. The present article applies such an approach in turn to the reasoning operative in various paradoxes: the simple Liar, the complex Liar paradoxes, the Grelling-type paradoxes, and Gödel’s Theorem. It finds that in each case a meaningless statement, one generated by circular definition, is treated as if were meaningful, and consequently as either true or false, (...) although in fact it is neither. The situation is further complicated by the fact that the sentence used to express the meaningless statement is ambiguous, and may also be used to express a meaningful statement. The paradoxes result from a failure to distinguish between the two meanings the sentence may have. (shrink)

In this paper, we attempt to show that a weak version of Hilbert's metamathematics is compatible with Gödel's Incompleteness Theorems by employing only what are clearly natural prov‐ ability predicates. Defining first “T proves the consistency of a theory S indirectly in one step”, we subsequently prove “PA proves its own consistency indirectly in one step” and sketch the proof for “If S is a recursively enumerable extension of , S proves its own consistency indirectly in one step”. The formalizations (...) of the metatheoretical consistency assertions that occur in these theorems are clearly the natural ones. We conclude the paper with reflections on indirect consistency proofs and soundness proofs. (shrink)

On the heels of Franzén's fine technical exposition of Gödel's incompleteness theorems and related topics (Franzén 2004) comes this survey of the incompleteness theorems aimed at a general audience. Gödel's Theorem: An Incomplete Guide to its Use and Abuse is an extended and self-contained exposition of the incompleteness theorems and a discussion of what informal consequences can, and in particular cannot, be drawn from them.

Remarks on the Foundations of Mathematics, Wittgenstein, despite his official 'mathematical nonrevisionism', slips into attempting to refute Gödel's theorem. Actually, Wittgenstein could have used Gödel's theorem to good effect, to support his view that proof, and even truth, are 'family resemblance' concepts. The reason that Wittgenstein did not see all this is that Gödel's theorem had become an icon of mathematical realism, and he was blinded by his own ideology. The essay is a reply to Juliet Floyd's work on Gödel: (...) what she says Wittgenstein said, I say he should have said, but didn't (couldn't). (shrink)

In this paper I discuss whether Gödel's incompleteness theorems have any implications for studies in Artificial Life (AL). Since Gödel's incompleteness theorems have been used to argue against certain mechanistic theories of the mind, it seems natural to attempt to apply the theorems to certain strong mechanistic arguments postulated by some AL theorists. -/- We find that an argument using the incompleteness theorems can not be constructed that will block the hard AL claim, specifically in the field of robotics. However, (...) we will see that the beginnings of an argument casting doubt on our ability to create living systems entirely resident in a computer environment might be suggested by looking at the incompleteness theorems from the point of view of Gödel's belief in mathematical realism. (shrink)

Slides for the second tutorial on Gödel's incompleteness theorems, held at UniLog 5 Summer School, Istanbul, June 24, 2015.

In 1931, the young Kurt Gödel published his First Incompleteness Theorem, which tells us that, for any sufficiently rich theory of arithmetic, there are some arithmetical truths the theory cannot prove. This remarkable result is among the most intriguing (and most misunderstood) in logic. Gödel also outlined an equally significant Second Incompleteness Theorem. How are these Theorems established, and why do they matter? Peter Smith answers these questions by presenting an unusual variety of proofs for the First Theorem, showing how (...) to prove the Second Theorem, and exploring a family of related results (including some not easily available elsewhere). The formal explanations are interwoven with discussions of the wider significance of the two Theorems. This book - extensively rewritten for its second edition - will be accessible to philosophy students with a limited formal background. It is equally suitable for mathematics students taking a first course in mathematical logic. -/- (This second edition revises the first edition, with the aim of making it even more reader-friendly.). (shrink)