Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal

Let $\mathbb{N}$ be the set of natural numbers with its addition and order, let $n\in\mathbb{N}$, and for $k\in\mathbb{N}$ let $[k]$ be the initial segment determined by $k$ and $[n]^{k}$ the set of $k$-tuples in $[n]$, that is, of maps $[k]\to[n]$.

1. (Words)¶ The empty word $\varnothing$ is the map with empty domain and values in $[n]$. For $k\in\mathbb{N}$, a word of length $k$ is an element of $[n]^{k}$. The set $W_{n}$ of words in the letters $1,\dots,n$ consists of the empty word and of the words of length $k$ for all $k\in\mathbb{N}$. A word of length $k$ has domain $[k]$, which is nonempty by claim 1 of Basic Properties of Initial Segments of the Natural Numbers and has $k$ elements by claim 1 of Basic Properties of Finite Sets; hence the empty word has no length in $\mathbb{N}$, and every other word has exactly one length, by Uniqueness of the Number of Elements. For $j\in[n]$ the letter $j$ is the word $(j)$ of length $1$.

2. (Concatenation)¶ For $u,v\in W_{n}$ the concatenation $uv\in W_{n}$ is defined as follows. If $u=\varnothing$ then $uv=v$, and if $v=\varnothing$ then $uv=u$. If $u$ has length $k$ and $v$ has length $l$, then $uv$ is the word of length $k+l$ with

this determines $uv$ on all of $[k+l]$, and consistently, because $[k+l]$ is the union of the disjoint sets $[k]$ and $[k+l]\setminus[k]$ and $i\mapsto k+i$ is a bijection from $[l]$ onto the latter, by claim 5 of Basic Properties of Initial Segments of the Natural Numbers.

3. (Reversal)¶ The reversal of $w\in W_{n}$ is the word $w^{\mathrm{rev}}\in W_{n}$ with $\varnothing^{\mathrm{rev}}=\varnothing$, and, if $w$ has length $k$, $w^{\mathrm{rev}}$ the word of length $k$ with

for $i\in[k]$; such a $j\in\mathbb{N}$ exists and is unique by claims 1, 3, 4, 5, 6 and 7 of Properties of the Order on the Natural Numbers, and it lies in $[k]$ because $j<j+i=i+j=k+1=S(k)$, with $S$ the successor map, by claim 6 of that lemma and claims 4 and 1 of Arithmetic of Addition on the Natural Numbers, whence $j\le k$ by claim 5 of Properties of the Order on the Natural Numbers.