Elementary first-order theories of trees allowing at most, exactly $\mathrm{m}$, and any finite number of immediate descendants are introduced and proved mutually interpretable among themselves and with Robinson arithmetic, Adjunctive Set Theory with Extensionality and other well-known weak theories of numbers, sets, and strings.

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.

In this paper we explore the following question: how weak can a logic be for Rosser’s essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson’s Q is essentially undecidable in intuitionistic logic, and P. Hájek proved it in the fuzzy logic BL for Grzegorczyk’s variant of Q which interprets the arithmetic operations as nontotal nonfunctional relations. We present a proof of essential undecidability in a much weaker substructural logic and for a much weaker arithmetic theory, a version of Robinson’s R (with arithmetic operations also interpreted as mere relations). Our result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic.

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.