On Interpretability in the Theory of Concatenation
Švejdar, Vítězslav
Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, p. 87-95 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We prove that a variant of Robinson arithmetic $\mathsf{Q}$ with nontotal operations is interpretable in the theory of concatenation $\mathsf{TC}$ introduced by A. Grzegorczyk. Since $\mathsf{Q}$ is known to be interpretable in that nontotal variant, our result gives a positive answer to the problem whether $\mathsf{Q}$ is interpretable in $\mathsf{TC}$ . An immediate consequence is essential undecidability of $\mathsf{TC}$ .
Publié le : 2009-01-15
Classification:  concatenation,  interpretability,  Robinson arithmetic,  essential undecidability,  03B25,  03F25 
@article{1232375164,
     author = {\v Svejdar, V\'\i t\v ezslav},
     title = {On Interpretability in the Theory of Concatenation},
     journal = {Notre Dame J. Formal Logic},
     volume = {50},
     number = {1},
     year = {2009},
     pages = { 87-95},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1232375164}
}

Švejdar, Vítězslav. On Interpretability in the Theory of Concatenation. Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, pp.  87-95. http://gdmltest.u-ga.fr/item/1232375164/