Abstract
The finitistic philosophy of mathematics, critical of referencing infinite totalities, has been associated from its inception with primitive recursion. That kinship was not initially substantiated, but is widely assumed, and is supported by Parson’s Theorem, which may be construed as equating finitistic reasoning with finitistic computing.
In support of identifying PR with finitism we build on the generic framework of [7] and articulate a finitistic theory of finite partial-structures, and a generic imperative programming language for modifying them, equally rooted in finitism. The theory is an abstract generalization of Primitive Recursive Arithmetic, and the programming language is a generic generalization of first-order recurrence (primitive recursion). We then prove an abstract form of Parson’s Theorem that links the two.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that we generate here all finite structures, not a special subset which is somehow related to primitive recursion.
- 2.
It is a special case of Concrete-function-choice above, but one for which we have a proof from the remaining axioms.
- 3.
Mints cites Parsons’ paper, but mentions his own earlier unpublished presentations.
References
Avigad, J.: Saturated models of universal theories. Ann. Pure Appl. Log. 118(3), 219–234 (2002)
Buss, S.: First-order proof theory of arithmetic. In: Buss, S.R. (ed.) Handbook of Proof Theory, pp. 79–148. Elsevier, Amsterdam (1998)
Euclid: Elements. Dover, New York (1956)
Ferreira, F.: A simple proof of Parsons’ theorem. Notre Dame J. Formal Log. 46(1), 83–91 (2005)
Hilbert, D.: Über das unendliche. Math. Ann. 95, 161–190 (1926)
Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, New York (1998). https://doi.org/10.1007/978-1-4612-0539-5
Leivant, D.: A theory of finite structures. Logical methods in computer science (2019, to appear). Preliminary version: arXiv.org:1808.04949 (2018)
Leivant, D., Marion, J.: Primitive recursion in the abstract. Mathematical structures in computer science (2019, to appear). Preliminary version under the title Implicit complexity via structure transformation, in arXiv:1802.03115 (2018)
Mayberry, J.: The Foundations of Mathematics in the Theory of Sets. Encyclopedia of Mathematics, vol. 82. Cambridge University Press, Cambridge (2000)
Meyer, A., Ritchie, D.: The complexity of loop programs. In: Proceedings of the 1967 22nd National Conference, New York, pp. 465–469 (1967)
Mints, G.: Quantifier-free and one-quantifier systems. J. Soviet Math. 1, 71–84 (1972)
Parsons, C.: On a number theoretic choice schema and its relation to induction. In: Intuitionism and Proof Theory, North-Holland, Amsterdam , pp. 459–473 (1970)
Parsons, C.: On n-quantier induction. J. Symb. Log. 37(3), 466–482 (1972)
Skolem, T.: Einige bemerkungen zur axiomatischen begründung der mengenlehre. In: Matematikerkongressen in Helsingfors Den femte skandinaviske matematikerkongressen (1922)
Tait, W.: Finitism. J. Philos. 78, 524–546 (1981)
Takahashi, M.: An induction principle in set theory I. Yokohama Math. J. 17, 53–59 (1969)
Takeuti, G.: Proof Theory. Amsterdam (1975)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Leivant, D. (2020). Finitism, Imperative Programs and Primitive Recursion. In: Artemov, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 2020. Lecture Notes in Computer Science(), vol 11972. Springer, Cham. https://doi.org/10.1007/978-3-030-36755-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-36755-8_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36754-1
Online ISBN: 978-3-030-36755-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)