Mutual Interpretability of Weak Essentially Undecidable Theories

Journal of Symbolic Logic 87 (4):1374-1395 (2022)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 79,724

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A Weak Essentially Undecidable Theory.Kamila Bendova - 2007 - Reports on Mathematical Logic.
Weak Theories of Concatenation and Arithmetic.Yoshihiro Horihata - 2012 - Notre Dame Journal of Formal Logic 53 (2):203-222.
Complexity of the interpretability logics ILW and ILP.Luka Mikec - 2023 - Logic Journal of the IGPL 31 (1):194-213.
Vaught's theorem on axiomatizability by a scheme.Albert Visser - 2012 - Bulletin of Symbolic Logic 18 (3):382-402.
On the Decidability of Axiomatized Mereotopological Theories.Hsing-Chien Tsai - 2015 - Notre Dame Journal of Formal Logic 56 (2):287-306.
Arithmetic on semigroups.Mihai Ganea - 2009 - Journal of Symbolic Logic 74 (1):265-278.
Weak essentially undecidable theories of concatenation.Juvenal Murwanashyaka - 2022 - Archive for Mathematical Logic 61 (7):939-976.
Minimal truth and interpretability.Martin Fischer - 2009 - Review of Symbolic Logic 2 (4):799-815.


Added to PP

9 (#957,967)

6 months
5 (#166,481)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Zlatan Damnjanovic
University of Southern California

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references