The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness (...) class='Hi'>theorem, and Boolos’ theorem is derived from the second incompleteness theorem in the standard way. It is also shown that none of Rosser’s, Kleene’s second or Boolos’ theorems is equivalent with the second incompleteness theorem, and Chaitin’s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another. (shrink)

We prove that any 1-closed (see def 1.1) model of the Π 2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Godel incompleteness theorem without the use of the Godel diagonal lemma. We prove a few other theorems by the same method.

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

Informal statements of Gödel's Second Incompleteness Theorem, referred to here as Informal Second Incompleteness, are simple and dramatic. However, current versions of Formal Second Incompleteness are complicated and awkward. We present new versions of Formal Second Incompleteness that are simple, and informally imply Informal Second Incompleteness. These results rest on the isolation of simple formal properties shared by consistency statements. Here we do not address any issues concerning proofs of (...) Second Incompleteness. (shrink)

In this paper I have considered various attempts to attribute significance to Gödel's second incompleteness theorem (G2 for short). Two of these attempts (Beth-Cohen and the position maintaining that G2 shows the failure of Hilbert's Program), I have argued, are false. Two others (an argument suggested by Beth, Cohen and ??? and Resnik's Interpretation), I argue, are groundless.

By generalizing Kreisel’s proof of the Second Incompleteness Theorem of G¨odel I extract a general principle which can also be used for otherpurely model-theoretical proofs of that theorem.

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

We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition (...) faces serious obstacles. We conclude that, in the types of settings mentioned, the Reflexivity Defense does not justify the usual ‘reading’ of G2—namely, that the consistency of the represented theory is not provable in the representing theory. (shrink)

It is argued that an instrumentalist notion of proof such as that represented in Hilbert's viewpoint is not obligated to satisfy the conservation condition that is generally regarded as a constraint on Hilbert's Program. A more reasonable soundness condition is then considered and shown not to be counter-exemplified by Godel's First Theorem. Finally, attention is given to the question of what a theory is; whether it should be seen as a "list" or corpus of beliefs, or as a (...) method for selecting beliefs. The significance of this question for assessing "intensional" results like Godel's Second Theorem, and their bearing on Hilbert's Program are discussed. (shrink)

The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introducedeviantnumberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of (...) this paper however, these “counterexamples” do not refute the theorem’s prevalent interpretation, since once a natural class ofadmissiblenumberings is singled out, invariance is maintained. (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.

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 (...) class='Hi'>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)

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 several publications, Juliet Floyd and Hilary Putnam have argued that the so-called ‘notorious paragraph’ of the Remarks on the Foundations of Mathematics contains a valuable philosophical insight about Gödel’s informal proof of the first incompleteness theorem – in a nutshell, the idea they attribute to Wittgenstein is that if the Gödel sentence of a system is refutable, then, because of the resulting ω-inconsistency of the system, we should give up the translation of Gödel’s sentence by the English (...) sentence “I am unprovable”.I will argue against Floyd and Putnam’s use of the idea, and I will indirectly question its attribution to Wittgenstein. First, I will point out that the idea is inefficient in the context of the first incompleteness theorem because there is an explicit assumption of soundness in Gödel’s informal discussion of that theorem. Secondly, I will argue that of he who makes the observation that Floyd and Putnam think Wittgenstein has made about the first theorem, one will expect to see an analogous observation about Gödel’s second incompleteness theorem – yet we see nothing to that effect in Wittgenstein’s remarks. Incidentally, that never-made remark on the import of the second theorem is of genuine logical significance.‏. (shrink)

It is not yet clear just what the most illuminating ways of rigorously stating the Incompleteness Theorems are. This is particularly true of the Second. Also I believe that there are more illuminating proofs of the Second that have yet to be uncovered.

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)

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 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 (...) class='Hi'>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)

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)

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.

We present an analogue of Gödel’s second incompleteness theorem for systems of second-order arithmetic. Whereas Gödel showed that sufficiently strong theories that are $\Pi ^0_1$ -sound and $\Sigma ^0_1$ -definable do not prove their own $\Pi ^0_1$ -soundness, we prove that sufficiently strong theories that are $\Pi ^1_1$ -sound and $\Sigma ^1_1$ -definable do not prove their own $\Pi ^1_1$ -soundness. Our proof does not involve the construction of a self-referential sentence but rather relies on ordinal (...) analysis. (shrink)

We present a semantic proof of Gödel's second incompleteness theorem, employing Grelling's antinomy of heterological expressions. For a theory T containing ZF, we define the sentence HETT which says intuitively that the predicate “heterological” is itself heterological. We show that this sentence doesn't follow from T and is equivalent to the consistency of T. Finally we show how to construct a similar incompleteness proof for Peano Arithmetic.

We translate Socrates’ famous saying I know that I know nothing into the arithmetical sentence I prove that I prove nothing. Then it is easy to show that this translated saying is formally undecidable in formal arithmetic, using Gödel’s Second Incompleteness Theorem. We investigate some variations of this Socrates-Gödel sentence. In an appendix we sketch a ramified epistemic logic with propositional quantifiers in order to analyze the Socrates-Gödel sentence in a more logical way, separated from the arithmetical (...) context. (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 paper addresses the question: given some theory T that we accept, is there some natural, generally applicable way of extending T to a theory S that can prove a range of things about what it itself (i.e. S) can prove, including a range of things about what it cannot prove, such as claims to the effect that it cannot prove certain particular sentences (e.g. 0 = 1), or the claim that it is consistent? Typical characterizations of Gödel’s second (...) incompleteness theorem, and its significance, would lead us to believe that the answer is ‘no’. But the present paper explores a positive answer. The general approach is to follow the lead of recent (and not so recent) approaches to truth and the Liar paradox. (shrink)

Gödel's second incompleteness theorem is proved for Herbrand consistency of some arithmetical theories with bounded induction, by using a technique of logarithmic shrinking the witnesses of bounded formulas, due to Z. Adamowicz [Herbrand consistency and bounded arithmetic, Fundamenta Mathematical vol. 171 (2002), pp. 279-292]. In that paper, it was shown that one cannot always shrink the witness of a bounded formula logarithmically, but in the presence of Herbrand consistency, for theories I∆₀+ Ωm, with m ≥ 2, any (...) witness for any bounded formula can be shortened logarithmically. This immediately implies the unprovability of Herbrand consistency of a theory T ⊇ I∆₀ + Ω₂ in t itself. In this paper, the above results are generalized for I∆₀ + Ω₁. Also after tailoring the definition of Herbrand consistency for I∆₀ we prove the corresponding theorems for I∆₀. Thus the Herbrand version of Gödel's second incompleteness theorem follows for the theories I∆₀ + Ω₁ and I∆₀. (shrink)

In a note appended to the translation of “On consistency and completeness” (), Gödel reexamined the problem of the unprovability of consistency. Gödel here focuses on an alternative means of expressing the consistency of a formal system, in terms of what would now be called a ‘reflection principle’, roughly, the assertion that a formula of a certain class is provable in the system only if it is true. Gödel suggests that it is this alternative means of expressing consistency that we (...) should be interested in from a foundational point of view, and he gives a result that shows certain reflection principles to be underivable in extensions of elementary number theory under conditions significantly weaker than the Hilbert-Bernays derivability conditions. In this paper I shall discuss the background to Gödel's result and the foundational significance he claims for it. Along the way, I shall present a new proof of the result which places it in an even more general context than the one considered by Gödel in the 1960s. (shrink)

We give a proof of Gödel's first incompleteness theorem based on Berry's paradox, and from it we also derive the second incompleteness theorem model-theoretically.

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)

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.

Guided by questions of scope, this paper provides an overview of what is known about both the scope and, consequently, the limits of Gödel’s famous first incompleteness theorem.

We present a new manifestation of Gödel’s second incompleteness theorem and discuss its foundational significance, in particular with respect to Hilbert’s program. Specifically, we consider a proper extension of Peano arithmetic ( $\mathbf {PA}$ ) by a mathematically meaningful axiom scheme that consists of $\Sigma ^0_2$ -sentences. These sentences assert that each computably enumerable ( $\Sigma ^0_1$ -definable without parameters) property of finite binary trees has a finite basis. Since this fact entails the existence of polynomial time (...) algorithms, it is relevant for computer science. On a technical level, our axiom scheme is a variant of an independence result due to Harvey Friedman. At the same time, the meta-mathematical properties of our axiom scheme distinguish it from most known independence results: Due to its logical complexity, our axiom scheme does not add computational strength. The only known method to establish its independence relies on Gödel’s second incompleteness theorem. In contrast, Gödel’s theorem is not needed for typical examples of $\Pi ^0_2$ -independence (such as the Paris–Harrington principle), since computational strength provides an extensional invariant on the level of $\Pi ^0_2$ -sentences. (shrink)

The aim of this paper is to argue about the impossibility of constructing a complete formal theory or a complete Turing machines' algorithm that represent the human capacity of recognizing mathematical truths. More specifically, based on a direct argument from Gödel's First Incompleteness Theorem, we discuss the impossibility of constructing a complete formal theory or a complete Turing machines' algorithm to the human capacity of recognition of first-order arithmetical truths and so of mathematical truths in general.

Within a weak subsystem of second-order arithmetic , that is -conservative over , we reformulate Kreisel's proof of the Second Incompleteness Theorem and Boolos' proof of the First Incompleteness Theorem.

In this paper I shall consider two related avenues of argument that have been used to make the case for the inconsistency of mathematics: firstly, Gödel’s paradox which leads to a contradiction within mathematics and, secondly, the incompatibility of completeness and consistency established by Gödel’s incompleteness theorems. By bringing in considerations from the philosophy of mathematical practice on informal proofs, I suggest that we should add to the two axes of completeness and consistency a third axis of formality and (...) informality. I use this perspective to respond to the arguments for the inconsistency of mathematics made by Beall and Priest, presenting problems with the assumptions needed concerning formalisation, the unity of informal mathematics and the relation between the formal and informal. (shrink)

According to a common view, belief in God cannot be proved and is an issue that must be left to faith. Kant went even further and argued that he can prove this unprovability. But any argument implying that a certain sentence is not provable is challenged by Gödel’s second theorem. Indeed, one trivial consequence of GST is that for any formal system F that satisfies certain conditions and for every sentence K that is formulated in F it is (...) impossible to prove, from F, that K is not provable. In the article, I explore the general issue of proving the unprovability of the existence of God. Of special interest is the question of the relation between the existence of God and the conditions that F must satisfy in order to allow for its subjection to GST. (shrink)

We present an abstract framework in which we give simple proofs for Gödel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’, Chaitin’s and Kritchman-Raz’s Theorems.

It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with (...) Gödel’s results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines. (shrink)

The present first part about the eventual completeness of mathematics (called “Hilbert mathematics”) is concentrated on the Gödel incompleteness (1931) statement: if it is an axiom rather than a theorem inferable from the axioms of (Peano) arithmetic, (ZFC) set theory, and propositional logic, this would pioneer the pathway to Hilbert mathematics. One of the main arguments that it is an axiom consists in the direct contradiction of the axiom of induction in arithmetic and the axiom of infinity in (...) set theory. Thus, the pair of arithmetic and set are to be similar to Euclidean and non-Euclidean geometries distinguishably only by the Fifth postulate now, i.e. after replacing it and its negation correspondingly by the axiom of finiteness (induction) versus that of finiteness being idempotent negations to each other. Indeed, the axiom of choice, as far as it is equivalent to the well-ordering “theorem”, transforms any set in a well-ordering either necessarily finite according to the axiom of induction or also optionally infinite according to the axiom of infinity. So, the Gödel incompleteness statement relies on the logical contradiction of the axiom of induction and the axiom of infinity in the final analysis. Nonetheless, both can be considered as two idempotent versions of the same axiom (analogically to the Fifth postulate) and then unified after logicism and its inherent intensionality since the opposition of finiteness and infinity can be only extensional (i.e., relevant to the elements of any set rather than to the set by itself or its characteristic property being a proposition). So, the pathway for interpreting the Gödel incompleteness statement as an axiom and the originating from that assumption for “Hilbert mathematics” accepting its negation is pioneered. A much wider context relevant to realizing the Gödel incompleteness statement as a metamathematical axiom is consistently built step by step. The horizon of Hilbert mathematics is the proper subject in the third part of the paper, and a reinterpretation of Gödel’s papers (1930; 1931) as an apology of logicism as the only consistent foundations of mathematics is the topic of the next second part. (shrink)