Weak theories of concatenation and minimal essentially undecidable theories: An encounter of WTC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}}$$\end{document} and S2S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{S2S}}$$\end{document}

Archive for Mathematical Logic 53 (7-8):835-853 (2014)
  Copy   BIBTEX

Abstract

We consider weak theories of concatenation, that is, theories for strings or texts. We prove that the theory of concatenation WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document}, which is a weak subtheory of Grzegorczyk’s theory TC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}^{-\varepsilon}}$$\end{document}, is a minimal essentially undecidable theory, that is, the theory WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document} is essentially undecidable and if one omits an axiom scheme from WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document}, then the resulting theory is no longer essentially undecidable. Moreover, we give a positive answer to Grzegorczyk and Zdanowski’s conjecture that ‘The theory TC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}^{-\varepsilon}}$$\end{document} is a minimal essentially undecidable theory’. For the alternative theories WTC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}}$$\end{document} and TC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}}$$\end{document} which have the empty string, we also prove that the each theory without the neutrality of ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon}$$\end{document} is to be such a theory too.

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

Weak Theories of Concatenation and Arithmetic.Yoshihiro Horihata - 2012 - Notre Dame Journal of Formal Logic 53 (2):203-222.
Arithmetic on semigroups.Mihai Ganea - 2009 - Journal of Symbolic Logic 74 (1):265-278.
On VC-minimal theories and variants.Vincent Guingona & Michael C. Laskowski - 2013 - Archive for Mathematical Logic 52 (7-8):743-758.
Forking in VC-minimal theories.Sarah Cotter & Sergei Starchenko - 2012 - Journal of Symbolic Logic 77 (4):1257-1271.
More on The Decidability of Mereological Theories.Hsing-Chien Tsai - 2011 - Logic and Logical Philosophy 20 (3):251-265.
Minimal truth and interpretability.Martin Fischer - 2009 - Review of Symbolic Logic 2 (4):799-815.
Weakly one-based geometric theories.Alexander Berenstein & Evgueni Vassiliev - 2012 - Journal of Symbolic Logic 77 (2):392-422.
Remarks on Compositionality and Weak Axiomatic Theories of Truth.Günther Eder - 2014 - Journal of Philosophical Logic 43 (2-3):541-547.
Some two-cardinal results for o-minimal theories.Timothy Bays - 1998 - Journal of Symbolic Logic 63 (2):543-548.
Small theories of Boolean ordered o-minimal structures.Roman Wencel - 2002 - Journal of Symbolic Logic 67 (4):1385-1390.
Weak dividing, chain conditions, and simplicity.Alfred Dolich - 2004 - Archive for Mathematical Logic 43 (2):265-283.
Hereditary undecidability of some theories of finite structures.Ross Willard - 1994 - Journal of Symbolic Logic 59 (4):1254-1262.

Analytics

Added to PP
2014-07-19

Downloads
15 (#809,553)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Current Research on Gödel’s Incompleteness Theorems.Yong Cheng - 2021 - Bulletin of Symbolic Logic 27 (2):113-167.
Finding the limit of incompleteness I.Yong Cheng - 2020 - Bulletin of Symbolic Logic 26 (3-4):268-286.
Weak essentially undecidable theories of concatenation.Juvenal Murwanashyaka - 2022 - Archive for Mathematical Logic 61 (7):939-976.

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.
On Interpretability in the Theory of Concatenation.Vítězslav Švejdar - 2009 - Notre Dame Journal of Formal Logic 50 (1):87-95.

View all 9 references / Add more references