On Interpretability in the Theory of Concatenation
Vítězslav Švejdar · Notre Dame Journal of Formal Logic · 2009
We prove that a variant of Robinson arithmetic Q with nontotal operations is interpretable in the theory of concatenation TC introduced by A. Grzegorczyk. Since Q is known to be interpretable in that nontotal variant, our result gives a positive answer to the problem whether Q is interpretable in TC . An immediate consequence is essential undecidability of TC .