Godel's Theorem

I give a detailed review of 'The Outer Limits of Reason' by Noson Yanofsky from a unified perspective of Wittgenstein and evolutionary psychology. I indicate that the difficulty with such issues as paradox in language and math, incompleteness, undecidability, computability, the brain and the universe as computers etc., all arise from the failure to look carefully at our use of language in the appropriate context and hence the failure to separate issues of scientific fact from issues of how language works. (...) I discuss Wittgenstein's views on incompleteness, paraconsistency and undecidability and the work of Wolpert on the limits to computation. To sum it up: The Universe According to Brooklyn---Good Science, Not So Good Philosophy. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 3rd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv dot org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, (...) and even independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility, incompleteness, the limits of computation, and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things, a non- quantum mechanical uncertainty principle and a proof of monotheism. There are obvious connections to the classic work of Chaitin, Solomonoff, Komolgarov and Wittgenstein and to the notion that no program (and thus no device) can generate a sequence (or device) with greater complexity than it possesses. One might say this body of work implies atheism since there cannot be any entity more complex than the physical universe and from the Wittgensteinian viewpoint, ‘more complex’ is meaningless (has no conditions of satisfaction, i.e., truth-maker or test). Even a ‘God’ (i.e., a ‘device’with limitless time/space and energy) cannot determine whether a given ‘number’ is ‘random’, nor find a certain way to show that a given ‘formula’, ‘theorem’ or ‘sentence’ or ‘device’ (all these being complex language games) is part of a particular ‘system’. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 2nd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

Introduction to mathematical logic, part 2.Textbook for students in mathematical logic and foundations of mathematics. Platonism, Intuition, Formalism. Axiomatic set theory. Around the Continuum Problem. Axiom of Determinacy. Large Cardinal Axioms. Ackermann's Set Theory. First order arithmetic. Hilbert's 10th problem. Incompleteness theorems. Consequences. Connected results: double incompleteness theorem, unsolvability of reasoning, theorem on the size of proofs, diophantine incompleteness, Loeb's theorem, consistent universal statements are provable, Berry's paradox, incompleteness and Chaitin's theorem. Around Ramsey's theorem.

Review of "Exploring Randomness" (200) and "The Unknowable" (1999) by Gregory Chaitin.

In this paper, I recreate a paradox from my earlier work (“Paradox with just self-reference”) albeit entirely within the language of arithmetic. (In lieu of self-referential expressions, Gödel numbering is used to generate the paradox.) This can suggest that Robinson arithmetic and its extensions are unsound; however, I claim instead that the metalanguage may be to blame, owing to arithmetization of syntax. If so, then the moral would be to restrict arithmetization in the metalanguage somehow, rather than distrust the arithmetical (...) theory in the object language. (shrink)

The mathematical proof is the most important form of justification in mathematics. It is not, however, the only kind of justification for mathematical propositions. The existence of other forms, some of very significant strength, places a question mark over the prominence given to proof within mathematics. This collection of essays, by leading figures working within the philosophy of mathematics, is a response to the challenge of understanding the nature and role of the proof.

The formalist philosophy of mathematics (in its purest, most extreme version) is widely regarded as a “discredited position”. This pure and extreme version of formalism is called by some authors “game formalism”, because it is alleged to represent mathematics as a meaningless game with strings of symbols. Nevertheless, I would like to draw attention to some arguments in favour of game formalism as an appropriate philosophy of real mathematics. For the most part, these arguments have not yet been used or (...) were neglected in past discussions. (shrink)

This volume represents the beginning of a new stage of research in interpreting Kurt Gödel’s philosophy in relation to his scientific work. It is more than a collection of essays on Gödel. It is in fact the product of a long enduring international collaboration on Kurt Gödel’s Philosophical Notebooks (Max Phil). New and significant material has been made accessible to a group of experts, on which they rely for their articles. In addition to this, Gödel’s Nachlass is presented anew by (...) the current state of research and the corpus of Gödel’s Philosophical Notebooks (Max Phil) is described in its entirety for the first time in its details. The volume is sub-divided into three parts. The fist part is dedicated to descriptions of the Gödel Nachlass that is to be found in The Shelby White and Leon Levy Archives Center des Institute for Advanced Study in Princeton. This part starts with an updated overview on Kurt Gödel’s Nachlass by the current state of research and is followed by a detailed description of Gödel’s Philosophical Notebooks (Max Phil). The second part is dedicated by several Gödel scholars to the close reading of single remarks in the Max Phil. And the third part of this volume unites a variety of papers by experts in Gödel studies, logic, and Leibniz as well as by some enthusiasts for Gödel. These papers are nearly all written for this volume. (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 Theorem, showing how to prove the (...) Second Theorem, and exploring a family of related results. The formal explanations are interwoven with discussions of the wider significance of the two Theorems. This book will be accessible to philosophy students with a limited formal background. It is equally suitable for mathematics students taking a first course in mathematical logic. (shrink)

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

O presente artigo procede, em primeiro lugar, a um exame das evidências disponíveis referentes à atitude de Wittgenstein em relação ao, bem como conhecimento do, primeiro teorema da incompletude de Gödel, incluindo as suas discussões com Turing, Watson e outros em 1937-1939, e o testemunho posterior de Goodstein e Kreisel Em segundo lugar, o artigo discute a importância filosófica e histórica da atitude de Wittgenstein em relação ao teorema de Gödel e outros teoremas da lógica matemática, contrastando esta atitude com (...) a de, por exemplo, Penrose. Finalmente, a autora responde também a criticas instrutivas feitas por Mark Steiner a um artigo seu publicado em 1995, as quais estabelecem a importância do trabalho semântico de Tarski, quer para o nosso entendimento das observacoes de Wittgenstein. /// This paper presents, first, a survey of current evidence available concerning Wittgenstein's attitude toward, and knowledge of, Gödel's first incompleteness theorem, including his discussions with Turing, Watson and others in 1937-1939, and later testimony of Goodstein and Kreisel Secondly, the article discusses the philosophical and historical importance of Wittgenstein's attitude toward Gödal's and other theorems in mathematical logic, contrasting this attitude with that of, e. g., Penrose. Finally, the author also replies to an instructive criticism of her 1995 paper by Mark Steiner which assesses the importance ofTarskih semantical work, both for our understanding of Wittgenstein's remarks on Godel, and our understanding ofGodeVs theorem itself. (shrink)

A survey of current evidence available concerning Wittgenstein's attitude toward, and knowledge of, Gödel's first incompleteness theorem, including his discussions with Turing, Watson and others in 1937–1939, and later testimony of Goodstein and Kreisel; 2) Discussion of the philosophical and historical importance of Wittgenstein's attitude toward Gödel's and other theorems in mathematical logic, contrasting this attitude with that of, e.g., Penrose; 3) Replies to an instructive criticism of my 1995 paper by Mark Steiner which assesses the importance of Tarski's semantical (...) work, both for our understanding of Wittgenstein's remarks on Gödel, and our understanding of Gödel's theorem itself. (shrink)

1) A survey of current evidence available concerning Wittgenstein's attitude toward, and knowledge of, Gödel's first incompleteness theorem, including his discussions with Turing, Watson and others in 1937–1939, and later testimony of Goodstein and Kreisel; 2) Discussion of the philosophical and historical importance of Wittgenstein's attitude toward Gödel's and other theorems in mathematical logic, contrasting this attitude with that of, e.g. , Penrose; 3) Replies to an instructive criticism of my 1995 paper by Mark Steiner which assesses the importance of (...) Tarski's semantical work, both for our understanding of Wittgenstein's remarks on Gödel, and our understanding of Gödel's theorem itself. (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 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)

This is a review of Penrose's trilogy, The Emperor's New Mind, Shadows of the Mind and The Large the Small and the Human Mind.

Introduction to a special issue of Philosophia Mathematica on the mechanization of reasoning. Authors include: M. Detlefsen, D. Mundici, S. Shanker, S. Shapiro, W. Sieg and C. Wright.

Various parallels between Kant's critical program and Hilbert's formalistic program for the philosophy of mathematics are considered.

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)

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.

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)

Gödel’s incompleteness applies to any system with recursively enumerable axioms and rules of inference. Chaitin’s approach to Gödel’s incompleteness relates the incompleteness to the amount of information contained in the axioms. Zurek’s quantum Darwinism attempts the physical description of the universe using information as one of its major components. The capacity of quantum Darwinism to describe quantum measurement in great detail without requiring ad-hoc non-unitary evolution makes it a good candidate for describing the transition from quantum to classical. A baby-universe (...) diffusion model of cosmic inflation is analyzed using quantum Darwinism. In this model cosmic inflation can be approximated as Brownian motion of a quantum field, and quantum Darwinism implies that molecular interaction during Brownian motion will make the quantum field decohere. The quantum Darwinism approach to decoherence in the baby-universe cosmic-inflation model yields the decoherence times of the baby-universes. The result is the equation relating the baby-universe’s decoherence time with the Hubble parameter, and that the decoherence time is considerably shorter than the cosmic inflation period. (shrink)

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

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

Albert Einstein once made the following remark about "the world of our sense experiences": "the fact that it is comprehensible is a miracle." (1936, p. 351) A few decades later, another physicist, Eugene Wigner, wondered about the unreasonable effectiveness of mathematics in the natural sciences, concluding his classic article thus: "the miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve" (1960, p. 14). (...) At least three factors are involved in Einstein's and Wigner's miracles: the physical world, mathematics, and human cognition. One way to relate these factors is to ask how the universe could possibly be structured in such a way that mathematics would be applicable to it, and we would be able to understand that application. This is roughly Wigner's question. Alternatively, the way of the mathematical naturalist is to argue that we abstract certain properties from the world, perhaps using our bodies and physical tools, thereby articulating basic mathematical concepts, which we continue building into the complex formal structures of mathematics. John Stuart Mill, Penelope Maddy, and Rafael Nuñez teach this strategy of cognitive abstraction, in very different manners. But what if the very concepts and basic principles of mathematics were built into our cognitive structure itself? Given such a cognitive a priori mathematical endowment, would the miracles of the link between world and cognition (Einstein) and mathematics and world (Wigner) not vanish, or at least significantly diminish? This is the stance of Stanislas Deheane and Elizabeth Brannon's 2011 anthology, following a venerable rationalist tradition including Plato and Immanuel Kant. (shrink)

If a semantically open language has no constraints on self-reference, one can show there is a predicate which is both satisfied and unsatisfied by a self-referring term. The argument requires diagonalization on a definition-scheme for the predicate ‘x is Lagadonian’. (The term ‘Lagadonian’ is adapted from David Lewis). Briefly, a self-referring term is counted as “Lagadonian” if the initial variable in the schema is replaced with the term itself. But the same term is not counted as Lagadonian if this variable (...) is replaced with the quotation or other name for the term. Thus the term both satisfies and does not satisfy ‘x is Lagadonian’. Finally, a related paradox is presented, which requires no self-referring name; it rather depends on a definite description for the sentence containing the description. (shrink)

Acknowledgement At one time I was labelled a mathematical prodigy. But due to insufficient luck, talent or motivation I wasn't as successful as my teachers ...

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)

This book is well known for its proof that many mathematical systems - including lattice theory and closure algebras - are undecidable. It consists of three treatises from one of the greatest logicians of all time: "A General Method in Proofs of Undecidability," "Undecidability and Essential Undecidability in Mathematics," and "Undecidability of the Elementary Theory of Groups.".

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

Any (1-)consistent and sufficiently strong system of first-order formal arithmetic fails to decide some independent Gödel sentence. We examine consistent first-order extensions of such systems. Our purpose is to discover what is minimally required by way of such extension in order to be able to prove the Gödel sentence in a nontrivial fashion. The extended methods of formal proof must capture the essentials of the so-called 'semantical argument' for the truth of the Gödel sentence. We are concerned to show that (...) the deflationist has at his disposal such extended methods--methods which make no use or mention of a truth-predicate. (edited). (shrink)

Storrs McCall appeals to a particular true but improvable sentence of formal arithmetic to argue, by appeal to its irrefutability, that human minds transcend Turing machines. Metamathematical oversights in McCall's discussion of the Godel phenomena, however, render invalid his philosophical argument for this transcendentalist conclusion.

Metaphysics, Mathematics, and Meaning brings together Nathan Salmon's influential papers on topics in the metaphysics of existence, non-existence, and fiction; modality and its logic; strict identity, including personal identity; numbers and numerical quantifiers; the philosophical significance of Godel's Incompleteness theorems; and semantic content and designation. Including a previously unpublished essay and a helpful new introduction to orient the reader, the volume offers rich and varied sustenance for philosophers and logicians.

This paper offers a justification of the ‘Hilbert-Bernays Derivability Conditions’ by considering what is required of a theory which gives an account of provability in itself.

An interpretation of Wittgenstein’s much criticized remarks on Gödel’s First Incompleteness Theorem is provided in the light of paraconsistent arithmetic: in taking Gödel’s proof as a paradoxical derivation, Wittgenstein was drawing the consequences of 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. It is shown that the features of paraconsistent arithmetics match (...) with some intuitions underlying Wittgenstein’s philosophy of mathematics, such as its strict finitism and the insistence on the decidability of any mathematical question. (shrink)

I clarify how the requirement of conservative extension features in the thinking of various deflationists, and how this relates to another litmus claim, that the truth-predicate stands for a real, substantial property. I discuss how the deflationist can accommodate the result, to which Cieslinski draws attention, that non-conservativeness attends even the generalization that all logical theorems in the language of arithmetic are true. Finally I provide a four-fold categorization of various forms of deflationism, by reference to the two claims of (...) conservativeness and substantiality. This helps to clarify the various possible positions in the deflationism debate. (shrink)