I asked this question on math stack exchange, but I didn't get any responses. So, now I am motivated to ask it here. Is the class of free monoids first order axiomatizable? And what about the class of full transformation monoids, in other words monoids that are isomorphic to a monoids of all functions over a set S to itself under composition?



Free monoids and full transformation monoids
In order to prove that something is not first-order axiomatizable it is sometimes fun to use ultraproducts. I think we can do this in this case. Note that one of the characteristic features of free monoids is that any element of a free monoid can have only finitely many "prefixes" (this is number 4 from Ben Steinberg's answer to the question he linked to in the comments a moment ago). This is the feature we will violate.


Let F be a non-principal ultrafilter on the natural numbers. Let M be the free monoid on the one element set {1}. Let $\mu$ be the element of the ultrapower $M^{F}$ determined by $\mu(n):=1\ldots 1$ where $n$-many $1$'s occur here. Essentially, $\mu$ is an infinite word. It is then easy to see that $\mu$ has infinitely many prefixes and therefore $M^{F}$ cannot be a free monoid. For example, we could take $\nu(n):=1$ for all $n$ and $\xi(n)$ to be the empty word $()$ when $n=0$ and $\mu(n-1)$ otherwise. Then $\mu=\nu\xi$ in $M^{F}$ (the set on which they disagree contains just the number $0$). We can now perform a shift of this example in any number of ways to obtain infinitely many prefixes of $\mu$.


This contradicts the claim that the theory of free monoids is first-order axiomatizable.


