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.

An introductory textbook on metalogic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. The audience is undergraduate students with some background in formal logic.

Gödel’s philosophical conceptions bear striking similarities to Cantor’s. Although there is no conclusive evidence that Gödel deliberately used or adhered to Cantor’s views, one can successfully reconstruct and see his “Cantorianism” at work in many parts of his thought. In this paper, I aim to describe the most prominent conceptual intersections between Cantor’s and Gödel’s thought, particularly on such matters as the nature and existence of mathematical entities (sets), concepts, Platonism, the Absolute Infinite, the progress and inexhaustibility of mathematics.

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)

The paper is devoted to the discussion of some philosophical and historical problems connected with the theorem on the undefinability of the notion of truth. In particular the problem of the priority of proving this theorem will be considered. It is claimed that Tarski obtained this theorem independently though he made clear his indebtedness to Gödel’s methods. On the other hand, Gödel was aware of the formal undefinability of truth in 1931, but he did not publish this result. Reasons for (...) that are also considered. (shrink)

This paper proposes a possible reconstruction and philosophical-logical clarification of Gödel's idea of causality as the philosophical fundamental concept. The results are based on Gödel's published and non-published texts (including Max Phil notebooks), and are established on the ground of interconnections of Gödel's dispersed remarks on causality, as well as on the ground of his general philosophical views. The paper is logically informal but is connected with already achieved results in the formalization of a causal account of Gödel's onto-theological theory. (...) Gödel's main causal concepts are analysed (will, force, enjoyment, God, time and space, life, form, matter). Special attention is paid to a possible causal account of some of Gödel's logical concepts (assertion, privation, affirmation, negation, whole, part, general, particular, subject, predicate, necessary, possible, implication), as well as of logical antinomies. The problem of mechanical and non-mechanical procedures in the work with and on concepts is addressed in terms of Gödel's causal view. (shrink)

Modern science, based on the laws of physics, claims validity for all events in space and time. However, it also reveals its own limitations, such as the indeterminacy of quantum physics, the limits of decidability, and, presumably, limits of decodability of the mind-brain relationship. At the philosophical level, these intrinsic limitations allow for different interpretations of the relation between human cognition and the natural order. In particular, modern science may be logically consistent with religious as well as agnostic views of (...) humans and the universe. These points are exemplified through the transcript of a discussion between Kurt Gödel and Rudolf Carnap that took place in 1940. Gödel, discoverer of mathematical undecidability, took a proreligious view; Carnap, one of the founders of analytical philosophy, an antireligious view. By the time of the discussion, Carnap had liberalized his ideas on theoretical concepts of science: he believed that observational terms do not suffice for an exhaustive definition of theoretical concepts. Then, responded Gödel, one should formulate a theory or metatheory that is consistent with scientific rationality, yet also encompasses theology. Carnap considered such theories unproductive. The controversy remained unresolved, but its emphasis shifted from rationality to wisdom, not only in the Gödel-Carnap discussion but also in our time. -/- . (shrink)

This paper discusses a sequence of extensions ofNFU, Jensen's improvement of Quine's set theory “New Foundations” (NF) of [16].The original theoryNFof Quine continues to present difficulties. After 60 years of intermittent investigation, it is still not known to be consistent relative to any set theory in which we have confidence. Specker showed in [20] thatNFdisproves Choice (and so proves Infinity). Even if one assumes the consistency ofNF, one is hampered by the lack of powerful methods for proofs of consistency and (...) independence such as are available for use withZFC; very clever work has been done with permutation methods, starting with [18] and [5], and exemplified more recently by [14], but permutation methods can only be applied to show the consistency or independence of unstratified sentences (see the definition ofNFUbelow for a definition of stratification). For example, there is no method available to determine whether the assertion “the continuum can be well-ordered” is consistent with or independent ofNF. There is one substantial independence result for an assertion with nontrivial stratified consequences, using metamathematical methods: this is Orey's proof of the independence of the Axiom of Counting fromNF(see below for a statement of this axiom).We mention these difficulties only to reassure the reader of their irrelevance to the present work. Jensen's modification of “New Foundations” (in [13]), which was to restrict extensionality to sets, allowing many non-sets (urelements) with no elements, has almost magical effects. (shrink)

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

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)

In set theory, a maximality principle is a principle that asserts some maximality property of the universe of sets or some part thereof. Set theorists have formulated a variety of maximality principles in order to settle statements left undecided by current standard set theory. In addition, philosophers of mathematics have explored maximality principles whilst attempting to prove categoricity theorems for set theory or providing criteria for selecting foundational theories. This article reviews recent work concerned with the formulation, investigation and justification (...) of maximality principles. (shrink)

‘Reasoning’ can be considered a general concept that, upon speaking, is the ‘enraonar’, a Catalan word that should not be mistaken with ‘explain’ nor with ‘discuss’ which imply more detail, and cover different situations. This article is presented as an essay on the ancient ideal of ‘enraonar’. To that end, it is explained in what sense ‘enraonar’ and reason are one of the most complex phenomena thought has to deal with. Here it is argued that these natural phenomena require a (...) systematic and ‘scientific’ study, and that withoutthis knowledge computer science cannot simulate people’s every-day ‘enraonar’. (shrink)

It is by now well known that Gödel first advocated the philosophy of Leibniz and then, since 1959, that of Husserl. This raises three questions:1.How is this turn to Husserl to be interpreted? Is it a dismissal of the Leibnizian philosophy, or a different way to achieve similar goals?2.Why did Gödel turn specifically to the later Husserl's transcendental idealism?3.Is there any detectable influence from Husserl on Gödel's writings?Regarding the first question, Wang [96, p.165] reports that Gödel ‘[saw] in Husserl's work (...) a method of refining and consolidating Leibniz' monadology’. But what does this mean? In what for Gödel relevant sense is Husserl's work a refinement and consolidation of Leibniz' monadology?The second question is particularly pressing, given that Gödel was, by his own admission, a realist in mathematics since 1925. Wouldn't the uncompromising realism of the early Husserl's Logical investigations have been a more obvious choice for a Platonist like Gödel?The third question can only be approached when an answer to the second has been given, and we want to suggest that the answer to the first question follows from the answer to the second. We begin, therefore, with a closer look at the actual turn towards phenomenology.Some 30 years before his serious study of Husserl began, Gödel was well aware of the existence of phenomenology. Apart from its likely appearance in the philosophy courses that Gödel took, it reached him from various directions. (shrink)

This paper surveys the interactions between Russell and Gödel, both personal and intellectual. After a description of Russell’s influence on Gödel, it concludes with a discussion of Russell’s reaction to the incompleteness theorems.

In 1880, when Oliver Wendell Holmes (later to be a Justice of the U.S. Supreme Court) criticized the logical theology of law articulated by Christopher Columbus Langdell (the first Dean of Harvard Law School), neither Holmes nor Langdell was aware of the revolution in logic that had begun, the year before, with Frege's Begriffsschrift. But there is an important element of truth in Holmes's insistence that a legal system cannot be adequately understood as a system of axioms and corollaries; and (...) this element of truth is not obviated by the more powerful logical techniques that are now available. (shrink)

It is well known that in his later years Gödel turned to a systematic reading of phenomenology, whose founder, Edmund Husserl, was highly esteem as a philosopher who sought to elevate philosophy to the standards of a rigorous science. For reasons purportedly related to his earlier attraction to Leibnizian monadology, Gödel was particularly interested in Husserl's transcendental phenomenology and the way it may shape the discussion on the nature of mathematical‐logical objects and the meaning and internal coherence of primitive terms (...) in mathematics. This article, which is less interested in historical facts that are amply presented in other scholars’ accounts, rather tries to point to the mostly indirect influence that the ideas of transcendental phenomenology, including Gödel's reported reference to the notion of (inner) time, had on his philosophy of mathematics, especially with a view to key independent questions of mathematical foundations. A main source for Gödel's philosophical‐epistemological views (of course in addition to his own published material) will be his recorded discussions with H. Wang and S. Toledo, as well as various articles and drafts found in his Nachlass. (shrink)

According to some scholars, such as Rodych and Steiner, Wittgenstein objects to Gödel’s undecidability proof of his formula $$G$$, arguing that given a proof of $$G$$, one could relinquish the meta-mathematical interpretation of $$G$$ instead of relinquishing the assumption that Principia Mathematica is correct. Most scholars agree that such an objection, be it Wittgenstein’s or not, rests on an inadequate understanding of Gödel’s proof. In this paper, I argue that there is a possible reading of such an objection that is, (...) in fact, reasonable and related to Gödel’s proof. (shrink)

The use of the three labels to denote the three foundational schools of the early twentieth century are now part of literature. Yet, neither their number nor the...

This book summarizes the intense research that the author performed for his Ph.D. thesis , revised and with the addition of an intuitionistic critique of Husserl's concept of number. His starting point consisted of a double conviction: 1) Brouwerian intuitionism is a valid way of doing mathematics but is grounded on a weak philosophy; 2) Husserlian phenomenology can provide a suitable philosophical ground for intuitionism. In order to let intuitionism and phenomenology match, he had to solve in general two problems: (...) 1) the question of the reciprocal indifference that the authors had toward each other's theorizing which indeed they knew; 2) Husserl's general attitude of accepting classical mathematics, which contrasts with the critical attitude of the intuitionists.Moreover, in the specific case focused on by this book—concerning choice sequences, that is, sequences that can be completely lawless and that were admitted as mathematical entities by Brouwer—van Atten had to handle a further problem: such sequences do not fit the characteristic of omnitemporality that the late Husserl seemed to consider a necessary attribute of entities if they were to be considered mathematical. In as far as they are lawless we cannot predict at any moment how they will develop in the future, hence they are not determined at any particular time—they will be determined only in the future.Let us begin with van Atten's first conviction, i.e., that Brouwerian intuitionism is grounded on a weak philosophy. We have to recall that Brouwer provided a mystical attitude for proposing his intuitionism: man can obtain happiness only by keeping himself closed inside the inner Self. Any attempted movement towards the exterior world is a source of pain: in particular language and the sciences. Mathematics, in order to be morally acceptable …. (shrink)

The paper examines the interrelationship between mathematics and logic, arguing that a central characteristic of each has an essential role within the other. The first part is a reconstruction of and elaboration on Paul Bernays’ argument, that mathematics and logic are based on different directions of abstraction from content, and that mathematics, at its core it is a study of formal structures. The notion of a study of structure is clarified by the examples of Hilbert’s work on the axiomatization of (...) geometry and Hilbert et al.’s formalist proof theory. It is further argued that the structural aspect of logic puts it under the purview of the mathematical, analogously to how the deductive nature of mathematics puts it under the purview of logic. This is then linked, in the second part, to certain aspects of Gödel’s critique of Carnap’s conventionalism, that ‘mere syntax’ cannot capture the full content of mathematics, which is revealed to be closely related to the characteristic of mathematics argued for by Bernays. Finally, this is connected with Gödel’s latter-day views about two kinds of formality, intensional and extensional, and the relationship between them. (shrink)