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

We use the definitions Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal (clauses Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §words, Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation, Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §reversal), Natural Numbers, Order on the Natural Numbers, Tuples in a Set, Finite Set, Bijection of Sets and Family and Subfamily of Subsets of a Set, and the results Arithmetic of Addition on the Natural Numbers, Properties of the Order on the Natural Numbers, Basic Properties of Initial Segments of the Natural Numbers, Inverse of a Bijection, Characteristic Property of the Ordered Pair, Basic Properties of Finite Sets, Peeling an Element off a Finite Set, and Unions of Finite Sets, Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets, Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus, Basic Properties of Countable Sets, Products and Powers of Countable Sets and A Countable Union of Countable Sets is Countable.

Throughout, a word of length $k$ is a map $[k]\to[n]$ (Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §words and Tuples in a Set), so two words of the same length $k$ are equal exactly when their components $w_{i}$, $i\in[k]$, agree; and by Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §words the empty word has no length, while every other word has exactly one length. We use freely that addition on $\mathbb{N}$ is associative and commutative (claims 3 and 4 of Arithmetic of Addition on the Natural Numbers).

Claim 1 (monoid). Step 1. The identities $\varnothing u=u$ and $u\varnothing=u$ are the first two cases of Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation. If $u$, $v$ have lengths $k$, $l$, then $uv$ has length $k+l$ by the same clause.

Step 2. If $u\neq\varnothing$, then $u$ has a length $k$; if $v=\varnothing$ then $uv=u\neq\varnothing$, and if $v$ has length $l$ then $uv$ has the length $k+l$, so $uv\neq\varnothing$. The case $v\neq\varnothing$ is symmetric. Hence $uv=\varnothing$ only if $u=v=\varnothing$.

Step 3 (associativity). If $u=\varnothing$, both sides equal $vz$; if $v=\varnothing$, both equal $uz$; if $z=\varnothing$, both equal $uv$ (Step 1). Now let $u,v,z$ have lengths $k,l,r$. By Step 1, $(uv)z$ has length $(k+l)+r$ and $u(vz)$ has length $k+(l+r)$, the same number. By claim 5 of Basic Properties of Initial Segments of the Natural Numbers (twice), every $i\in[k+l+r]$ is of exactly one of the forms (a) $i\in[k]$, (b) $i=k+j$ with $j\in[l]$, (c) $i=(k+l)+j$ with $j\in[r]$, and $[k]\subseteq[k+l]$, $[l]\subseteq[l+r]$, $[k+l]\subseteq[k+l+r]$. We compare components using Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation. (a) $((uv)z)_{i}=(uv)_{i}=u_{i}=(u(vz))_{i}$. (b) $((uv)z)_{k+j}=(uv)_{k+j}=v_{j}$, and $(u(vz))_{k+j}=(vz)_{j}=v_{j}$. (c) $((uv)z)_{(k+l)+j}=z_{j}$. Here $(k+l)+j=k+(l+j)$, and $l+j\in[l+r]$ because $j\le r$ implies $l+j\le l+r$ (claim 6 of Properties of the Order on the Natural Numbers); so $(u(vz))_{k+(l+j)}=(vz)_{l+j}=z_{j}$. Hence $(uv)z=u(vz)$.

Claim 2 (last letter). Let $w$ have length $S(k)$. By claim 5 of Properties of the Order on the Natural Numbers, $k<S(k)$, hence $k\le S(k)$, and $[k]\subseteq[S(k)]$ by claim 4 of Basic Properties of Initial Segments of the Natural Numbers. So the restriction $w'$ of $w$ to $[k]$ is a map $[k]\to[n]$, a word of length $k$. Let $j=w_{S(k)}\in[n]$ and let $(j)$ be the letter, the word of length $1$ with $(j)_{1}=j$. By Claim 1, $w'(j)$ has length $k+1=S(k)$ (identity 1 of Natural Numbers). By claim 3 of Basic Properties of Initial Segments of the Natural Numbers, $[S(k)]=[k]\cup\{S(k)\}$. For $i\in[k]$, $(w'(j))_{i}=w'_{i}=w_{i}$; and $(w'(j))_{S(k)}=(w'(j))_{k+1}=(j)_{1}=j=w_{S(k)}$. Hence $w=w'(j)$. Finally, if $w$ has length $1$, then $[1]=\{1\}$ (claim 2 of Basic Properties of Initial Segments of the Natural Numbers) and $w=(j)$ with $j=w_{1}$, since both are maps $[1]\to[n]$ with the same value at $1$.

Claim 3 (reversal). For $k\in\mathbb{N}$ and $i\in[k]$ let $\rho_{k}(i)$ be the unique $j\in[k]$ with $i+j=k+1$ (Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §reversal), so $(w^{\mathrm{rev}})_{i}=w_{\rho_{k}(i)}$ for $w$ of length $k$.

Step 1 ($\rho_{k}$ is an involution). If $j=\rho_{k}(i)$, then $j+i=i+j=k+1$ with $i\in[k]$, so $\rho_{k}(j)=i$ by the uniqueness in Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §reversal. Thus $\rho_{k}(\rho_{k}(i))=i$.

Step 2 (double reversal). $(\varnothing^{\mathrm{rev}})^{\mathrm{rev}}=\varnothing$. If $w$ has length $k$, then $w^{\mathrm{rev}}$ and $(w^{\mathrm{rev}})^{\mathrm{rev}}$ have length $k$, and $((w^{\mathrm{rev}})^{\mathrm{rev}})_{i}=(w^{\mathrm{rev}})_{\rho_{k}(i)}=w_{\rho_{k}(\rho_{k}(i))}=w_{i}$ by Step 1.

Step 3 (letters). For $k=1$, $[1]=\{1\}$ and $1+1=1+1$, so $\rho_{1}(1)=1$ and $((j)^{\mathrm{rev}})_{1}=(j)_{1}$; thus $(j)^{\mathrm{rev}}=(j)$.

Step 4 (reversal of a product). If $u=\varnothing$, then $(uv)^{\mathrm{rev}}=v^{\mathrm{rev}}=v^{\mathrm{rev}}\varnothing=v^{\mathrm{rev}}u^{\mathrm{rev}}$ by Claim 1 and $\varnothing^{\mathrm{rev}}=\varnothing$; the case $v=\varnothing$ is symmetric. Let $u,v$ have lengths $k,l$. Then $(uv)^{\mathrm{rev}}$ has length $k+l$ and $v^{\mathrm{rev}}u^{\mathrm{rev}}$ has length $l+k=k+l$ (Claim 1). By claim 5 of Basic Properties of Initial Segments of the Natural Numbers, each $i\in[l+k]$ satisfies either (a) $i\in[l]$ or (b) $i=l+m$ with $m\in[k]$; also $[k]\subseteq[k+l]$. (a) Let $j=\rho_{l}(i)$, so $i+j=l+1$ and $(v^{\mathrm{rev}}u^{\mathrm{rev}})_{i}=(v^{\mathrm{rev}})_{i}=v_{j}$. Now $i+(k+j)=k+(i+j)=k+(l+1)=(k+l)+1$, and $k+j\in[k+l]$ as $j\le l$ gives $k+j\le k+l$ (claim 6 of Properties of the Order on the Natural Numbers); so $\rho_{k+l}(i)=k+j$ and $((uv)^{\mathrm{rev}})_{i}=(uv)_{k+j}=v_{j}$. (b) Let $j=\rho_{k}(m)$, so $m+j=k+1$ and $(v^{\mathrm{rev}}u^{\mathrm{rev}})_{l+m}=(u^{\mathrm{rev}})_{m}=u_{j}$. Now $(l+m)+j=l+(k+1)=(k+l)+1$ and $j\in[k]\subseteq[k+l]$, so $\rho_{k+l}(l+m)=j$ and $((uv)^{\mathrm{rev}})_{l+m}=(uv)_{j}=u_{j}$. Hence $(uv)^{\mathrm{rev}}=v^{\mathrm{rev}}u^{\mathrm{rev}}$.

Step 5. By Step 2 the map $w\mapsto w^{\mathrm{rev}}$ is its own two-sided inverse, so it is a bijection of $W_{n}$ onto $W_{n}$ by claim 3 of Inverse of a Bijection; it preserves length by Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §reversal.

Claim 4 (factorisations). Step 1. $\varnothing\varnothing=\varnothing$, and if $uv=\varnothing$ then $u=v=\varnothing$ by Claim 1; so $F(\varnothing)=\{(\varnothing,\varnothing)\}$, which is nonempty and finite (claim 2 of Basic Properties of Finite Sets).

Step 2. Let $w$ have length $k$. Then $(\varnothing,w)\in F(w)$ by Claim 1, so $F(w)\neq\emptyset$. Let $(u,v)\in F(w)$ with $u\neq\varnothing$, of length $i$. If $v=\varnothing$ then $u=w$, so $i=k$ by uniqueness of length. If $v$ has length $l$, then $w=uv$ has length $i+l$ (Claim 1), so $k=i+l$ and $i<k$ by claim 6 of Properties of the Order on the Natural Numbers. In both cases $i\le k$, i.e. $i\in[k]$. Symmetrically, if $v\neq\varnothing$ has length $l$, then $l=k$ (if $u=\varnothing$) or $k=i+l=l+i$ and $l<k$; so $l\in[k]$.

Step 3. Let $U=\bigcup_{i\in[k]}[n]^{i}$ and $P=U\cup\{\varnothing\}$. The set $[n]$ is nonempty and finite (claim 1 of Basic Properties of Initial Segments of the Natural Numbers, claim 1 of Basic Properties of Finite Sets), so each $[n]^{i}$ is finite by claim 3 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets; $[k]$ is nonempty and finite likewise; so $U$ is finite by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §finite-union, $P$ is finite by claim 1 of Peeling an Element off a Finite Set, and Unions of Finite Sets, and $P\times P$ is finite by claim 1 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets. By Step 2, $F(w)\subseteq P\times P$, so $F(w)$ is finite by claim 3 of Basic Properties of Finite Sets.

Claim 5 (products). Let $C=\{uv:u\in A,\ v\in B\}$. If $A=\emptyset$ or $B=\emptyset$, then $C=\emptyset$, which is finite. Otherwise $A\times B$ is finite by claim 1 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets and nonempty, so it has $N$ elements for some $N\in\mathbb{N}$ (Finite Set). The map $q:A\times B\to C$, $q((u,v))=uv$, is well defined by Characteristic Property of the Ordered Pair and surjective by the definition of $C$; so $C$ is finite by claim 4 of Basic Properties of Finite Sets.

Claim 6 (countability). The set $[n]$ is finite (as in Claim 4, Step 3), hence countable by claim 2 of Basic Properties of Countable Sets. For $k\in\mathbb{N}$ let $X_{k}=[n]^{k}\subseteq W_{n}$; it is countable by claim 2 (powers) of Products and Powers of Countable Sets. So $(X_{k})_{k\in\mathbb{N}}$ is a family of countable subsets of $W_{n}$ (Family and Subfamily of Subsets of a Set), and $X=\bigcup_{k\in\mathbb{N}}X_{k}$ is countable by A Countable Union of Countable Sets is Countable. By Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §words, $W_{n}=X\cup\{\varnothing\}$, which is countable by claim 6 (adjoining a point) of Basic Properties of Countable Sets, applied with $S=W_{n}$ and $z=\varnothing$. $\blacksquare$