3.9 Article

Weak theories of concatenation and minimal essentially undecidable theories

Journal

ARCHIVE FOR MATHEMATICAL LOGIC
Volume 53, Issue 7-8, Pages 835-853

Publisher

SPRINGER HEIDELBERG
DOI: 10.1007/s00153-014-0391-x

Keywords

Theory of concatenation; The monadic second-order theory of two successors; Minimal essentially undecidable theory; Interpretability

Funding

  1. Grants-in-Aid for Scientific Research [13J10409] Funding Source: KAKEN

Ask authors/readers for more resources

We consider weak theories of concatenation, that is, theories for strings or texts. We prove that the theory of concatenation , which is a weak subtheory of Grzegorczyk's theory , is a minimal essentially undecidable theory, that is, the theory is essentially undecidable and if one omits an axiom scheme from , then the resulting theory is no longer essentially undecidable. Moreover, we give a positive answer to Grzegorczyk and Zdanowski's conjecture that 'The theory is a minimal essentially undecidable theory'. For the alternative theories and which have the empty string, we also prove that the each theory without the neutrality of is to be such a theory too.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

3.9
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available