Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-29T18:23:10.694Z Has data issue: false hasContentIssue false
  • English
  • Français

The axiom of elementary sets on the edge of Peircean expressibility

Published online by Cambridge University Press:  12 March 2014

Andrea Formisano ,
Eugenio G. Omodeo  and
Alberto Policriti
Andrea Formisano
Affiliation:
Dipartimento di Informatica, UniversitÀ di Laquila, Via Vetoio–Loc, Coppito, 67010 l'Aquila, ItalyE-mail:, [email protected]
Eugenio G. Omodeo
Affiliation:
Dipartimento di Matematica e Informatica, UniversitÀ di Trieste, Via Valerio, 12/B, 34127 Trieste, ItalyE-mail:, [email protected]
Alberto Policriti
Affiliation:
Dipartimento di Matematica e Informatica, UniversitÀ di Udine, Via Delle Scienze 206-Loc. Rizzi, 33100 Udine, ItalyE-mail:, [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Being able to state the principles which lie deepest in the foundations of mathematics by sentences in three variables is crucially important for a satisfactory equational rendering of set theories along the lines proposed by Alfred Tarski and Steven Givant in their monograph of 1987.

The main achievement of this paper is the proof that the ‘kernel’ set theory whose postulates are extensionality. (E), and single-element adjunction and removal. (W) and (L), cannot be axiomatized by means of three-variable sentences. This highlights a sharp edge to be crossed in order to attain an ‘algebraization’ of Set Theory. Indeed, one easily shows that the theory which results from the said kernel by addition of the null set axiom, (N), is in its entirety expressible in three variables.

Keywords

Weak set theoriesn-variable expressibilitypebble games
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 3 , September 2005 , pp. 953 - 968
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Barwise, J., On Moschovakis closure ordinals, this Journal, vol. 42 (1977), pp. 292–296.Google Scholar
[2]Dawar, A., Finite models and finitely many variables, Banach Center Publications, vol. 46, Institute of Mathematics, Polish Academy of Sciences, 1999.Google Scholar
[3]Ebbinghaus, H.-D. and Flum, J., Finite model theory, Perspectives in Mathematical Logic, Springer, 1999, Second revised and enlarged edition.Google Scholar
[4]Formisano, A., Omodeo, E. G., and Policriti, P., Three-variable statements of set-pairing, Theoretical Computer Science, vol. 322 (2004), no. 1, pp. 147–173.CrossRefGoogle Scholar
[5]Formisano, A., Omodeo, E. G., and Temperini, M., Goals and benchmarks for automated map reasoning, Journal of Symbolic Computation, vol. 29 (2000), no. 2, Special issue. (M.-P Bonacina and U. Furbach, editors).CrossRefGoogle Scholar
[6]van Heijenoort, J. (editor), From Frege to GÖdel— A source book in mathematical logic, 1879–1931, 3rd printing ed., Source books in the history of the sciences, Harvard University Press, 1977.Google Scholar
[7]Hodkinson, I., Finite variable logics, Bulletin of the European Association for Theoretical Computer Science, vol. 51 (1993), pp. 111–140, Columns: Logic in Computer Science.Google Scholar
[8]Immerman, N., Upper and lower bounds for first order expressibility, Journal of Computer and System Sciences, vol. 25 (1982), no. 1, pp. 76–98.CrossRefGoogle Scholar
[9]Immerman, N. and Kozen, D., Definability with bounded number of bound variables, Information and Computation, vol. 83 (1989), no. 2, pp. 121–139.CrossRefGoogle Scholar
[10]Kolaitis, P. G. and Vardi, M. Y., On the expressive power of variable-confined logics, Proceedings, 11th annual IEEE symposium on logic in computer science (New Brunswick, New Jersey), IEEE Computer Society Press, 1996, pp. 348–359.CrossRefGoogle Scholar
[11]Kwatinetz, M. K., Problems of expressibility infinite languages, Ph.D. thesis, University of California, Berkeley, 1981.Google Scholar
[12]Tarski, A., Some metalogical results concerning the calculus of relations, this Journal, vol. 18 (1953), pp. 188–189.Google Scholar
[13]Tarski, A. and Givant, S., A formalization of Set Theory without variables, Colloquium Publications, vol. 41, American Mathematical Society, 1987.Google Scholar
[14]Thomas, W., Languages, automata and logic, Handbook of formal languages, vol. III (Rozenberg, G. and Salomaa, A., editors), Springer, 1997, pp. 389–455.CrossRefGoogle Scholar
[15]Zermelo, E., Untersuchungen Über die Grundlagen der Mengenlehre I, In Heijenoort [6], (English translation), pp. 199–215.Google Scholar