vol 4: Glossary
Site map
Directory
Search this site
Home
1: About
2: Synopsis
3: Development
Next:
Previous: Glossary: Toc
... to restore theology to the mainstream of science
Completeness and incompleteness
[Hazewinkel, Completeness (In Logic)] [Borowski, Completeness]
Questions of completeness and incompleteness entered mathematics through Hilbert and Ackermann's treatise on the Principles of Mathematical Logic. Hilbert and Ackermann. Discussing the axiomatic method, they write that "the most important of questions which arise are those of consistency, independence and completeness". Stanley Burris.
A set of axioms is consistent if it does not contain a contradiction. That is one cannot use it derive a contradiction, p = not-p. It is independent if none of the axioms is implied by the others. Cohen. Completness means that every valid formula can be derived from the axioms of a system by means of a finite sequence of formal inferences. Goedel, in Feferman, p 61.
The classic work on completeness and incompleteness was done by Kurt Goedel, whose papers are reproduced in German and English in Feferman. In On the completness of the calculus of logic, Goedel showed that the 'calculus of logic' (which is now called propositional calculus) is complete. This result was quite consistent with the mathematical feeling of the era expressed by Hilbert: There are absolutely no unsolvable problems. Instead of the foolish ignorabimus, our answer is on the contrary: We must know, We shall know. Jeremy Gray.
Goedel's second result was much more surprising and dashed Hilbert's hope. In On formally undecidable propositions of Principia Mathematica and related systems I and II , Goedel wrote:
These two systems [the system of Principa Mathematica and the Zermelo-Fraenkel-von Neumann axioms for set theory] are so comprehensive that in them all methods of proof used in mathematics today are formalized, that is reduced to a few axioms and rulkes of inference. One might therefore conjecture that these axioms and rules of inference are sufficient to decide any mathematical question that can be formally expressed in tehse systems. It will be shown below that this is not the case, that on the contrary there are in the two systems mentioned relatively simple problems in the theory of integers that cannot be decided on the basis of the axioms. in Feferman, p 145, Kurt Goedel 1.
The mathematical consequences of incompleteness are still emerging. The next step in the chain was Turing's discovery of incomputability. Turing, Davis.
Further reading
Books
| Chaitin, Gregory J, Information, Randomness & Incompleteness: Papers on Algorithmic Information Theory, World Scientific 1987 Jacket: 'Algorithmic information theory is a branch of computational complexity theory concerned with the size of computer programs rather than with their running time. ... The theory combines features of probability theory, information theory, statistical mechanics and thermodynamics, and recursive function or computability theory. ... [A] major application of algorithmic information theory has been the dramatic new light it throws on Goedel's famous incompleteness theorem and on the limitations of the axiomatic method. ...' Amazon back |
| Chaitin, Gregory J, Algorithmic Information Theory, Cambridge UP 1987 Foreword: 'The crucial fact here is that there exist symbolic objects (i.e., texts) which are "algorithmically inexplicable", i.e., cannot be specified by any text shorter than themselves. Since texts of this sort have the properties associated with random sequences of classical probability theory, the theory of describability developed ... in the present work yields a very interesting new view of the notion of randomness.' J T Schwartz Amazon back |
| Cohen, Paul J, Set Theory and the Continuum Hypothesis, Benjamin/Cummings 1966-1980 Preface: 'The notes that follow are based on a course given at Harvard University, Spring 1965. The main objective was to give the proof of the independence of the continuum hypothesis [from the Zermelo-Fraenkel axioms for set theory with the axiom of choice included]. To keep the course as self contained as possible we included background materials in logic and axiomatic set theory as well as an account of Goedel's proof of the consistency of the continuum hypothesis. ..' (i) Amazon back |
| Davis, Martin, Computability and Unsolvability, Dover 1982 Preface: 'This book is an introduction to the theory of computability and non-computability ususally referred to as the theory of recursive functions. The subject is concerned with the existence of purely mechanical procedures for solving problems. ... The existence of absolutely unsolvable problems and the Goedel incompleteness theorem are among the results in the theory of computability that have philosophical significance.' Amazon back |
| Feferman, Solomon, and John W Dawson, Stephen C Kleene, Gregory H Moore, Robert M Solovay, Jean van Heijenoort (editors), Kurt Goedel: Collected Works Volume 1 Publications 1929-1936, Oxford UP 1986 Jacket: 'Kurt Goedel was the most outstanding logician of the twentieth century, famous for his work on the completeness of logic, the incompleteness of number theory and the consistency of the axiom of choice and the continuum hypotheses. ... The first volume of a comprehensive edition of Goedel's works, this book makes available for the first time in a single source all his publications from 1929 to 1936, including his dissertation. ...' Amazon back |
| Hilbert, David, and W. Ackermann, Lewis M. Hammond (Translator), George G. Leckie (Translator), F. Steinhardt (Translator), Robert E. Luce (Editor), Principles of Mathematical Logic, American Mathematical Society A classic. 'Brief though it is, Priniciples manages to cover not only the usual topics (sentential calculus, first-order predicate calculus, completeness, decidability), but also: the monadic predicate calculus in relation to Aristotelian logic; second-order logic; set theory and the Fregean concept of number; and the theory of types (logics of higher order). You might say that Hilbert covers the same ground in 160 pages that Russell and Whitehead labor over for 3 volumes. The bottom line: a treat for anyone interested in logic, especially in the period from Frege to Godel.' A reader from Ithaca. Amazon back |
Papers
| Turing, Alan, "On Computable Numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2, 42, 12 November 1937, page 230-265. 'The "computable" numbers maybe described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost as easy to define and investigate computable functions of an integrable variable or a real or computable variable, computable predicates and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the rewlations of the computable numbers, functions and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine'. back |
Links
| Alan Turing On Computable Numbers, with an application to the Entscheidungsproblem back |
| Erich Friedman Wilhelm Ackermann 'Among Ackermann's later work there are consistency proofs for set theory, full arithmetic , and type free logic. He also gave a new axiomatization of set theory in 1956, and wrote the book Solvable cases of the decision problem in 1954.' back |
| Jeremy Gray The Hilbert Problems, 1900-2000 'In 1900 David Hilbert went to the second International Congress of Mathematicians in Paris to give an invited paper. He spoke on The Problems of Mathematics, to such effect that Hermann Weyl later referred to anyone who solved one of the 23 problems that Hilbert presented as entering the honours class of mathematicians. Throughout the 20th century the solution of a problem was the occasion for praise and celebration.' The original version of this article, including further photos, appeared in the Newsletter 36 of the European Mathematical Society 2000, 10-13. back |
| Kurt Goedel 1 On formally undecidable propositions of Principia Mathematica and related systems, I The classic paper, part I. back |
| Stanley Burris Grundzuge der theoretischen Logik: Hilbert and Ackermann Hilbert and Ackermann's 1928 Logic Book. '... They follow Principia in the axiomatization of the propositional calculus, using the work of Bernays (1926) to reduce the list of axioms from 5 to 4. Turning to the questions associated with the axiomatic method (Theoretical Logic, p. 29) they write that "the most important of the questions which arise are those of consistency, independence and completeness." ... The completeness result is the strong version, namely that adding any non-tautology to the axioms permits the derivation of a contradiction, and hence the derivation of all propositional formulas.' back |
Click on an "Amazon" link in the booklist at the foot of the page to buy the book, see more details or search for similar items
Related sites:
Concordat Watch
Revealing Vatican attempts to propagate its religion by international treaty
