On Interpretability in the Theory of Concatenation

Notre Dame Journal of Formal Logic 50 (1):87-95 (2009)
  Copy   BIBTEX

Abstract

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}$

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

Modal analysis of generalized Rosser sentences.Vítězslav Švejdar - 1983 - Journal of Symbolic Logic 48 (4):986-999.
Weak Theories of Concatenation and Arithmetic.Yoshihiro Horihata - 2012 - Notre Dame Journal of Formal Logic 53 (2):203-222.
Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.
The formalization of interpretability.Albert Visser - 1991 - Studia Logica 50 (1):81 - 105.
The interpretability logic of peano arithmetic.Alessandro Berarducci - 1990 - Journal of Symbolic Logic 55 (3):1059-1089.

Analytics

Added to PP
2010-09-13

Downloads
30 (#459,346)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Deflationism beyond arithmetic.Kentaro Fujimoto - 2019 - Synthese 196 (3):1045-1069.
Growing Commas. A Study of Sequentiality and Concatenation.Albert Visser - 2009 - Notre Dame Journal of Formal Logic 50 (1):61-85.
Arithmetic on semigroups.Mihai Ganea - 2009 - Journal of Symbolic Logic 74 (1):265-278.
Finding the limit of incompleteness I.Yong Cheng - 2020 - Bulletin of Symbolic Logic 26 (3-4):268-286.

View all 14 citations / Add more citations

References found in this work

Concatenation as a basis for arithmetic.W. V. Quine - 1946 - Journal of Symbolic Logic 11 (4):105-114.
Undecidability without Arithmetization.Andrzej Grzegorczyk - 2005 - Studia Logica 79 (2):163-230.
Growing Commas. A Study of Sequentiality and Concatenation.Albert Visser - 2009 - Notre Dame Journal of Formal Logic 50 (1):61-85.
Arithmetic on semigroups.Mihai Ganea - 2009 - Journal of Symbolic Logic 74 (1):265-278.

Add more references