Bi-interpretability of some monoids with the arithmetic and applications

DOI10.1007/S00233-019-10021-4zbMATH Open1467.03030arXiv1803.06003OpenAlexW2964192494WikidataQ128118417 ScholiaQ128118417MaRDI QIDQ2003186FDOQ2003186

Olga Kharlampovich, L. López

Publication date: 16 July 2019

Published in: Semigroup Forum (Search for Journal in Brave)

Abstract: We will prove bi-interpretability of the arithmetic $N=langleN,+,cdot,0,1angle$ and the weak second order theory of $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 $phi$ such that every finitely generated monoid satisfying $phi$ 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 $mathbbN$ to any boolean combination of formulas from $P{i}_n$ or $Sigm{a}_n$.

Full work available at URL: https://arxiv.org/abs/1803.06003

zbMATH Keywords

free monoidpartially commutative monoidfirst order properties

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Commutative semigroups (20M14) Free semigroups, generators and relations, word problems (20M05) Interpolation, preservation, definability (03C40) Models of arithmetic and set theory (03C62) Relative consistency and interpretations (03F25)

Cites Work

• DEFINABLE SETS IN A HYPERBOLIC GROUP
• Elementary theory of free non-abelian groups.
• Title not available (Why is that?)
• Homogeneity in the free group.
• Diophantine geometry over groups. VI: The elementary theory of a free group.
• Homogeneity and prime models in torsion-free hyperbolic groups.
• Describing Groups
• Concatenation as a basis for arithmetic
• Tarski-type problems for free associative algebras
• DIOPHANTINE REPRESENTATION OF ENUMERABLE PREDICATES
• On groups and fields interpretable in torsion-free hyperbolic groups

Cited In (2)

• On equations and first-order theory of one-relator monoids
• Bi-interpretability and QFA structures: study of some soluble groups and commutative rings. (Bi-interprétabilité et structures QFA : étude de groupes résolubles et des anneaux commutatifs

This page was built for publication: Bi-interpretability of some monoids with the arithmetic and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003186)