Abstract
We present a new unified framework for formalizations of axiomatic set theories of different strength, from rudimentary set theory to full ZF. It allows the use of set terms, but provides a static check of their validity. Like the inconsistent “ideal calculus” for set theory, it is essentially based on just two set-theoretical principles: extensionality and comprehension (to which we add ∈-induction and optionally the axiom of choice). Comprehension is formulated as: \(x\in\{x\mid\varphi\}\leftrightarrow\varphi\), where {x|ϕ} is a legal set term of the theory. In order for {x|ϕ} to be legal, ϕ should be safe with respect to {x}, where safety is a relation between formulas and finite sets of variables. The various systems we consider differ from each other mainly with respect to the safety relations they employ. These relations are all defined purely syntactically (using an induction on the logical structure of formulas). The basic one is based on the safety relation which implicitly underlies commercial query languages for relational database systems (like SQL).
Our framework makes it possible to reduce all extensions by definitions to abbreviations. Hence it is very convenient for mechanical manipulations and for interactive theorem proving. It also provides a unified treatment of comprehension axioms and of absoluteness properties of formulas.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ackermann, W.: Zur Axiomatik der Mengenlehre. Mathematische Annalen 131, 336–345 (1956)
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Avron, A.: Transitive closure and the mechanization of mathematics. In: Kamareddine, F. (ed.) Thirty Five Years of Automating Mathematics, pp. 149–171. Kluwer Academic Publishers, Dordrecht (2003)
Avron, A.: Safety signatures for first-order languages and their applications. In: Hendricks, et al. (eds.) First-Order Logic Revisited, pp. 37–58. Logos Verlag, Berlin (2004)
Avron, A.: Formalizing set theory as it is actually used. In: Asperti, A., Bancerek, G., Trybulec, A. (eds.) MKM 2004. LNCS, vol. 3119, pp. 32–43. Springer, Heidelberg (2004)
Avron, A.: Constructibility and decidability versus domain independence and absluteness. Theoretical Computer Science (2007), doi:10.1016/j.tcs.2007.12.008
Cantone, D., Omodeo, E., Policriti, A.: Set Theory for Computing. Springer, Heidelberg (2001)
Devlin, K.J.: Constructibility. Perspectives in Mathematical Logic. Springer, Heidelberg (1984)
Di Paola, R.A.: The recursive unsolvability of the decision problem for the class of definite formulas. J. ACM 16(2), 324–327 (1969)
Fraenkel, A., Bar-Hillel, Y., Levy, A.: Foundations of Set Theory. North-Holland, Amsterdam (1973)
Feferman, S.: Finitary inductively presented logics. In: Logic Colloquium 1988, pp. 191–220. North-Holland, Amsterdam (1989)
Gandy, R.O.: Set-theoretic functions for elementary syntax. In: Axiomatic Set Theory, Part 2, pp. 103–126. AMS, Providence, Rhode Island (1974)
Gentzen, G.: Neue fassung des widerspruchsfreiheitsbeweises für die reine zahlentheorie. Forschungen zur Logik, N.S. (4), 19–44 (1938)
Immerman, N.: Languages which capture complexity classes. In: 15th Symposium on Theory of Computing, Association for Computing Machinery, pp. 347–354 (1983)
Jensen, R.B.: The fine structure of the constructible hierarchy. Annals of Mathematical Logic 4, 229–308 (1972)
Hallett, M.: Cantorian Set Theory and Limitation of Size. Clarendon Press, Oxford (1984)
Kunen, K.: Set Theory, An Introduction to Independence Proofs. North-Holland, Amsterdam (1980)
Levy, A.: Basic Set Theory. Springer, Heidelberg (1979)
Reinhardt, W.R.: Ackermann’s set theory Equals ZF. Annals of Mathematical Logic 2, 189–249 (1970)
Shoenfield, J.R.: Mathematical Logic. Addison-Wesley, Reading (1967)
Shoenfield, J.R.: Axioms of set theory. In: Barwise, J. (ed.) Handbook of Mathematical Logic, North-Holland, Amsterdam (1977)
Shapiro, S.: Foundations Without Foundationalism: A Case for Second-order Logic. Oxford University Press, Oxford (1991)
Smullyan, R.M.: The Incompleteness Theorems. Oxford University Press, Oxford (1992)
Ullman, J.D.: Principles of Database and Knowledge-Base Systems. Computer Science Press (1988)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Avron, A. (2008). A Framework for Formalizing Set Theories Based on the Use of Static Set Terms. In: Avron, A., Dershowitz, N., Rabinovich, A. (eds) Pillars of Computer Science. Lecture Notes in Computer Science, vol 4800. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78127-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-78127-1_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78126-4
Online ISBN: 978-3-540-78127-1
eBook Packages: Computer ScienceComputer Science (R0)