Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-29T16:58:39.752Z Has data issue: false hasContentIssue false
  • English
  • Français

On mathematical instrumentalism*

Published online by Cambridge University Press:  12 March 2014

Patrick Caldon  and
Aleksandar Ignjatović
Patrick Caldon
Affiliation:
School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia National Ict Australia, Sydney Laboratory, AustraliaE-mail:, [email protected]
Aleksandar Ignjatović
Affiliation:
School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia National Ict Australia, Sydney Laboratory, AustraliaE-mail:, [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we devise some technical tools for dealing with problems connected with the philosophical view usually called mathematical instrumentalism. These tools are interesting in their own right, independently of their philosophical consequences. For example, we show that even though the fragment of Peanos Arithmetic known as IΣ1 is a conservative extension of the equational theory of Primitive Recursive Arithmetic (PRA). IΣ1 has a super-exponential speed-up over PRA. On the other hand, theories studied in the Program of Reverse Mathematics that formalize powerful mathematical principles have only polynomial speed-up over IΣ1.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 3 , September 2005 , pp. 778 - 794
Copyright
Copyright © Association for Symbolic Logic 2005

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

*

This is a revised excerpt from the second author's Ph.D. Thesis submitted at the University of California at Berkeley in 1990. The author is grateful to his adviser. Professor Jack Silver, for his support, many helpful discussions and for sharing his insights, to Professor Charles Chihara for discussions and encouragements, to the referees for many most useful comments which reshaped the paper.

References

REFERENCES

[1]Avigad, J., Formalizing forcing arguments in subsystems of second-order arithmetic, Annals of Pure and Applied Logic, vol. 82 (1996), pp. 165–191.CrossRefGoogle Scholar
[2]Brown, D. K., Subsystems of second order arithmetic, Ph.D. thesis, Pennsylvania State University, 1987.Google Scholar
[3]Buss, S., Bounded Arithmetic, Bibliopolis, 1986.Google Scholar
[4]Enderton, H., A Mathematical Introduction to Logic, Academic Press, 1972.Google Scholar
[5]Feferman, S., Systems of predicative analysis, this Journal, vol. 29 (1964), pp. 1–30.Google Scholar
[6]Hájek, P., On interpretability of theories containing arithmetic, II, Commentationes Mathematical Universitatis Carolinae, vol. 22 (1981), pp. 667–688.Google Scholar
[7]Hájek, P., Interpretability and fragments of arithmetic, Arithmetic, Proof Theory, and Computational Complexity (Clote, P. and Krajíček, J., editors), Oxford, 1993, pp. 185–196.Google Scholar
[8]Hilbert, D. and Bernays, P., Grundlagen der Mathematik I, II, 2. Auflage, Springer, Berlin, 1968/1970.Google Scholar
[9]Ignjatović, A., Fragments of first- and second-order arithmetic and length of proofs, Ph.D. thesis, University of California at Berkeley, Berkeley, California, 1990.Google Scholar
[10]Ignjatović, A., Hilbert's program and the ω-rule, this Journal, vol. 59 (1994), no. 1, pp. 322–343.Google Scholar
[11]Isaacson, D., Arithmetical truth and hidden higher-order concepts, Logic Colloquium '85, Paris Logic Group, North Holland, 1987.Google Scholar
[12]Kreisel, G., What can be done for Mathematical Logic, Bertrand Russell: Philosopher of the Century (Schoenman, R., editor), Allen and Unwin, London, 1967. pp. 273–303.Google Scholar
[13]Paris, J. and Dimitracopulos, C., A note on undefinability of cuts, this Journal, vol. 48 (1983), pp. 564–569.Google Scholar
[14]Pudlák, P., Cuts, consistency statements and interpretations, this Journal, vol. 50 (1985), pp. 423–441.Google Scholar
[15]Pudlák, P., On the length of proofs offinitistic consistency statements in first-order theories, Logic Colloquium '84 (Paris, J. B., Wilkie, A. J., and Wilmers, G. M., editors), North-Holland, 1986.Google Scholar
[16]Sieg, W., Fragments of arithmetic, Annals of Pure and Applied Logic, vol. 28 (1985). pp. 33–71.CrossRefGoogle Scholar
[17]Simpson, S. G., Partial realization of Hilbert'sprogram, this Journal, vol. 53 (1988), pp. 349–363.Google Scholar
[18]Simpson, S. G., Subsystems of second order arithmetic, Springer-Verlag, 1998.Google Scholar
[19]Simpson, S. G. and Smith, R. L., Factorization of polynomials and Σ10-induction, Annals of Pure and Applied Logic, vol. 31 (1986), pp. 289–306.CrossRefGoogle Scholar
[20]Solovay, R., Letter to P. Hájek, see also [6] and [13].Google Scholar
[21]Tait, W. W., Finitism, Journal of Philosophy, vol. 78 (1981), pp. 524–546.CrossRefGoogle Scholar
[22]Takeuti, G., Proof Theory, 2nd ed., North-Holland, 1987.Google Scholar
[23]Wainer, S. S., Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy, this Journal, vol. 37 (1972), pp. 281–292.Google Scholar