Return to Answer

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 $> max(|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 max(|u|, |v|)$, and a new element called $0$, with multiplication as before (and, if the product is $> max(|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!)

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!)

The standard meaning of residually finite here is that for every pair of elements $u, v \in 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!)

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 $> max(|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 max(|u|, |v|)$, and a new element called $0$, with multiplication as before (and, if the product is $> max(|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!)

The standard meaning of residually finite here is that for every pair of elements $u, v \in 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$ do not decrease. We can 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!)

The standard meaning of residually finite here is that for every pair of elements $u, v \in 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!)