Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1396

Preprint Number 1396

Previous Next Preprint server

1396. Olga Kharlampovich and Laura Lopez
Bi-interpretability of a Free Monoid with the Arithmetic and Applications

Submission date: 15 March 2018


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.

Last updated: March 23 2021 10:20 Please send your corrections to: