Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T06:19:09.614Z Has data issue: false hasContentIssue false

MUTUAL INTERPRETABILITY OF WEAK ESSENTIALLY UNDECIDABLE THEORIES

Published online by Cambridge University Press:  18 February 2022

ZLATAN DAMNJANOVIC*
Affiliation:
SCHOOL OF PHILOSOPHY UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES, CA90089, USA

Abstract

Kristiansen and Murwanashyaka recently proved that Robinson arithmetic, Q, is interpretable in an elementary theory of full binary trees, T. We prove that, conversely, T is interpretable in Q by producing a formal interpretation of T in an elementary concatenation theory QT+, thereby also establishing mutual interpretability of T with several well-known weak essentially undecidable theories of numbers, strings, and sets. We also introduce a “hybrid” elementary theory of strings and trees, WQT*, and establish its mutual interpretability with Robinson’s weak arithmetic R, the weak theory of trees WT of Kristiansen and Murwanashyaka, and the weak concatenation theory WTCε of Higuchi and Horihata.

Type
Article
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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

Damnjanovic, Z., Mutual interpretability of Robinson arithmetic and adjunctive set theory . Bulletin of Symbolic Logic , vol. 23 (2017), pp. 381404.CrossRefGoogle Scholar
Damnjanovic, Z., From strings to sets: A technical report, preprint, 2017, arXiv:1701.07548, University of Southern California.Google Scholar
Damnjanovic, Z., Appendix to “Mutual Interpretability of Weak Essentially Undecidable Theories”, preprint, 2021, arXiv:2104.07202.CrossRefGoogle Scholar
Ferreira, F. and Ferreira, G., Interpretability in Robinson’s Q . Bulletin of Symbolic Logic , vol. 19 (2013), pp. 289317.CrossRefGoogle Scholar
Higuchi, K. and Horihata, Y., Weak theories of concatenation and minimal essentially undecidable theories . Archive for Mathematical Logic , vol. 53 (2014), pp. 835853.CrossRefGoogle Scholar
Kristiansen, L. and Murwanashyaka, J., On interpretability between some weak essentially undecidable theories , Beyond the Horizon of Computability (Anselmo, M., Vedova, G. D., Manea, F., Pauly, A., editors), Lecture Notes in Computer Science, vol. 12098, Springer, Cham, 2020, pp. 6374.CrossRefGoogle Scholar
Quine, W. V. O., Concatenation as a basis for arithmetic, this Journal, vol. 11 (1946), pp. 105–114.Google Scholar
Tarski, A., Mostowski, A., and Robinson, R. M., Undecidable Theories , North-Holland, Amsterdam, 1953.Google Scholar
Visser, A., Growing commas: A study of sequentiality and concatenation . Notre Dame Journal of Formal Logic , vol. 50 (2009), pp. 6185.Google Scholar
Visser, A., Why the theory R is special , Foundational Adventures: Essays in Honour of Harvey Friedman (Tennant, N., editor), College Publications, London, 2014, pp. 723.Google Scholar