Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T04:04:10.745Z Has data issue: false hasContentIssue false

Incompleteness in a General Setting

Published online by Cambridge University Press:  15 January 2014

John L. Bell*
Affiliation:
Department of Philosophy, University of Western Ontario, CanadaE-mail: [email protected]

Extract

Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel's theorems without getting mired in syntactic or computational details. One of the most important of these efforts was made by Löb [8] in connection with his analysis of sentences asserting their own provability. Löb formulated three conditions (now known as the Hilbert-Bernays-Löb derivability conditions), on the provability predicate in a formal system which are jointly sufficient to yield the Gödel's second incompleteness theorem for it. A key role in Löb's analysis is played by (a special case of) what later became known as the diagonalization or fixed point property of formal systems, a property which had already, in essence, been exploited by Gödel in his original proofs of the incompleteness theorems. The fixed point property plays a central role in Lawvere's [7] category-theoretic account of incompleteness phenomena (see also [10]).

Type
Articles
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Bell, John L., Toposes and local set theories, Clarendon Press, Oxford, 1988.Google Scholar
[2] Bell, John L., Set theory: Boolean-valued models and independence proofs, Clarendon Press, Oxford, 2005.Google Scholar
[3] Bell, John L. and Machover, M., A course in mathematical logic, North-Holland, 1977.Google Scholar
[4] Boolos, G., Gödel's second incompleteness theorem explained in words of one syllable, Mind, vol. 103 (1994), no. 409, pp. 13.Google Scholar
[5] Boolos, G., The logic of provability, Cambridge University Press, 1995.Google Scholar
[6] Boolos, G. and Jeffrey, R., Computability and logic, Cambridge University Press, 1974.Google Scholar
[7] Lawvere, F. W., Diagonal arguments and cartesian closed categories. Category theory, homology theory and their applications, II, Battelle Institute Conference, Seattle, Washington, 1968, Springer, Berlin, 1969, pp. 134145.Google Scholar
[8] Löb, M. H., Solution of a problem of Leon Henkin, The Journal of Symbolic Logic, vol. 20 (1955), pp. 115–118.Google Scholar
[9] Smorynski, C., The incompleteness theorems, Handbook of mathematical logic (Barwise, J., editor), North-Holland, 1977, pp. 821866.Google Scholar
[10] Yanofsky, N., A universal approach to self-referential paradoxes, incompleteness and fixed points, this Bulletin, vol. 9 (2003), no. 3, pp. 362386.Google Scholar