Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-27T19:30:42.127Z Has data issue: false hasContentIssue false

Reflecting on incompleteness1

Published online by Cambridge University Press:  12 March 2014

Solomon Feferman*
Affiliation:
Department of Mathematics, Stanford University, Stanford, California 94305

Extract

To what extent can mathematical thought be analyzed in formal terms? Gödel's theorems show the inadequacy of single formal systems for this purpose, except in relatively restricted parts of mathematics. However at the same time they point to the possibility of systematically generating larger and larger systems whose acceptability is implicit in acceptance of the starting theory. The engines for that purpose are what have come to be called reflection principles. These may be iterated into the constructive transfinite, leading to what are called recursive progressions of theories. A number of informative technical results have been obtained about such progressions (cf. Feferman [1962], [1964], [1968] and Kreisel [1958], [1970]). However, for some years I had hoped to give a more realistic and perspicuous finite generation procedure. This was first done in a rather special way in Feferman [1979] for the characterization of predicativity, which may be regarded as that part of mathematical thought implicit in our acceptance of elementary number theory. What is presented here is a new and simple notion of the reflective closure of a schematic theory which can be applied quite generally.

Two examples of schematic theories in the sense used here are versions of Peano arithmetic and Zermelo set theory.

Type
Survey/expository paper
Copyright
Copyright © Association for Symbolic Logic 1991

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.)

Footnotes

1

Retiring Presidential Address. For the background to this paper and acknowledgements, see the end of the Introduction, below.

References

REFERENCES

Aczel, P. [1977] The strength of Martin-Löfs intuitionistic type theory with one universe, Proceedings of the symposium on mathematical logic (Oulo, 1974), Report No. 2, Department of Philosophy, University of Helsinki, pp. 132.Google Scholar
Aczel, P. [1980] Frege structures and the notions of proposition, truth and set, The Kleene symposium, North-Holland, Amsterdam, pp. 3159.CrossRefGoogle Scholar
Beeson, M. [1985] Foundations of constructive mathematics, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Bernays, P. [1976] On the problem of schemata of infinity in axiomatic set theory, Sets and classes. On the work of Paul Bernays, North-Holland, Amsterdam, pp. 121172.CrossRefGoogle Scholar
Buchholz, W., Feferman, S., Pohlers, W. and Sieg, W. [1981] Iterated inductive definitions and subsystems of analysis: Recent proof-theoretical studies, Lecture Notes in Mathematics, vol. 897, Springer-Verlag, Berlin.Google Scholar
Cantini, A. [1989] Notes on format theories of truth, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 35, pp. 3597.CrossRefGoogle Scholar
Cantini, A. [1990] A theory of formal truth arithmetically eguivalent to ID1, this Journal, vol. 55, pp. 244259.Google Scholar
Church, A. [1956] Introduction to mathematical logic. Vol. I, Princeton University Press, Princeton, New Jersey.Google Scholar
Feferman, S. [1960] Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae, vol. 49, pp. 49–35.CrossRefGoogle Scholar
Feferman, S. [1962] Transfinite recursive progressions of axiomatic theories, this Journal, vol. 27, pp. 259316.Google Scholar
Feferman, S. [1964] Systems of predicative analysis, this Journal, vol. 29, pp. 130.Google Scholar
Feferman, S. [1968] Systems of predicative analysis. II: Representations of ordinals, this Journal, vol. 33, pp. 193220.Google Scholar
Feferman, S. [1979] A more perspicuous formal system for predicativity, Konstruktionen versus Positionen. I, Walter de Gruyter, Berlin, pp. 6893.Google Scholar
Feferman, S. [1982] Inductively presented systems and the formalization of metamathematics, Logic Colloquium '80, North-Holland, Amsterdam, pp. 95128.Google Scholar
Feferman, S. [1984] Toward useful type-free theories. I, this Journal, vol. 49, pp. 75111.Google Scholar
Feferman, S. [1987] Proof theory: a personal report, Appendix to Proof theory by Takeuti, G., 2nd ed., North-Holland, Amsterdam, pp. 447485.Google Scholar
Feferman, S. [1988] Hilbert's program relativized: proof-theoretical and foundational reductions, this Journal, vol. 53, pp. 364384.Google Scholar
Feferman, S. [1988a] Weyl vindicated: “Das Kontinuum” 70 years later, Temi e prospettive della logica e delta filosofia delta scienza contemporanee, CLUEB, Bologna, pp. 5993.Google Scholar
Feferman, S. [1989] Finitary inductively presented logics, Logic Colloquium '88, North-Holland, Amsterdam, pp. 191220.Google Scholar
Feferman, S. and Jäger, G. [1983] Choice principles, the bar rule, and iterated comprehension principles in analysis, this Journal, vol. 48, pp. 6370.Google Scholar
Feferman, S. and Sieg, W. [1981] Proof-theoretical equivalences between classical and constructive theories for analysis, in Buchholz et al. [1981], pp. 78142.CrossRefGoogle Scholar
Friedman, H. [1970] Iterated inductive definitions and -AC, Intuitionism and proof theory, North-Holland, Amsterdam, pp. 435442.Google Scholar
Friedman, H. and Sheard, M. [1987] An axiomatic approach to self-referential truth, Annals of Pure and Applied Logic, vol. 33, pp. 33–1.CrossRefGoogle Scholar
Gandy, R. O. [1974] Set-theoretic functions for elementary syntax, in Axiomatic set theory, Proceedings of Symposia in Pure Mathematics, vol. 13, Part II, American Mathematical Society, Providence, Rhode Island, pp. 103126.CrossRefGoogle Scholar
Gödel, K. [1931] Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I, Monatshefte für Mathematik und Physik, vol. 38, pp. 173198 (reprinted with English translation in Gödel [1986], pp. 144–195).Google Scholar
Gödel, K. [1986] Collected Works. Vol. I: Publications 1929–1936, Oxford University Press, New York.Google Scholar
Gödel, K. [1990] Collected Works. Vol. II: Publications 1938–1974, Oxford University Press, New York.Google Scholar
Hilbert, D. and Ackermann, W. [1928] Grundzüge der theoretischen Logik, Springer-Verlag, Berlin.Google Scholar
Hilbert, D. and Ackermann, W. [1938] Grundzüge der theoretischen Logik, Springer-Verlag, Berlin, 2nd rev. ed.CrossRefGoogle Scholar
Hilbert, D. and Bernays, P. [1934] Grundlagen der Mathematik. Vol. I, Springer-Verlag, Berlin.Google Scholar
Howard, W. [1972] A system of abstract constructive ordinals, this Journal, vol. 37, pp. 355374.Google Scholar
Jensen, R. B. and Karp, C. [1971] Primitive recursive set functions, Axiomatic set theory, Proceedings of Symposia in Pure Mathematics, vol. 13, Part I, American Mathematical Society, Providence, Rhode Island, pp. 143176.CrossRefGoogle Scholar
Kleene, S. C. [1959] Quantification of number-theoretic functions, Compositio Mathematica, vol. 14, pp. 1423.Google Scholar
Kreisel, G. [1958] Ordinal logics and the characterization of informal concepts of proof, Proceedings of the International Congress of Mathematicians (Edinburgh, 1958), Cambridge University Press, New York, 1960, pp. 289299.Google Scholar
Kreisel, G. [1970] Principles of proof and ordinals implicit in given concepts, Intuitionism and proof theory, North-Holland, Amsterdam, pp. 489516.Google Scholar
Kripke, S. [1975] Outline of a theory of truth, Journal of Philosophy, vol. 72, pp. 690716 (reprinted in Martin [1984], pp. 53–81).CrossRefGoogle Scholar
Martin, R. L. (editor) [1984] Recent essays on truth and the Liar paradox, Clarendon Press, Oxford.Google Scholar
Parsons, C. [1970] On a number-theoretic choice schema and its relation to induction, Intuitionism and proof theory, North-Holland, Amsterdam, pp. 459473.Google Scholar
Reinhardt, W. N. [1986] Some remarks on extending and interpreting theories with a partial predicate for truth, Journal of Philosophical Logic, vol. 15, pp. 15219.CrossRefGoogle Scholar
Schütte, K. [1965] Predicative well-orderings, Formal systems andrecursive functions, North-Holland, Amsterdam, pp. 279302.Google Scholar
Schütte, K. [1965a] Eine Grenze für die Beweisbarkeit der transfiniten Induktion in der verzweigten Typenlogik, Archh für Mathematische Logik und Grundlagenforschung, vol. 7, pp. 745.Google Scholar
Schütte, K. [1977] Proof theory, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Smoryński, C. [1977] The incompleteness theorems, Handbook of mathematical logic, North-Holland, Amsterdam, pp. 821865.CrossRefGoogle Scholar
Takeuti, G. [1965] A formalization of the theory of ordinal numbers, this Journal, vol. 30, pp. 295317.Google Scholar
Turing, A. [1939] Systems of logic based on ordinals, Proceedings of the London Mathematical Society, ser. 2, vol. 45, pp. 161228.CrossRefGoogle Scholar
van Fraassen, B. [1968] Presupposition, implication and self-reference, Journal of Philosophy, vol. 65, pp. 65135.CrossRefGoogle Scholar
van Heijenoort, J. (editor) [1967] From Frege to Gödel: A source book in mathematical logic, Harvard University Press, Cambridge, Massachusetts.Google Scholar
Visser, A. [1989] Semantics and the Liar paradox, Handbook of philosophical logic, vol. IV, Reidel, Dordrecht, pp. 617706.CrossRefGoogle Scholar