Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-19T09:16:22.208Z Has data issue: false hasContentIssue false
  • English
  • Français

MUTUAL INTERPRETABILITY OF ROBINSON ARITHMETIC AND ADJUNCTIVE SET THEORY WITH EXTENSIONALITY

Published online by Cambridge University Press:  15 February 2018

ZLATAN DAMNJANOVIC
ZLATAN DAMNJANOVIC*
Affiliation:
SCHOOL OF PHILOSOPHY UNIVERSITY OF SOUTHERN CALIFORNIA LOAS ANGELES, CA 90089, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

An elementary theory of concatenation, QT+, is introduced and used to establish mutual interpretability of Robinson arithmetic, Minimal Predicative Set Theory, quantifier-free part of Kirby’s finitary set theory, and Adjunctive Set Theory, with or without extensionality. The most basic arithmetic and simplest set theory thus turn out to be variants of string theory.

Keywords

03-XXRobinson arithmeticinterpretabilityadjunctive set theoryextensionalitystring theoryconcatenationpredicative set theoryfinitary set theory
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 23 , Issue 4 , December 2017 , pp. 381 - 404
Copyright
Copyright © The Association for Symbolic Logic 2017 

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

Burgess, J., Fixing Frege, Princeton University Press, Princeton, 2005.Google Scholar
Collins, G. E. and Halpern, J. D., On the interpretability of arithmetic in set theory. Notre Dame Journal of Formal Logic, vol. 11 (1970), pp. 477–483.Google Scholar
Damnjanovic, Z., From Strings to Sets: A Technical Report, University of Southern California, 2016, arXiv: 1701.07548.Google Scholar
Ferreira, F. and Ferreira, G., Interpretability in Robinson’s Q, this Bulletin, vol. 19 (2013), pp. 289–317.Google Scholar
Ganea, M., Arithmetic in semigroups. Journal of Symbol Logic, vol. 74 (2007), pp. 265–278.Google Scholar
Grzegorczyk, A., Undecidability without arithmetization. Studia Logica, vol. 79 (2005), pp. 163–230.Google Scholar
Grzegorczyk, A. and Zdanowski, K., Undecidability and concatenation, Andrzej Mostowski and Foundational Studies (Ehrenfeucht, A., Marek, V. W., and Srebrny, M., editors), IOS Press, Amsterdam, 2008, pp. 72–91.Google Scholar
Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Springer, Berlin, 1993.Google Scholar
Kirby, L., Finitary set theory. Notre Dame Journal of Formal Logic, vol. 50 (2009), pp. 227–243.Google Scholar
Montagna, F. and Mancini, A., A minimal predicative set theory. Notre Dame Journal of Formal Logic, vol. 35 (1994), pp. 186–203.Google Scholar
Mycielski, J., Pudlák, P., and Stern, A. S., A Lattice of Chapters of Mathematics (Interpretations between Theorems), Memoirs of the American Mathematical Society, vol. 426, American Mathematical Society, Providence, RI, 1990.Google Scholar
Nelson, E., Predicative Arithmetic, Princeton University Press, Princeton, 1986.Google Scholar
Quine, W. V. O., Concatenation as a basis for arithmetic. Journal of Symbolic Logic, vol. 11 (1946), pp. 105–114.Google Scholar
Szmielew, W. and Tarski, A., Mutual interpretability of some essentially undecidable theories, Proceedings of the International Congress of Mathematicians (Cambridge, Massachussetts, 1950), (Graves, L. M., Hille, E., Smith, P. A., and Zariski, O., editors), vol. 1, American Mathematical Society, Providence, RI, 1952, p. 734.Google Scholar
Švejdar, V, On interpretability in the theory of concatenation. Notre Dame Journal of Formal Logic, vol. 50 (2009), pp. 87–95.Google Scholar
Tarski, A., Mostowski, A., and Robinson, R. M., Undecidable Theories, North-Holland, Amsterdam, 1953.Google Scholar
Visser, A., Pairs, sets and sequences in first-order theories. Archive for Mathematical Logic, vol. 47 (2008), pp. 297–326.Google Scholar
Visser, A., Cardinal arithmetic in the style of Baron von Münchhausen. Review of Symbolic Logic, vol. 2 (2009), pp. 570–589.Google Scholar
Visser, A., Growing commas: A study of sequentiality and concatenation. Notre Dame Journal of Formal Logic, vol. 50 (2009), pp. 61–85.Google Scholar