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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ For the second question, the answer is clearly "no": no transformation monoid is countably infinite, and so the Lowenheim-Skolem theorem kills this one. I'm sure the answer to the first question is "no" as well, but I don't see the proof yet. $\endgroup$– Noah SchweberMay 29, 2014 at 3:24
-
$\begingroup$ You might try axiomatizing lack of relations for free monoids. Cancellation properties are a good start folllowed by ab=cd iff one or more of them is a unit or else there are r s and t with a and b and c and d being some finite combinations of r, s, and t. $\endgroup$– The Masked AvengerMay 29, 2014 at 6:57
-
3$\begingroup$ The answer to the first question is “no” by the same argument as in mathoverflow.net/a/131986/12705. $\endgroup$– Emil JeřábekMay 29, 2014 at 9:56
-
1$\begingroup$ Related question mathoverflow.net/questions/17483/… $\endgroup$– Benjamin SteinbergMay 29, 2014 at 18:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
1$\begingroup$ The Fréchet filter is not an ultrafilter. And as observed in the linked answer on groups, you don’t need to explicitly compute any prefixes, it suffices to observe that the ultrapower is commutative, but uncountable. $\endgroup$ May 29, 2014 at 21:11
-
1$\begingroup$ In fact, you don’t need ultrapowers either, the Löwenheim–Skolem theorem gives directly that the free monoid on one generator has elementary extensions of arbitrary cardinality. $\endgroup$ May 29, 2014 at 21:17
-
$\begingroup$ @EmilJeřábek, yes quite right that the Fréchet filter is not an ultrafilter (not sure what I was thinking). I have updated the answer to reflect this point. :) $\endgroup$ May 29, 2014 at 21:39