Article contents
MUTUAL INTERPRETABILITY OF WEAK ESSENTIALLY UNDECIDABLE THEORIES
Published online by Cambridge University Press: 18 February 2022
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.
Keywords
MSC classification
- Type
- Article
- Information
- Copyright
- © The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic
References
- 3
- Cited by