Bi-interpretability of Some Monoids with the Arithmetic and Applications

Abstract

We will prove bi-interpretability of the arithmetic $\mathbb{N}=⟨N,+,\cdot ,0,1⟩$ and the weak second order theory of $\mathbb{N}$ with the free monoid ${\mathbb{M}}_X$ of finite rank greater than 1 and with a non-trivial partially commutative monoid with trivial center. This bi-interpretability implies that finitely generated submonoids of these monoids are definable. Moreover, any recursively enumerable language in the alphabet $X$ is definable in ${\mathbb{M}}_X$. Primitive elements, and, therefore, free bases are definable in the free monoid. It has the so-called QFA property, namely there is a sentence $\ddot{I}•$ such that every finitely generated monoid satisfying $\ddot{I}•$ is isomorphic to ${\mathbb{M}}_X$. The same is true for a partially commutative monoid without center. We also prove that there is no quantifier elimination in the theory of any structure that is bi-interpretable with $\mathbb{N}$ to any boolean combination of formulas from ${\hat{I}}_n$ or $\hat{I}{\pounds }_n$.

We added new results. The paper is now accepted to Semigroup Forum