Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Noah S May 29 at 3:24
    
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. –  The Masked Avenger May 29 at 6:57
3  
The answer to the first question is “no” by the same argument as in mathoverflow.net/a/131986/12705. –  Emil Jeřábek May 29 at 9:56
1  
Related question mathoverflow.net/questions/17483/… –  Benjamin Steinberg May 29 at 18:34

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
1  
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. –  Emil Jeřábek May 29 at 21:11
1  
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. –  Emil Jeřábek May 29 at 21:17
    
@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. :) –  Michael A Warren May 29 at 21:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.