Abstract
Recently, Feferman and Hellman (and Aczel) showed how to establish the existence and categoricity of a natural number system by predicative means given the primitive notion of a finite set of individuals and given also a suitable pairing function operating on individuals. This short paper shows that this existence and categoricity result does not rely (even indirectly) on finite-set induction, thereby sustaining Feferman and Hellman's point in favor of the view that natural number induction can be derived from a very weak fragment of finite-set theory, so weak that finite-set induction is not assumed. Many basic features of finiteness fail to hold in these weak fragments, conspicuously the principle that finite sets are in one-one correspondence with a proper initial segments of a (any) natural number structure. In the last part of the paper, we propose two prima facie evident principles for finite sets that, when added to these fragments, entail this principle.
Similar content being viewed by others
REFERENCES
Feferman, S. and Hellman, G.: Predicative foundations of arithmetic, J. Philos. Logic 24(1) (1995), 1–17.
Feferman, S. and Hellman, G.: Challenges to predicative foundations of arithmetic, in G. Sher and R. Tieszen (eds), Between Logic and Intuition: Essays in Honor of Charles Parsons, Cambridge University Press, Cambridge, 1998.
Garcia, N.: New Foundations for Recursion Theory, PhD Thesis, Oxford University, Hilary Term, 1980.
Parsons, C.: The impredicativity of induction, in M. Detlefsen (ed.), Proof, Logic and Formalization, Routledge, 1992, pp. 139–161. Revised and expanded version of a 1983 paper.
Simpson, S.: Subsystems of Z 2 and reverse mathematics, in G. Takeuti (ed.), Proof Theory, North-Holland, Amsterdam, 1987, pp. 433–446.
Tarski, A.: Sur les ensembles finis, in S. Givant and R. McKenzie (eds), Alfred Tarski – Collected Works (Vol. 1), Birkhäuser, Basel 1986, pp. 67–117. First published in 1924.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ferreira, F. A Note on Finiteness in the Predicative Foundations of Arithmetic. Journal of Philosophical Logic 28, 165–174 (1999). https://doi.org/10.1023/A:1004377219147
Issue Date:
DOI: https://doi.org/10.1023/A:1004377219147