Are all free monoids residually finite?

Question

I cannot manage to prove that a free monoid with operation concatenation, and with at least two generators is residually finite. If there is just one generator, the free monoid $\{a\}^*$ is isomorphic to $\langle N, +\rangle$ which is residually finite. What happens if there are two or more generators? I found some results about monoids with relations on the generators, but I don't see how to lift the result to the free monoid. I will be grateful for any help or reference.

Answer 1

The standard meaning of residually finite here is that for every pair of elements $u, v$ in the free monoid $A^\ast$, if $u \neq v$ then there is a homomorphism $\phi \colon A^\ast \to F$ with $F$ a finite monoid and $\phi(u) \neq \phi(v)$. Proving that free monoids are residually finite is conceptually quite simple; no fancy tools are needed.

So, given distinct $u, v \in A^\ast$, consider the ideal $I$ of $A^\ast$ which consists of all words of length $>|u|+|v|$ (here $|u|$ denotes the length of the word $u$). Obviously, this is a (two-sided) ideal; if I multiply any word in $A^\ast$ by an element from $I$, then I will remain in $I$, as the length of products in $A^\ast$ can only increase. We can then consider the Rees quotient semigroup $A^\ast/I$ of $A^\ast$ by $I$, which is just a fancy way of saying "collapse all elements of $I$ into a single element $0$, and define multiplication in the obvious way". Then $A^\ast / I$ is a finite monoid - indeed, its elements are all the words of length $\leq |u|+|v|$, and a new element called $0$, with multiplication as before (and, if the product is $>|u|+|v|$, then we set the product to be $0$). The obvious homomorphism from $A^\ast$ to $A^\ast / I$ will map $u$ and $v$ to distinct elements, as neither $u$ nor $v$ are long enough words to be killed by the quotient. Thus free monoids are residually finite.

(This proof does not carry over to free groups - after all, the set of words of length $\geq n$ in a free group does not form an ideal!)

Answer 2

Here is another proof that I like, although it is not as simple as modding out by a cofinite ideal as per @Carl-FredrikNybergBrodda's answer. This approach I learned from Stalling's old geometric group theory lecture notes. Hopefully I am correctly recalling it. Since all free monoids on a countable generating set embed in the free monoid on 2 generators $\mathbf 0$, $\mathbf 1$ it is enough to do that case.

I'll give a representation of the free monoid on $2$ generated by $2\times 2$ nonnegative matrices (invertible over $\mathbb Z[1/2]$) that is particularly easy to verify is faithful (but this representation does not extend faithfully to the free group). Since the monoid of $2\times 2$ integer matrices is clearly residually finite by taking the entries modulo large primes, we are done.

Map $\mathbf 0$ to $\begin{bmatrix}1 & 0 \\ 0 & 2\end{bmatrix}$ and map $\mathbf 1$ to $\begin{bmatrix} 1 & 1\\ 0 & 2\end{bmatrix}$. Then a simple induction shows a word $w$ maps to $\begin{bmatrix} 1 & d(w)\\ 0 & 2^{|w|}\end{bmatrix}$ where $|w|$ is the length of $w$ and $d(w)$ is the natural number whose base $2$ expansion is $w$ (with perhaps some leading zeroes). Knowing the length of $w$ and the integer $d(w)$ lets you recover $w$ since from the length you know how many leading zeroes to add.

Answer 3

One can generalize the notion of residual finiteness to universal algebra. An algebraic structure $A$ is said to be residually finite if $A$ is isomorphic to a subdirect product of finite algebraic structures. Equivalently, $A$ is residually finite if for each $a,b\in A$ with $a\neq b$, there is a homomorphism $\phi:A\rightarrow B$ where $B$ is a finite algebraic structure and $\phi(a)\neq\phi(b)$.

As it was observed by ADL in the comments, one can use the fact that free groups are residually finite to conclude that free monoids are also residually finite as a corollary (on this site, here is a collection of proofs that free groups are residually finite).

We may also establish residual finiteness of $A^*$ using monoid homomorphisms $\phi:A^*\rightarrow M$ both when $M$ is always a group and when $M$ is far away from being a group.

If $R,S$ are sets, then $R^S$ denotes the set of all functions from $S$ to $R$.

Let $A,B$ be finite sets. Suppose $*:A\times B\rightarrow B$ is a binary operation $*$. For each $a\in A$, let $L_{a,*,n}:B^n\rightarrow B^n.$ be the mapping defined by letting $L_{a,*,n}(b_1,\dots,b_n)=(a*b_n,b_1,\dots,b_{n-1})$. We can define a monoid homomorphism $\phi_{*,n}:A^*\rightarrow (B^n)^{B^n}$ by letting $\phi_{*,n}(a_1\dots a_r)=\phi(a_1)\dots\phi(a_r)=L_{a_1,*,n}\dots L_{a_r,*,,n}$. Then $$\phi_{*,n}(a_1\dots a_n)(b_1,\dots,b_n)=(a_1*b_1,\dots,a_n*b_n).$$

Observation 1: If the operation $*$ is left cancellative, then the mapping $\phi_{*,n}(a_1\dots a_n)$ is injective, so $\phi_{*,n}[A^*]$ is a subgroup of $S(A^n)$. This shows that the free monoid embeds into a product of symmetric groups.

Observation 2: If $A=B$ and the operation $*$ satisfies $x*y=x$, then the semigroup $\phi_{*,n}[A^*]\setminus\{e\}$ satisfies the identity $x_1\dots x_ny_1\dots y_n=x_1\dots x_n$. This means that $A^*$ can be embedded into a product of monoids $M$ where $M\setminus\{e\}$ is a subsemigroup that satisfies the identity $x_1\dots x_ny_1\dots y_n=x_1\dots x_n$.

There are other constructions for embedding $A^*$ into a product of non-group-like finite semigroups.