Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability

Let $n\in\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers with successor map $S$, and let $W_{n}$ be the set of words in the letters $1,\dots,n$, with empty word $\varnothing$, concatenation $(u,v)\mapsto uv$ and reversal $w\mapsto w^{\mathrm{rev}}$. Finite and countable sets are as in Finite Set and Countable Set.

1. (Monoid)¶ For all $u,v,z\in W_{n}$: $(uv)z=u(vz)$ and $\varnothing u=u\varnothing=u$. If $u$ and $v$ have lengths $k$ and $l$, then $uv$ has length $k+l$; and $uv=\varnothing$ holds only if $u=v=\varnothing$.

2. (Last letter)¶ If $w$ has length $S(k)$ for some $k\in\mathbb{N}$, then $w=w'(j)$, where $w'$ is the restriction of $w$ to $[k]$, a word of length $k$, and $(j)$ is the letter $j=w_{S(k)}$. Every word of length $1$ is a letter.

3. (Reversal)¶ For all $u,v,w\in W_{n}$: $(w^{\mathrm{rev}})^{\mathrm{rev}}=w$, $(uv)^{\mathrm{rev}}=v^{\mathrm{rev}}u^{\mathrm{rev}}$, and $(j)^{\mathrm{rev}}=(j)$ for every letter $(j)$. In particular $w\mapsto w^{\mathrm{rev}}$ is a bijection from $W_{n}$ onto $W_{n}$, and it maps words of length $k$ to words of length $k$.

4. (Factorisations)¶ For every $w\in W_{n}$ the set

of factorisations of $w$ is nonempty and finite, and $F(\varnothing)=\{(\varnothing,\varnothing)\}$.

5. (Finite sets of products)¶ If $A,B\subseteq W_{n}$ are finite, then the set $\{uv:\ u\in A,\ v\in B\}$ is finite.

6. (Countability)¶ $W_{n}$ is countable.