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)

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)

In the paper some applications of Gödel's incompleteness theorems to discussions of problems of computer science are presented. In particular the problem of relations between the mind and machine (arguments by J.J.C. Smart and J.R. Lucas) is discussed. Next Gödel's opinion on this issue is studied. Finally some interpretations of Gödel's incompleteness theorems from the point of view of the information theory are presented.

The determinism-free will debate is perhaps as old as philosophy itself and has been engaged in from a great variety of points of view including those of scientific, theological, and logical character. This chapter focuses on two arguments from logic. First, there is an argument in support of determinism that dates back to Aristotle, if not farther. It rests on acceptance of the Law of Excluded Middle, according to which every proposition is either true or false, no matter whether the (...) proposition is about the past, present or future. In particular, the argument goes, whatever one does or does not do in the future is determined in the present by the truth or falsity of the corresponding proposition. The second argument coming from logic is much more modern and appeals to Gödel's incompleteness theorems to make the case against determinism and in favour of free will, insofar as that applies to the mathematical potentialities of human beings. The claim more precisely is that as a consequence of the incompleteness theorems, those potentialities cannot be exactly circumscribed by the output of any computing machine even allowing unlimited time and space for its work. The chapter concludes with some new considerations that may be in favour of a partial mechanist account of the mathematical mind. (shrink)

Although written in Japanese, this article handles historical and technical survey of Gödel's incompleteness theorem thoroughly.

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)

This paper is a summary of a lecture in which I presented some remarks on Gödel’s incompleteness theorems and their meaning for the foundations of physics. The entire lecture will appear elsewhere.

This paper is a summary of a lecture in which I presented some remarks on Gödel’s incompleteness theorems and their meaning for the foundations of physics. The entire lecture will appear elsewhere. doi: http://dx.doi.org/ 10.5007 / 1808-1711.2011v15n3p453.

Over a period of 22 years (1934-1955), the mathematician Kurt Gödel wrote down philosophical remarks, the so-called Maximen Philosophie (Max Phil). They are preserved in 15 notebooks in Gabelsberger shorthand. The first booklet contains general philosophical considerations, booklets two and three consist of Gödel's individual ethics. The following books show that Gödel developed a philosophy of science in which he places his discussions on physics, psychology, biology, mathematics, language, theology and history in the context of a metaphysics. A complete, historical-critical (...) edition of Gödel's Philosophical Notebooks is now being prepared for the first time at the Kurt Gödel Research Centre of the Berlin-Brandenburg Academy of Sciences and Humanities. One volume will be published each year as part of this edition. Volume 5 is particularly interesting because Gödel reveals his satisfaction with it at the beginning of 'Maximen V'. He states that he has arrived at independent thought here, which has not primarily come about through discussion with other authors. Furthermore, in addition to numerous remarkable philosophical considerations, there is a previously unknown interpretation of his (second) incompleteness theorem that goes beyond the mathematical one. (shrink)

We give a survey of current research on Gödel’s incompleteness theorems from the following three aspects: classifications of different proofs of Gödel’s incompleteness theorems, the limit of the applicability of Gödel’s first incompleteness theorem, and the limit of the applicability of Gödel’s second incompleteness theorem.

This paper is a summary of a lecture in which I presented some remarks on Gödel’s incompleteness theorems and their meaning for the foundations of physics. The entire lecture will appear elsewhere.

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n L(F ). The proof resembles Berry’s..

At the turn of the century, there appeared two comprehensive mathematical systems, which were indeed so vast that it was taken for granted that all mathematics could be decided on the basis of them. However, in 1931, Kurt Gödel surprised the entire mathematical world with his epoch‐making paper which begins with the following startling words: The development of mathematics in the direction of greater precision has led to large areas of it being formalized, so that proofs can be carried out (...) according to a few mechanical rules. The most comprehensive formal systems to date are, on the one hand, the Principia Mathematica of Whitehead and Russell, and, on the other hand the Zermelo‐Fraenkel system of axiomatic set theory. Both systems are so extensive that all methods of proof used in mathematics today can be formalized in them‐i.e., can be reduced to a few axioms and rules of inference. It would seem reasonable, therefore, to surmise that these axioms and rules of inference are sufficient to decide all mathematical questions which can be formulated in the system concerned. In what follows it will be shown that this is not the case, but rather that, in both of the cited systems, there exist relatively simple problems of the theory of ordinary whole numbers which cannot be decided on the basis of the axioms. (shrink)

This Element takes a deep dive into Gödel's 1931 paper giving the first presentation of the Incompleteness Theorems, opening up completely passages in it that might possibly puzzle the student, such as the mysterious footnote 48a. It considers the main ingredients of Gödel's proof: arithmetization, strong representability, and the Fixed Point Theorem in a layered fashion, returning to their various aspects: semantic, syntactic, computational, philosophical and mathematical, as the topic arises. It samples some of the most important proofs (...) of the Incompleteness Theorems, e.g. due to Kuratowski, Smullyan and Robinson, as well as newer proofs, also of other independent statements, due to H. Friedman, Weiermann and Paris-Harrington. It examines the question whether the incompleteness of e.g. Peano Arithmetic gives immediately the undecidability of the Entscheidungsproblem, as Kripke has recently argued. It considers set-theoretical incompleteness, and finally considers some of the philosophical consequences considered in the literature. (shrink)

According to several commentators, Kurt Godel's incompleteness discoveries were assimilated promptly and almost without objection by his contemporaries - - a circumstance remarkable enough to call for explanation. Careful examination reveals, however, that there were doubters and critics, as well as defenders and rival claimants to priority. In particular, the reactions of Carnap, Bernays, Zermelo, Post, Finsler, and Russell, among others, are considered in detail. Documentary sources include unpublished correspondence from Godel's Nachlass.

It is well known that Gödel’s incompleteness theorems hold for ∑1-definable theories containing Peano arithmetic. We generalize Gödel’s incompleteness theorems for arithmetically definable theories. First, we prove that every ∑n+1-definable ∑n-sound theory is incomplete. Secondly, we generalize and improve Jeroslow and Hájek’s results. That is, we prove that every consistent theory having ∏n+1set of theorems has a true but unprovable ∏nsentence. Lastly, we prove that no ∑n+1-definable ∑n-sound theory can prove its own ∑n-soundness. These three results are generalizations (...) of Rosser’s improvement of the first incompleteness theorem, Gödel’s first incompleteness theorem, and the second incompleteness theorem, respectively. (shrink)

In this paper I argue that it is more difficult to see how Godel's incompleteness theorems and related consistency proofs for formal systems are consistent with the views of formalists, mechanists and traditional intuitionists than it is to see how they are consistent with a particular form of mathematical realism. If the incompleteness theorems and consistency proofs are better explained by this form of realism then we can also see how there is room for skepticism about Church's Thesis (...) and the claim that minds are machines. (shrink)

The paper examines Husserl’s interactions with logicians in the 1930s in order to assess Husserl’s awareness of Gödel’s incompleteness theorems. While there is no mention about the results in Husserl’s known exchanges with Hilbert, Weyl, or Zermelo, the most likely source about them for Husserl is Felix Kaufmann (1895–1949). Husserl’s interactions with Kaufmann show that Husserl may have learned about the results from him, but not necessarily so. Ultimately Husserl’s reading marks on Friedrich Waismann’s Einführung in das mathematische Denken: (...) die Begriffsbildung der modernen Mathematik, 1936, show that he knew about them before his death in 1938. (shrink)

ABSTRACT We use Gödel’s incompleteness theorems as a case study for investigating mathematical depth. We examine the philosophical question of what the depth of Gödel’s incompleteness theorems consists in. We focus on the methodological study of the depth of Gödel’s incompleteness theorems, and propose three criteria to account for the depth of the incompleteness theorems: influence, fruitfulness, and unity. Finally, we give some explanations for our account of the depth of Gödel’s incompleteness theorems.

A survey of more philosophical applications of Gödel's incompleteness results.

What were the earliest reactions to Gödel's incompleteness theorems? After a brief summary of previous work in this area I analyse, by means of unpublished archival material, the first reactions in Vienna and Berlin to Gödel's groundbreaking results. In particular, I look at how Carnap, Hempel, von Neumann, Kaufmann, and Chwistek, among others, dealt with the new results.

This paper reassesses the criticism of the Lucas-Penrose anti-mechanist argument, based on Gödel’s incompleteness theorems, as formulated by Krajewski : this argument only works with the additional extra-formal assumption that “the human mind is consistent”. Krajewski argues that this assumption cannot be formalized, and therefore that the anti-mechanist argument – which requires the formalization of the whole reasoning process – fails to establish that the human mind is not mechanistic. A similar situation occurs with a corollary to the argument, (...) that the human mind allegedly outperforms machines, because although there is no exhaustive formal definition of natural numbers, mathematicians can successfully work with natural numbers. Again, the corollary requires an extra-formal assumption: “PA is complete” or “the set of all natural numbers exists”. I agree that extra-formal assumptions are necessary in order to validate the anti-mechanist argument and its corollary, and that those assumptions are problematic. However, I argue that formalization is possible and the problem is instead the circularity of reasoning that they cause. The human mind does not prove its own consistency, and outperforms the machine, simply by making the assumption “I am consistent”. Starting from the analysis of circularity, I propose a way of thinking about the interplay between informal and formal in mathematics. (shrink)

This article shows that in two respects, Gödel's incompleteness theorem strongly supports the arguments of Edgar Morin's complexity paradigm. First, from the viewpoint of the content of Gödel's theorem, the latter justifies the basic view of complexity paradigm according to which knowledge is a dynamic, unfinished process, and develops by way of self-criticism and self-transcendence. Second, from the viewpoint of the proof procedure of Gödel's theorem, the latter confirms the complexity paradigm's circular line of inference through (...) which is formed the all-round knowledge of a concrete object. (shrink)

It is shown in this article in how far one has to have a clear picture of Gödel’s philosophy and scientific thinking at hand (and also the philosophical positions of other philosophers in the history of Western Philosophy) in order to interpret one single Philosophical Remark by Gödel. As a single remark by Gödel (very often) mirrors his whole philosophical thinking, Gödel’s Philosophical Remarks can be seen as a philosophical monadology. This is so for two reasons mainly: Firstly, because it (...) pictures a monadology already via its form. And secondly, because Gödel wanted to establish in his Philosophical Remarks a modern monadology in adapting the philosophical principles of Leibniz’s monadology to modern science. This article will only deal with the first aspect that has been mentioned namely that a single remark by Gödel (very often) mirrors his whole philosophy (at the time) for example: set theory, perception and intuition of mathematical objects and axioms, the nature of the human mind, the concept and existence of God, and so on. This renders it extremely difficult to interpret Gödel’s philosophical remarks but interpreting it provides also a deep insight in Gödel’s philosophical thoughts. (shrink)

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)

What Gödel accomplished in the decade of the 1930s before joining the Institute changed the face of mathematical logic and continues to influence its development. As you gather from my title, I’ll be talking about the most famous of his results in that period, but first I want to indulge in some personal reminiscences. In many ways this is a sentimental journey for me. I was a member of the Institute in 1959-60, a couple of years after receiving my PhD (...) at the University of California in Berkeley, where I had worked with Alfred Tarski, another great logician. The subject of my dissertation was directly concerned with the method of arithmetization that Gödel had used to prove his theorems, and my main concern after that was to study systematic ways of overcoming incompleteness. Mathematical logic was going through a period of prodigious development in the 1950s and 1960s, and Berkeley and Princeton were two meccas for researchers in that field. For me, the prospect of meeting with Gödel and drawing on him for guidance and inspiration was particularly exciting. I didn’t know at the time what it took to get invited. Hassler Whitney commented for an obituary notice in 1978 that “it was hard to appoint a new member in logic at the Institute because Gödel could not prove to himself that a number of candidates shouldn’t be members, with the evidence at hand.” That makes it sound like the problem for Gödel was deciding who not to invite. Anyhow, I ended up being one of the lucky few. (shrink)

An outline is given of the development of logicism from the publication of the first edition of Whitehead and Russell's Principia mathematica (1910-1913) through the contributions of Wittgenstein, Ramsey and Chwistek to Russell's own modifications made for the second edition of the work (1925) and the adoption of many of its logical techniques by the Vienna Circle. A tendency towards extensionalism is emphasised.

We argue that Gödel's completeness theorem is equivalent to completability of consistent theories, and Gödel's incompleteness theorem is equivalent to the fact that this completion is not constructive, in the sense that there are some consistent and recursively enumerable theories which cannot be extended to any complete and consistent and recursively enumerable theory. Though any consistent and decidable theory can be extended to a complete and consistent and decidable theory. Thus deduction and consistency are not decidable in (...) logic, and an analogue of Rice's Theorem holds for recursively enumerable theories: all the non-trivial properties of them are undecidable. (shrink)