Online research in philosophy

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.

Kurt Godel, the greatest logician of our time, startled the world of mathematics in 1931 with his Theorem of Undecidability, which showed that some statements in mathematics are inherently "undecidable." His work on the completeness of logic, the incompleteness of number theory, and the consistency of the axiom of choice and the continuum theory brought him further worldwide fame. In this introductory volume, Raymond Smullyan, himself a well-known logician, guides the reader through the fascinating world of Godel's incompleteness theorems. The level of presentation is suitable for anyone with a basic acquaintance with mathematical logic. As a clear, concise introduction to a difficult but essential subject, the book will appeal to mathematicians, philosophers, and computer scientists.

This work is a sequel to the author's Godel's Incompleteness Theorems, though it can be read independently by anyone familiar with Godel's incompleteness theorem for Peano arithmetic. The book deals mainly with those aspects of recursion theory that have applications to the metamathematics of incompleteness, undecidability, and related topics. It is both an introduction to the theory and a presentation of new results in the field.

In this paper we interpret a characterization of the Gödel speed-up phenomenon as providing support for the ‘Nagel-Newman thesis’ that human theorem recognizers differ from mechanical theorem recognizers in that the former do not seem to be limited by Gödel's incompleteness theorems whereas the latter do seem to be thus limited. However, we also maintain that (currently non-existent) programs which are open systems in that they continuously interact with, and are thus inseparable from, their environment, are not covered by the above (or probably any other recursion-theoretic) argument.

Gödel began his 1951 Gibbs Lecture by stating: “Research in the foundations of mathematics during the past few decades has produced some results which seem to me of interest, not only in themselves, but also with regard to their implications for the traditional philosophical problems about the nature of mathematics.” (Gödel 1951) Gödel is referring here especially to his own incompleteness theorems (Gödel 1931). Gödel’s first incompleteness theorem (as improved by Rosser (1936)) says that for any consistent formalized system F, which contains elementary arithmetic, there exists a sentence GF of the language of the system which is true but unprovable in that system. Gödel’s second incompleteness theorem states that no consistent formal system can prove its own consistency.

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.

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

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

We give a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity, Chaitin's incompleteness theorem, and an argument that resembles the surprise examination paradox. We then go the other way around and suggest that the second incompleteness theorem gives a possible resolution of the surprise examination paradox. Roughly speaking, we argue that the flaw in the derivation of the paradox is that it contains a hidden assumption that one can prove the consistency of the mathematical theory in which the derivation is done; which is impossible by the second incompleteness theorem.

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.