Paradox and potential infinity. (English) Zbl 1277.03059

The article describes some models for systems of predicative arithmetic inside intuitionistic set theory to show the crucial behaviours of potentially infinite sets in the foundational literature back to Aristotle. A discussion of the strictly related Church’s thesis concludes the paper.
In detail, starting from Zeno’s paradox about the impossibility of movement and the way Aristotle confuted Zeno’s argument, the idea of potential infinity is introduced. Formalising Zeno’s argument, the core in the reasoning is reduced to prove the existence of a set \(D\) which is, at the same time, not finite and not infinite – an obvious falsity in classical mathematics, but possible in the intuitionistic framework.
Using a variant of realizability, the formal machinery to synthesize \(D\)-like sets within the domain of intuitionistic set theory is constructed. Then, by providing a sensibly positive definition of finite and infinite sets, the existence of a third class of potentially infinite sets becomes clear, as the classification is not exhaustive. The article explores in some depth the consequences of this fact with respect to many philosophical approaches to mathematical infinity, culminating with an analysis of Zeno’s paradox.
Then, the author analyses how the very same pattern (not finite implies infinite) appears in Bolzano and Chomsky, leading to fallacies in their way of reasoning, at least from the point of view of constructive mathematics.
Since, under the realizability interpretation, each potentially infinite set provides a natural model of predicative arithmetic, the retraceable sets playing a distinguished role, it is natural to ask whether such models are special. In the paper, the author proves that, apart from \(\omega\), the set of ordinary natural numbers, Zenonian numbers provide the only fully inductive number structures that exist in the set-theoretic universe under Kleene’s number realizability.
Finally, the article proves that the only functions represented in potentially infinite, retraceable realizability structures for predicative arithmetic are recursive functions with weakly bounded ranges, directly relating to the weak Church’s thesis.


03F55 Intuitionistic mathematics
03A05 Philosophical and critical aspects of logic and foundations
03F30 First-order arithmetic and fragments
Full Text: DOI


[1] Aristotle (1984). Physics. In J. Barnes (Ed.), The complete works of Aristotle (Vol. 1, pp. 315–446). Bollingen Series LXXI. 2. Princeton, NJ: Princeton University Press. [References by Bekker number].
[2] Beeson, M. (1985). Foundations of constructive mathematics. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge (Vol. 6, xxiii+466). Berlin, DE: Springer-Verlag. · Zbl 0565.03028
[3] Bolzano, B. (1851). Paradoxion des Unendlichen (xii+134 pp.). Leipzig, DE: C. H. Reclam. Reprinted as Paradoxes of the infinite (189 pp.). D. A. Steele (tr.) New Haven: Yale University Press (1950). [Translations of passages from this work are by the author].
[4] Brouwer, L. E. J. (1975). Points and spaces. In A. Heyting (Ed.), L. E. J. Brouwer collected works. Philosophy and foundations of mathematics (Vol. 1, pp. 522–538). Amsterdam, NL: North-Holland Publishing Company.
[5] Chomsky, N. (1981). On the representation of form and function. The linguistic review (Vol. 1, pp. 3–40).
[6] Crossley, J., & Nerode, A. (1974). Combinatorial functors. Ergebnisse der mathematik und ihrer Grenzgebiete. Band 81 (viii+146). New York, NY: Springer-Verlag. · Zbl 0283.02036
[7] Dedekind, R. (1888). Was sind und was sollen die Zahlen? (xv + 58). Braunsweig, DE: Friedrich Vieweg und Sohn. Reprinted as The nature and meaning of numbers. Essays on the theory of numbers (pp. 29–115). W. Beman (tr.) New York: Dover Publications (1963).
[8] Dekker, J., & Myhill, J. (1960). Recursive equivalence types (Vol. 3, number 3, pp. 67–214). New series. University of California Publications in Mathematics. · Zbl 0249.02021
[9] Du Bois-Reymond, P. (1882). Die allgemeine Funktionentheorie (xiv+292). Tübingen, DE: Verlag der H. Laupp’schen Buchhandlung. [Translations from this work are by the author].
[10] Dummett, M. (1977). Elements of intuitionism (1st ed., xii+467). Oxford, UK: Clarendon Press. (Second Edition (2000)). · Zbl 0358.02032
[11] Gibson, C. G. (1971). On the definition of an infinite species. Nieuw Archief voor Wiskunde (Third Series, no. 19, pp. 196–197). · Zbl 0234.02019
[12] Grayson, R. (1978). Intuitionistic set theory (v+117). D. Phil. Dissertation. Oxford, UK: University of Oxford.
[13] Heyting, A. (1930). Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften. Physikalisch- mathematische Klasse (pp. 42–56). · JFM 56.0823.01
[14] Heyting, A. (1930). Die formalen Regeln der intuitionistischen Mathematik I. Sitzungsberichte der Preussischen Akademie der Wissenschaften. Physikalisch- mathematische Klasse (pp. 57–71). · JFM 56.0823.01
[15] Heyting, A. (1930). Die formalen Regeln der intuitionistischen Mathematik II. Sitzungsberichte der Preussischen Akademie der Wissenschaften. Physikalisch-mathematische Klasse (pp. 158–169). · JFM 56.0823.01
[16] Heyting, A. (1976). Intuitionism. An introduction (3rd revised ed., ix+137). Amsterdam, NL: North-Holland Publishing Company.
[17] Kant, I. (1929). Critique of pure reason (xiii+681). N. K. Smith (tr.) New York, NY: St. Martin’s Press.
[18] Kleene, S. C. (1945). On the interpretation of intuitionistic number theory. The Journal of Symbolic Logic, 10(4), 109–124. · Zbl 0063.03260
[19] McCarty, C. (1984). Realizability and recursive mathematics (281 pp.). Pittsburgh, PA: Department of Computer Science, Carnegie-Mellon University. Report number CMU-CS-84-131. · Zbl 0558.03031
[20] McCarty, C. (1988). Markov’s principle, isols, and Dedekind-finite sets. The Journal of Symbolic Logic, 53(4), 1042–1069. · Zbl 0671.03037
[21] McCarty, C. (2006). Thesis and variations. In A. Olszewski, J. Wolenski, & R. Janusz (Eds.), Church’s thesis after 70 years (pp. 281–303). Frankfurt, DE: Ontos Verlag. · Zbl 1105.03009
[22] McCarty, C. (2008). The new intuitionism. In M. van Atten, et al. (Eds.), One hundred years of intuitionism (1907–2007) (pp. 37–49). Boston, MA: Birkhuser.
[23] Minio, R. (1974). Finite and countable sets in intuitionistic analysis (35 pp.). M.Sc. dissertation. Oxford, UK: University of Oxford.
[24] Nelson, E. (1986). Predicative arithmetic. Mathematical notes (Number 32, viii+189). Princeton, NJ: Princeton University Press.
[25] Rogers, H. (1967). Theory of recursive functions and effective computability (xix+482). New York: McGraw-Hill Publishing Company. · Zbl 0183.01401
[26] Thomson, J. (1954). Tasks and super-tasks. Analysis, 15(1), 1–13.
[27] Troelstra, A. (1967). Finite and infinite in intuitionistic mathematics. Compositio Mathematica, 18(1–2), 94–116. · Zbl 0163.00501
[28] Troelstra, A., & D. van Dalen (1988). Constructivism in mathematics: An introduction (Vol. I, xx+342+XIV). Amsterdam, NL: North-Holland. · Zbl 0653.03040
[29] Wittgenstein, L. (1976). In C. Diamond (Ed.), Wittgenstein’s lectures on the foundations of mathematics. Cambridge, 1939 (300 pp.). Ithaca, NY: Cornell University Press.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.