Bi-interpretability of some monoids with the arithmetic and applications

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)

Abstract: We will prove bi-interpretability of the arithmetic

N = l a n g l e N, +, c d o t, 0, 1 a n g l e

and the weak second order theory of

N

with the free monoid

m a t h b b 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

m a t h b b 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

p h i

such that every finitely generated monoid satisfying

p h i

is isomorphic to

m a t h b b 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

m a t h b b N

to any boolean combination of formulas from

P i_{n}

or

S i g m a_{n}

.

Recommendations

Cites work

Cited in

(3)

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)