• How to construct a ‘canonical’ Gödel sentence • If PA is sound, it is negation imcomplete • Generalizing that result to sound p.r. axiomatized theories whose language extends LA • ω-incompleteness, ω-inconsistency • If PA is ω-consistent, it is negation imcomplete • Generalizing that result to ω-consistent p.r. axiomatized theories which extend Q..

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

Let T be an extension of Robinson's arithmetic Q. Then T is incomplete even if the set of the Gödel numbers of all axioms of T is ∑2.

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)

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.

I define T-schema deflationism as the thesis that a theory of truth for our language can simply take the form of certain instances of Tarski's schema (T). I show that any effective enumeration of these instances will yield as a dividend an effective enumeration of all truths of our language. But that contradicts Gödel's First Incompleteness Theorem. So the instances of (T) constituting the T-Schema deflationist's theory of truth are not effectively enumerable, which casts doubt on the (...) idea that the T-schema deflationist in any sense has a theory of truth. (The argument in section 2 of "Semantics for Deflationists" supercedes this paper.). (shrink)

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)

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)

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.

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 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)

By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov complexity. We (...) shall show also that Vopěnka's proof can be reformulated in arithmetic by using the arithmetized completeness theorem. (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)

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.

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 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)

This chapter describes Kurt Gödel's paper on the incompleteness theorems. Gödel's incompleteness results are two of the most fundamental and important contributions to logic and the foundations of mathematics. It had been assumed that first-order number theory is complete in the sense that any sentence in the language of number theory would be either provable from the axioms or refutable. Gödel's first incompleteness theorem showed that this assumption was false: it states that there are (...) sentences of number theory that are neither provable nor refutable. The first theorem is general in the sense that it applies to any axiomatic theory, which is ω-consistent, has an effective proof procedure, and is strong enough to represent basic arithmetic. Their importance lies in their generality: although proved specifically for extensions of system, the method Gödel used is applicable in a wide variety of circumstances. Gödel's results had a profound influence on the further development of the foundations of mathematics. It pointed the way to a reconceptualization of the view of axiomatic foundations. (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.

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.

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)

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)

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)

Preface 1 The First Theorem revisited 1.1 Notational preliminaries 1.2 Definitional preliminaries 1.3 A general version of G¨ odel’s First Theorem 1.4 Giving the First Theorem bite 1.5 Generic G¨ odel sentences and arithmetic truth 1.6 Canonical and standard G¨ odel sentences 2 The Second Theorem revisited 2.1 Definitional preliminaries 2.2 Towards G¨ odel’s Second Theorem 2.3 A general version of G¨ odel’s Second Theorem 2.4 Giving the Second Theorem bite (...) 2.5 Comparisons 2.6 Further results about provability predicates 2.7 Back to the First Theorem 2.8 Introducing Rosserized provability predicates.. (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.

Reference [12] introduced a novel formula to formula translation tool that enables syntactic metatheoretical investigations of first-order modallogics, bypassing a need to convert them first into Gentzen style logics in order torely on cut elimination and the subformula property. In fact, the formulator tool,as was already demonstrated in loc. cit., is applicable even to the metatheoreticalstudy of logics such as QGL, where cut elimination is unavailable. This paper applies the formulator approach to show the independence of the axiom (...) schema ☐A → ☐∀ A of the logics M3and ML3 of [17, 18, 11, 13]. This leads to the conclusion that the two logics obtained by removing this axiom are incomplete, both with respect to their natural Kripke structures and to arithmetical interpretations. In particular, the so modified ML3 is, similarly to QGL, an arithmetically incomplete first-order extension of GL, but, unlike QGL, all its theorems have cut free proofs. We also establish here, via formulators, a stronger version of the disjunction property for GL and QGL without going through Gentzen versions of these logics. (shrink)

In the Handbook of Mathematical Logic, the Paris-Harrington variant of Ramsey's theorem is celebrated as the first result of a long ‘search’ for a purely mathematical incompleteness result in first-order Peano arithmetic. This paper questions the existence of any such search and the status of the Paris-Harrington result as the first mathematical incompleteness result. In fact, I argue that Gentzen gave the first such result, and that it was restated by Goodstein in a (...) number-theoretic form. (shrink)

We begin by considering two principles, each having the form causal completeness ergo screening-off. The first concerns a common cause of two or more effects; the second describes an intermediate link in a causal chain. They are logically independent of each other, each is independent of Reichenbach's principle of the common cause, and each is a consequence of the causal Markov condition. Simple examples show that causal incompleteness means that screening-off may fail to obtain. We derive a stronger (...) result: in a rather general setting, if the composite cause C1 & C2 & … & Cn screens-off one event from another, then each of the n component causes C1, C2, …, Cn must fail to screen-off. The idea that a cause may be ordinally invariant in its impact on different effects is defined; it plays an important role in establishing this no-go theorem. Along the way, we describe how composite and component causes can all screen-off when ordinal invariance fails. We argue that this theorem is relevant to assessing the plausibility of the two screening-off principles. The discovery of incomplete causes that screen-off is not evidence that causal completeness must engender screening-off. Formal and epistemic analogies between screening-off and determinism are discussed. (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)

In Arrovian social choice theory assuming the independence of irrelevant alternatives, Murakami (1968) proved two theorems about complete and transitive collective choice rules that satisfy strict non-imposition (citizens’ sovereignty), one being a dichotomy theorem about Paretian or anti-Paretian rules and the other a dictator-or-inverse-dictator impossibility theorem without the Pareto principle. It has been claimed in the later literature that a theorem of Malawski and Zhou (1994) is a generalization of Murakami’s dichotomy theorem and that Wilson’s (1972) (...) impossibility theorem is stronger than Murakami’s impossibility theorem, both by virtue of replacing Murakami’s assumption of strict non-imposition with the assumptions of non-imposition and non-nullness. In this note, we first point out that these claims are incorrect: non-imposition and non-nullness are together equivalent to strict non-imposition for all transitive collective choice rules. We then generalize Murakami’s dichotomy and impossibility theorems to the setting of incomplete social preference. We prove that if one drops completeness from Murakami’s assumptions, his remaining assumptions imply (i) that a collective choice rule is either Paretian, anti-Paretian, or dis-Paretian (unanimous individual preference implies noncomparability) and (ii) that adding proposed constraints on noncomparability, such as the regularity axiom of Eliaz and Ok (2006), restores Murakami’s dictator-or-inverse-dictator result. (shrink)

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of (...) forging connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine,M, and claims that the output ofMconsists of all and only the arithmetic truths that a human, or the totality of human mathematicians, will ever or can ever know. We assume that the output ofMis consistent. (shrink)

It might seem that three of Godel’s results - the Completeness and the First and Second Incompleteness Theorems - assume so little that they are reasonably indisputable. A version of the Completeness Theorem, for instance, can be proven in RCA0, which is the weakest system studied extensively in Simpson’s encyclopaedic Subsystems of Second Order Arithmetic. And it often seems that the minimum requirements for a system just to express the Incompleteness Theorems are sufficient to prove them. (...) However, it will be shown that a particular sub-system of Peano Arithmetic is powerful enough to express assertions about syntax, provability, consistency, and models, while being too weak to allow the standard proofs of the theorems to go through. An alternative proof is available for the First Incompleteness Theorem, but is of such a different nature that the import of the theorem changes. And there are no alternative proofs for (certainly) the Completeness and (apparently) the Second Incompleteness Theorems. It is therefore perfectly rational for someone to be skeptical about Godel’s results. (shrink)

This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays (1939) and also how it was later adapted by Kreisel (1950) (...) and Wang (1955) in order to obtain formal undecidability results. A generalization of this method will then be presented whereby Russell’s paradox, a variant of Mirimanoff’s paradox, the Liar, and the Grelling–Nelson paradox may be uniformly transformed into incompleteness theorems. Some additional observations are then framed relating these results to the unification of the set theoretic and semantic paradoxes, the intensionality of arithmetization (in the sense of Feferman, 1960), and axiomatic theories of truth. (shrink)

In Episode 1, we introduced the very idea of a negation-incomplete formalized theory T . We noted that if we aim to construct a theory of basic arithmetic, we’ll ideally like the theory to be able to prove all the truths expressible in the language of basic arithmetic, and hence to be negation complete. But Gödel’s First Incompleteness Theorem says, very roughly, that a nice theory T containing enough arithmetic will always be negation incomplete. Now, the (...) class='Hi'>Theorem comes in two flavours, depending on whether we cash out the idea of being ‘nice enough’ in terms of (i) the semantic idea of T ’s being a sound theory, or (ii) the idea of odel’s own T ’s being a consistent theory which proves enough arithmetic. And we noted that G¨. (shrink)

There is a long-standing gap in the literature as to whether Gödelian incompleteness constitutes a challenge for Neo-Logicism, and if so how serious it is. In this paper, I articulate and address the challenge in detail. The Neo-Logicist project is to demonstrate the analyticity of arithmetic by deriving all its truths from logical principles and suitable definitions. The specific concern raised by Gödel’s first incompleteness theorem is that no single sound system of logic syntactically implies all (...) arithmetical truths. I set out some responses that initially seem appealing and explain why they are not compelling. The upshot is that Neo-Logicism either offers an epistemic route only to some truths of arithmetic; or that it has to move from a syntactic to a semantic notion of logical consequence, which risks undermining its epistemic goals. I conclude by considering Crispin Wright’s recent attempt to address Gödelian incompleteness, which I argue is not satisfactory. (shrink)

In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem. We first define the notion “$\textsf {G1}$ holds for the theory $T$”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $\textsf {G1}$ holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s $\mathbf {R}$ interprets T but T does not (...) interpret $\mathbf {R}$ and $\textsf {G1}$ holds for T? In this paper, we show that there are many such theories based on Jeřábek’s work using some model theory. We prove that for each recursively inseparable pair $\langle A,B\rangle $, we can construct a r.e. theory $U_{\langle A,B\rangle }$ such that $U_{\langle A,B\rangle }$ is weaker than $\mathbf {R}$ w.r.t. interpretation and $\textsf {G1}$ holds for $U_{\langle A,B\rangle }$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $\mathbf {0}< \mathbf {d}<\mathbf {0}^{\prime }$, there is a theory T with Turing degree $\mathbf {d}$ such that $\textsf {G1}$ holds for T and T is weaker than $\mathbf {R}$ w.r.t. Turing reducibility. As a corollary, based on Shoenfield’s work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which $\textsf {G1}$ holds. (shrink)

I provide an interpretation of Wittgenstein's much criticized remarks on Gödel's First Incompleteness Theorem in the light of paraconsistent arithmetics: in taking Gödel's proof as a paradoxical derivation, Wittgenstein was right, given his deliberate rejection of the standard distinction between theory and metatheory. The reasoning behind the proof of the truth of the Gödel sentence is then performed within the formal system itself, which turns out to be inconsistent. I show that the models of paraconsistent arithmetics (obtained (...) via the Meyer-Mortensen collapsing filter on the standard model) match with many intuitions underlying Wittgensteins philosophy of mathematics, such as its strict finitism and the insistence on the decidability of any meaningful mathematical question. (shrink)

We first state a few previously obtained results that lead to general undecidability and incompleteness theorems in axiomatized theories that range from the theory of finite sets to classical elementary analysis. Out of those results we prove several incompleteness theorems for axiomatic versions of the theory of noncooperative games with Nash equilibria; in particular, we show the existence of finite games whose equilibria cannot be proven to be computable.

We first state a few previously obtained results that lead to general undecidability and incompleteness theorems in axiomatized theories that range from the theory of finite sets to classical elementary analysis. Out of those results we prove several incompleteness theorems for axiomatic versions of the theory of noncooperative games with Nash equilibria; in particular, we show the existence of finite games whose equilibria cannot be proven to be computable.

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 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 the early seventies, several logicians developed a semantics for propositional systems of relevance logic. The essential ingredients of this semantics were a privileged point o, an ‘accessibility’ relation R and a special operator * for evaluating negation. Under the truth- conditions of the semantics, each formula A(Pl,…,Pn) could be seen as expressing a first order condition A+(pl,…,pn, o, R,*) on sets p1,…,pn and o, R, *, while each formula-scheme could be regarded as expressing the second-order condition ∀p1,…,∀pn A+(p1,…,pn, (...) o, R, *). It could then be shown that many standard systems of propositional relevance logic were complete in the sense that their theorems were just those formulas true in all models whose components o, R and * conformed to the second-order conditions expressed by the axioms of the system. (shrink)

In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem, “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal V}$-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves (...) the open question in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to ${\cal V}$-baos, namely the provability logic $GLB$. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness. (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.

Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, (...) Bull. of the LMS 14 285–293]) and Harvey Friedman [S.G. Simpson, Non-provability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117; R. Smith, The consistency strength of some finite forms of the Higman and Kruskal theorems, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 119–136] who produced the first mathematically interesting independence results in Ramsey theory and well-order and well-quasi-order theory .In this article we investigate Friedman-style principles of combinatorial well-foundedness for the ordinals below ε0. These principles state that there is a uniform bound on the length of decreasing sequences of ordinals which satisfy an elementary recursive growth rate condition with respect to their Gödel numbers.For these independence principles we classify their phase transitions, i.e. we classify exactly the bounding conditions which lead from provability to unprovability in the induced combinatorial well-foundedness principles.As Gödel numbering for ordinals we choose the one which is induced naturally from Gödel’s coding of finite sequences from his classical 1931 paper on his incompleteness results.This choice makes the investigation highly non-trivial but rewarding and we succeed in our objectives by using an intricate and surprising interplay between analytic combinatorics and the theory of descent recursive functions. For obtaining the required bounds on count functions for ordinals we use a classical 1961 Tauberian theorem of Parameswaran which apparently is far remote from Gödel’s theorem. (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.

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.

Why these notes? After all, I’ve written An Introduction to Gödel’s Theorems. Surely that’s more than enough to be going on with? Ah, but there’s the snag. It is more than enough. In the writing, as is the way with these things, the book grew far beyond the scope of the lecture notes from which it started. And while I hope the result is still pretty accessible to someone prepared to put in the time and effort, there’s a lot more (...) in the book than is really needed by philosophers meeting the incompleteness theorems for the first time. After all, you might want to get your heads around only those technical basics which are actually needed for understanding philosophical discussions about incompleteness. So you need a cut-down version of the book – an introduction to the Introduction! Well, isn’t that what lectures are for? Indeed. But there’s another snag. I haven’t got many lectures to play with. So either I crack on at quite a fast pace, cover those basics, but perhaps leave too many people puzzled and alarmed. Or I do relaxed talk’n’chalk, highlighting the really Big Ideas, making sure everyone is grasping them as we go along, but inevitably omit important stuff and leave quite a gap between what happens in the lectures and what happens in the book. What to do? I’m going for plan. But then I still need to do something to fill that gap between lectures and book. Hence these notes. The idea, then, is to give relaxed lectures, highlighting Big Ideas, not worrying too much about depth or fine-detail. Then after the lecture, I’ll write up notes that expand things just enough, and then give pointers to relevant chunks of IGT. The idea, however, is for the notes to be more or less stand-alone, and to tell a brief but coherent story read by themselves. So occasionally I’ll copy a paragraph or two from the book, rather than just refer to them. Warning: just occasionally in these notes, I’ll no doubt apply that good maxim ‘Where it doesn’t itch, don’t scratch’. (shrink)

This paper examines the incompleteness of collective preference. We provide a series of Arrovian impossibility theorems without completeness. First, we consider the notion of regularity introduced by Eliaz and Ok (2006, Games and Economic Behavior 56, 61–86); it is an appropriate richness property for strict preference when preference is allowed to be incomplete. We examine the implication of imposing regularity on collective preference. Second, we propose responsiveness, a variation of positive responsiveness. This axiom requires that some changes in (...) individual preferences make an alternative weakly better than another. Third, we consider coherency conditions for collective preferences; this conditionally requires the existence of comparable pairs in a certain manner. We prove an impossibility result for each condition using Arrovian axioms. (shrink)

Kurt Gödel’s Incompleteness theorem is well known in Mathematics/Logic/Philosophy circles. Gödel was able to find a way for any given P (UTM), (read as, “P of UTM” for “Program of Universal Truth Machine”), actually to write down a complicated polynomial that has a solution iff (=if and only if), G is true, where G stands for a Gödel-sentence. So, if G’s truth is a necessary condition for the truth of a given polynomial, then P (UTM) has to answer (...) first that G is true in order to secure the truth of the said polynomial. But, interestingly, P (UTM) could never answer that G was true. This necessarily implies that there is at least one truth a P (UTM), however large it may be, cannot speak out. Daya Krishna and Karl Potter’s controversy regarding the construal of India’s Philosophies dates back to the time of Potter’s publication of “Presuppositions of India’s Philosophies” (1963, Englewood Cliffs Prentice-Hall Inc.) In attacking many of India’s philosophies, Daya Krishna appears to have unwittingly touched a crucial point: how can there be the knowledge of a ‘non-cognitive’ mokṣa? [‘mokṣa’ is the final state of existence of an individual away from Social Contract]—See this author’s Indian Social Contract and its Dissolution (2008) mokṣa does not permit the knowledge of one’s own self in the ordinary way with threefold distinction, i.e., subject–knowledge-object or knower–knowledge–known. But what is important is to demonstrate whether such ‘knowledge’ of non-cognitive mokṣa state can be logically shown, in a language, to be possible to attain, and that there is no contradiction involved in such demonstration, because, no one can possibly express the ‘experience-itself’ in language. Hence, if such ‘knowledge’ can be shown to be logically not impossible in language, then, not only Daya Krishna’s arguments against ‘non-cognitive mokṣa’ get refuted but also it would show the possibility of achieving ‘completeness’ in its truest sense, as opposed to Gödel’s ‘Incompleteness’. In such circumstances, man would himself become a Universal Truth Machine. This is because the final state of mokṣa is construed as the state of complete knowledge in Advaita. This possibility of ‘completeness’ is set in this paper in the backdrop of Śrī Śaṅkarācārya’s Advaitic (Non-dualistic) claim involved in the mahāvākyas (extra-ordinary propositions). (Mahāvākyas that Śaṅkara refers to are basically taken from different Upaniṣads. For example, “Aham Brahmāsmi” is from Bṛhadāraṇyaka Upanisad, and “Tattvamasi” is from Chāndogya Upaniṣad. Śrī Śaṅkarācārya has written extensively. His main works include his Commentary on Brahma-Sūtras, on major Upaniṣads, and on ŚrīmadBhagavadGītā, called Bhāṣyas of them, respectively. Almost all these works are available in English translation published by Advaita Ashrama, 5 Dehi Entally Road, Calcutta, 700014.) On the other hand, the ‘Incompleteness’ of Gödel is due to the intervening G-sentence, which has an adverse self-referential element. Gödel’s incompleteness theorem in its mathematical form with an elaborate introduction by R.W. Braithwaite can be found in Meltzer (Kurt Gödel: on formally undecidable propositions of principia mathematica and related systems. Oliver & Boyd, Edinburgh, 1962). The present author believes first that semantic content cannot be substituted by any amount of arithmoquining, (Arithmoquining or arithmatization means, as Braithwaite says,—“Gödel’s novel metamathematical method is that of attaching numbers to the signs, to the series of signs (formulae) and to the series of series of signs (“proof-schemata”) which occur in his formal system…Gödel invented what might be called co-ordinate metamathematics…”) Meltzer (1962 p. 7). In Antone (2006) it is said “The problem is that he (Gödel) tries to replace an abstract version of the number (which can exist) with the concept of a real number version of that abstract notion. We can state the abstraction of what the number needs to be, [the arithmoquining of a number cannot be a proof-pair and an arithmoquine] but that is a concept that cannot be turned into a specific number, because by definition no such number can exist.”.), especially so where first-hand personal experience is called for. Therefore, what ultimately rules is the semanticity as in a first-hand experience. Similar points are voiced, albeit implicitly, in Antone (Who understands Gödel’s incompleteness theorem, 2006). (“…it is so important to understand that Gödel’s theorem only is true with respect to formal systems—which is the exact opposite of the analogous UTM (Antone (2006) webpage 2. And galatomic says in the same discussion chain that “saying” that it ((is)) only true for formal systems is more significant… We only know the world through “formal” categories of understanding… If the world as it is in itself has no incompleteness problem, which I am sure is true, it does not mean much, because that is not the world of time and space that we experience. So it is more significant that formal systems are incomplete than the inexperiencable ‘World in Itself’ has no such problem.—galatomic”) Antone (2006) webpage 2. Nevertheless galatomic certainly, but unwittingly succeeds in highlighting the possibility of experiencing the ‘completeness’ Second, even if any formal system including the system of Advaita of Śaṅkara is to be subsumed or interpreted under Gödel’s theorem, or Tarski’s semantic unprovability theses, the ultimate appeal would lie to the point of human involvement in realizing completeness since any formal system is ‘Incomplete’ always by its very nature as ‘objectual’, and fails to comprehend the ‘subject’ within its fold. (shrink)