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}WTC{\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}S2S{\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}WTCε{\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}TCε{\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}WTCε{\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}WTCε{\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}TCε{\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}WTC{\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}TC{\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.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 104,556

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

Hard Provability Logics.Mojtaba Mojtahedi - 2021 - In Mojtaba Mojtahedi, Shahid Rahman & MohammadSaleh Zarepour, Mathematics, Logic, and their Philosophies: Essays in Honour of Mohammad Ardeshir. Springer. pp. 253-312.
Minimal elementary end extensions.James H. Schmerl - 2017 - Archive for Mathematical Logic 56 (5-6):541-553.

Analytics

Added to PP
2014-07-19

Downloads
29 (#854,238)

6 months
6 (#724,098)

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