Submission date: 15 March 2018

Abstract:

We will prove bi-interpretability of the arithmetic N = < N, + , ⠂ , 0 > and the weak second order theory of N with the free monoid M_X of finite rank. This bi-interpretability implies that finitely generated submonoids of M_X are definable. In contrast to this, proper subgroups of a free group are not definable (except cyclic subgroups when the language contains constants) [KM1]. Also primitive elements, and, therefore, free bases are not definable in a free group of rank greater than 2 [KM1], but they are easily definable in the free monoid. There is no quantifier elimination in the theory of M_X to any boolean combination of formulas from Π_n or Σ_n.

Mathematics Subject Classification: 03C60

Keywords and phrases:

Full text arXiv 1803.06003: pdf, ps.