×

Applicable mathematics in a minimal computational theory of sets. (English) Zbl 1454.03064

Summary: In previous papers on this project a general static logical framework for formalizing and mechanizing set theories of different strength was suggested, and the power of some predicatively acceptable theories in that framework was explored. In this work we first improve that framework by enriching it with means for coherently extending by definitions its theories, without destroying its static nature or violating any of the principles on which it is based. Then we turn to investigate within the enriched framework the power of the minimal (predicatively acceptable) theory in it that proves the existence of infinite sets. We show that that theory is a computational theory, in the sense that every element of its minimal transitive model is denoted by some of its closed terms. (That model happens to be the second universe in Jensen’s hierarchy.) Then we show that already this minimal theory suffices for developing very large portions (if not all) of scientifically applicable mathematics. This requires treating the collection of real numbers as a proper class, that is: a unary predicate which can be introduced in the theory by the static extension method described in the first part of the paper.

MSC:

03E30 Axiomatics of classical set theory and its fragments
03B35 Mechanization of proofs and logical operations

References:

[1] P. Aczel and M. Rathjen. Notes on constructive set theory. Technical Report 40, Mittag-Leffler, 2001.
[2] L. V. Ahlfors. Complex analysis. McGraw-Hill Book Co., Oliver and Boyd Ltd., 1964.
[3] J. Avigad and J. Harrison. Formally verified mathematics. Communications of the ACM, 57(4):66–75, 2014.
[4] A. Avron. Transitive closure and the mechanization of mathematics. In Thirty Five Years of Automating Mathematics, pages 149–171. Springer, 2003.
[5] A. Avron. Constructibility and decidability versus domain independence and absoluteness. Theoretical Computer Science, 394(3):144–158, 2008. · Zbl 1134.03025
[6] A. Avron. A framework for formalizing set theories based on the use of static set terms. In A. Avron, · Zbl 1133.03342
[7] A. Avron. A new approach to predicative set theory. In R. Schindler, editor, Ways of Proof Theory, pages 31–63. Onto Series in Mathematical Logic, Verlag, 2010. · Zbl 1244.03137
[8] A. Avron and L. Cohen. Formalizing scientifically applicable mathematics in a definitional framework. Journal of Formalized Reasoning, 9(1):53–70, 2016. · Zbl 1451.68333
[9] A. Avron, F. Honsell, I. A. Mason, and R. Pollack. Using typed lambda calculus to implement formal systems on a machine. Journal of Automated Reasoning, 9:309–354, 1992. · Zbl 0784.68072
[10] A. Avron, S. Lev, and N. Levy. Safety, absoluteness, and computability. 2018. To appear.
[11] A. Beckmann, S. R. Buss, and SD. Friedman. Safe recursive set functions. The Journal of Symbolic Logic, 80(3):730–762, 2015. · Zbl 1357.03075
[12] M. J. Beeson. Foundations of constructive mathematics: Metamathematical studies, volume 6. Springer Science & Business Media, 2012. · Zbl 0565.03028
[13] J. J. J. Campbell, J. C. G. Dos Reis, P. S. M. Wenzel, and V. Sorge, editors. Intelligent Computer Mathematics. Springer, 2008.
[14] D. Cantone, E. Omodeo, and A. Policriti. Set theory for computing: from decision procedures to declarative programming with sets. Springer, 2001. · Zbl 0981.03056
[15] D. Cantone, E. G. Omodeo, and J. T. Schwartz. Computational Logic and Set Theory: Applying Formalized Logic to Analysis. Springer, 2011. · Zbl 1246.03006
[16] A. Chlipala. Certified Programming with Dependent Types. MIT Press, Cambridge, MA, 2013. · Zbl 1288.68001
[17] L. Cohen and A. Avron. The middle ground–ancestral logic. Synthese, pages 1–23, 2015.
[18] R. L. Constable, S. F. Allen, M. Bromley, R. Cleaveland, et al. Implementing mathematics with the Nuprl proof development system. Prentice Hall, 1986.
[19] J. Corcoran, W. Hatcher, and J. Herring. Variable binding term operators. Mathematical Logic Quarterly, 18(12):177–182, 1972. · Zbl 0257.02013
[20] K. Devlin. Constructibility, volume 6 of perspectives in mathematical logic, 1984. · Zbl 0542.03029
[21] S. Feferman. Systems of predicative analysis. The Journal of Symbolic Logic, 29(01):1–30, 1964. · Zbl 0134.01101
[22] S. Feferman. Systems of predicative analysis, II: Representations of ordinals. The Journal of Symbolic Logic, 33(02):193–220, 1968. · Zbl 0162.02201
[23] S. Feferman. Why a little bit goes a long way: Logical foundations of scientifically applicable mathematics. In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, pages 442–455. JSTOR, 1992.
[24] S. Feferman. Operational set theory and small large cardinals. Information and Computation, 207(10):971 – 979, 2009. · Zbl 1183.03044
[25] A. A. Fraenkel, Y. Bar-Hillel, and A. Levy. Foundations of set theory. Elsevier, 1973. · Zbl 0248.02071
[26] H. Friedman. Set theoretic foundations for constructive analysis. Annals of Mathematics, 105(1):pp. 1–28, 1977. · Zbl 0353.02014
[27] R. O. Gandy. Set-theoretic functions for elementary syntax, volume 13, Part II of Proc. Symp. in Pure Math, pages 103–126. AMS, Providence, Rhode Island, 1974. · Zbl 0323.02067
[28] M. Hallett. Cantorian set theory and limitation of size. Clarendon Press Oxford, 1984. · Zbl 0656.03030
[29] R. Harper, F. Honsell, and Plotkin G. A framework for defining logics. Journal of the Association for Computing Machinery, 40:143–184, 1993. · Zbl 0778.03004
[30] K. Hrbacek and T. Jech. Introduction to Set Theory, Revised and Expanded, volume 220. Crc Press, 1999. · Zbl 1045.03521
[31] G. Jäger and R. Zumbrunnen. Explicit mathematics and operational set theory: Some ontological comparisons. The Bulletin of Symbolic Logic, 20(3):275–292, 2014. · Zbl 1345.03112
[32] R. B. Jensen. The fine structure of the constructible hierarchy. Annals of Mathematical Logic, 4(3):229– 308, 1972. · Zbl 0257.02035
[33] F. D. Kamareddine, editor. Thirty five years of automating mathematics, volume 28. Springer, 2003. · Zbl 1055.68002
[34] A. Levy. Basic set theory perspectives in mathematical logic. Berlim: Spring, 1979. · Zbl 0404.04001
[35] R. M. Martin. A homogeneous system for formal logic. The Journal of Symbolic Logic, 8(1):pp. 1–23, 1943. · Zbl 0060.02105
[36] A.R.D. Mathias, N.J. Bowler, et al. Rudimentary recursion, gentle functions and provident sets. Notre Dame Journal of Formal Logic, 56(1):3–60, 2015. · Zbl 1371.03061
[37] N. Megill. Metamath: A Computer Language for Pure Mathematics. Elsevier Science, 1997.
[38] J. Myhill. Constructive set theory. The Journal of Symbolic Logic, 40(03):347–382, 1975. · Zbl 0314.02045
[39] T. Nipkow, L. C. Paulson, and M. Wenzel. Isabelle/HOL: a proof assistant for higher-order logic, volume 2283. Springer, 2002. · Zbl 0994.68131
[40] E. G. Omodeo, D. Cantone, A. Policriti, and J. T. Schwartz. A computerized referee. In O. Stock and M. Schaerf, editors, Reasoning, Action and Interaction in AI Theories and Systems: Essays Dedicated to Luigia Carlucci Aiello, pages 117–139. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
[41] R. H. Risch. Algebraic properties of the elementary functions of analysis. American Journal of Mathematics, 101(4):743–759, 1979. · Zbl 0438.12016
[42] P. Rudnicki. An overview of the mizar project. In Proceedings of the 1992 Workshop on Types for Proofs and Programs, pages 311–330, 1992.
[43] S. Shapiro. Foundations without Foundationalism: A Case for Second-Order Logic: A Case for SecondOrder Logic. Oxford University Press, 1991. · Zbl 0732.03002
[44] S. G. Simpson. Subsystems of second order arithmetic, volume 1. Cambridge University Press, 2009. · Zbl 1181.03001
[45] N. Weaver. Analysis in J2. arXiv preprint math/0509245, 2005.
[46] H. Weyl. Das Kontinuum: Kritische Untersuchungen über die Grundlagen der Analysis. W. de Gruyter, 1932. · Zbl 0005.15403
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.