Search

There are various results due to Godel which are commonly collectively called ‘Godel’s theorem’; of these, we list the most important

In 1931 Kurt Godel [50, 51] proved a momentous theorem with far-reaching philosophical consequences: he showed that no reasonable formal proof sys-tern for number theory can prove all true sentences. This result set the logic community on its ear and left Hilbert’s formalist program in shambles. This result is widely regarded as one of the greatest intellectual achievements of twentieth-century mathematics.

There are many problems and possibilities relevant to the new paradigm, especially in regard to the relation between formal systems and natural language, that must be investigated. I have already touched on some of them, but, since Hofstadter’s ideas concerning meaning are obviously interlocked with his ideas concerning formal systems and natural language, those latter ideas should be addressed first, to preserve continuity, before I turn to the ideas of others.

A ground-motive for this study of some historical and metaphysical implications of the diagonal lemmas of Cantor and Godel is Cantor's insightful remark to Dedekind in 1899 that the Inbegriff alles Denkbaren (aggregate of everything thinkable) might, like some class-theoretic entities, be “inkonsistent”. In the essay's opening sections, I trace some recent antecedents of Cantor's observation in logical writings of Bolzano and Dedekind (more remote counterparts of his language appear in the First Critique), then attempt to relativize the notion of Inkonsistenz to ‘self-sufficient’ theories T which interpret ⌈themselves⌉. In effect, I argue that Godel's diagonal lemma suggests a sense in which metatheoretic notions of proof, well-foundeness and satisfaction are object-theoretically inkonsistent. With respect to Cantor's Inbegriff, for example, the lemma yields that any object-theoretic ‘reconstruction’ θ of ‘thinkability’ generates an ‘antidiagonal’ sentence τ, which one can paraphrase as ⌈Self-referential application of the assertion that ⌈self-reference is unthinkable⌉⌉ is unthinkable. This sentence is provably equivalent to ⌈its own⌉ ‘unthinkability’. In the essay's last sections, I offer a skeptical interpretation of the metatheoretical consistency, for any consistent and ‘self-sufficient’ scientific or mathematical theory T, of the theory T+⌝Con(T). In effect, this amounts to a preliminary study of one form of malign-genius-argument for such theories T: what should a miniature ‘metaphysical realist’ c in a model M of T+⌝Con(T) make of an encounter (perhaps indirect) with one of M's witnesses [‘nonstandard’ to ‘us’] of ⌝Con(T)? In response to this query, I argue The thought-experiment thus seems to yield a genuine metatheoretic counterpart of Duhem's traditional problem of the boundary conditions of object-theoretic consistency: ‘we’ cannot ‘know’ we are not c.

In 1931 in the journal Monatshefte fur Mathematik und Physik a short paper (a bit more than 20 pages) of an Austrian mathematician and logician Kurt Godel was published — paper which has turned out to be one of the greatest and most important papers in mathematical logic and foundations of mathematics. Its title was “Uber formal unentscheidbare Satze der ‘Principia Mathematica’ und verwandter Systeme. I”. In it Godel proved that arithmetic of natural numbers and all systems containing it are essentially incomplete provided they are consistent. It means that there are sentences which are undecidable in them, i.e. sentences φ such that neither φ, nor ¬φ are theorems. What’s more, we know which sentence of the pair φ, ¬φ is true in the basic model of the theory, i.e. in the model to the description of which the theory was formulated. This incompleteness is essential, i.e. it cannot be removed by adding the undecidable sentences as a new axioms because new undecidable sentences will appear (undecidable in the new, richer theory). This theorem (so called 1st Godel theorem) indicates the cognitive limitations of the deductive method.

One of the main goals of research in the foundations of mathematics in the 1920’s was to find a consistency proof for number theory. Not that the consistency of number theory was considered to be very dubious, but the consistency of set theory was considered a partially open question and finding a convincing consistency proof for number theory seemed a natural first step in that direction. The possibility of such a proof does not seem too unlikely since we can formalize the statement of consistency in a rather simple form: (x) — Bew(x, ‘0 = 1’). It is true that one would have to use some number theoretic principles or their equivalents to prove a statement of this form, but there was reason to hope that the proof could be carried out in a relatively ‘small’ subsystem, for example, using induction only for quantifier free formulas. Godel showed, however, in 1931 that no such proof was possible.

In this, our final chapter, we shift our center of interest first to the foundations of mathematics. In Section 8.1, we shall give a brief historical review of the formalist approach to the foundations of mathematics and see how Godel’s incompleteness theorem invalidated much of the Formalist program. In Section 8.2, we shall discuss some general properties of recursive logics, yielding a proof of Godel’s Incompleteness Theorem. We shall also follow Myhill’s surprising result that we can effectively remove this incompleteness, although never totally but only a part at a time. To deepen our understanding of Godel’s work, we present a proof of his Completeness Theorem in Section 8.3, and show the way in which completeness and incompleteness coexist. Section 8.4 studies speed-up theorems: showing that adding an axiom to a logic may not only enable the proofs of new theorems, but also dramatic shortening of proofs that were already available. Finally, in Section 8.5, we return to the main theme of this book by discussing the philosophical controversy centering around the implications of Godel’s theorem for the question: Are brains essentially superior to machines?

Publisher Summary This chapter discusses the computable analysis and differential equations. Computable analysis is an analysis restricted to the field of computable numbers, where a real number is called computable if there is an algorithm for obtaining arbitrarily precise rational approximations. Algorithms are the basis for the definitions of the functions and sequences of computable analysis, and in every instance of a number, function or sequence, an appropriate defining algorithm is assumed available. This constructive point of view leads the analysis to take on many intuitionistic aspects. A novel feature of this analysis is the wide use that can be made of the concept of effective method. The chapter discusses differential equations from the point of view of computable analysis, to bring out a few differences in comparison with real analysis, and other applications of the concept of effective method.

Publisher Summary This chapter describes unsolvable problems in the theory of computable numbers. A real number α is said to be computable if there is a recursive function associated with α , where R denotes the class of real numbers and C the class of computable numbers. The chapter considers the case of a simple root α that is not a finite decimal. As α is isolated, there is a finite decimal, such that α is the only root in the closed interval. All the roots of a polynomial with computable coefficients are computable. In particular, all algebraic numbers are computable. The problem of determining whether or not an arbitrary pair of recursive functions have the same associated numbers has the same degree of unsolvability as the Halting problem. For every recursively enumerable degree of unsolvability D, there is a class of computable numbers A such that the problem of determining whether or not two recursive functions in the class A have the same associated number has D as its degree of unsolvability.