  We will prove bi-interpretability of the arithmetic $\N = \langle N, +,\cdot,
0, 1\rangle$ 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 $\mathbb N$ to any
boolean combination of formulas from $\Pi_n$ or $\Sigma_n$.
