# Why is the D0L word a least fixed point?

Consider the finite alphabet $\sum=\{0,1,\cdots k-1\}$, the set $\sum^*$ of all words over it, and a mapping $T:\sum\to \sum^*$ such that each $i\in\sum$ is the initial symbol of $T(i)$. Now the natural order on $\sum$ gives a lexicographic order on $\sum^*$. We may extend $T$ to a map $T:\sum^*\to\sum^*$ by defining $T(v_1\cdots v_n)=T(v_1)\cdots T(v_n)$. Now we define the $D0L$ infinite word as the limit word of $0,T(0),T^2(0),T^3(0)\cdots$.

I want to establish that this is the least non-empty word $\sigma$ in lexicographic order such that $T(\sigma)=\sigma$. How can I establish that? By explicitly writing out the first few entries it is clear that this is a fixed point, but I am looking for a more formal proof.

Thanks.

-
The empty word comes earlier in lexicographic order and also satisfies $T(\varepsilon)=\varepsilon$. – Henning Makholm Oct 4 '12 at 15:49
@Henning Makholm: Thanks for pointing that out. I have edited the question to rule out this trivial case. – Shahab Oct 4 '12 at 16:14

Let $w_0=0$ and $w_{n+1}=T(w_n)$ for $n\in\Bbb N$.

Proposition. For each $n\in\Bbb N$, $w_{n+1}=w_nx$ for some $x\in\Sigma^*$.

Proof. Since $0$ is the initial symbol of $T(0)$, the result is clearly true for $n=0$. Let $n>0$ be minimal such that $w_n$ is not an initial segment of $w_{n+1}$. Then $w_n=w_{n-1}x$ for some $x\in\Sigma^*$, so $w_{n+1}=T(w_n)=T(w_{n-1})T(x)=w_nT(x)$, and the contradiction establishes the result. $\dashv$

We can therefore define the limit word $w\in{^{\Bbb Z^+}}\Sigma$ by $w(n)=i$ iff there is an $m\in\Bbb N$ such that $|w_m|\ge n$ and the $n$-th symbol of $w_m$ is $i$, and it’s clear that $\widehat T(w)=w$, where $\widehat T$ is the obvious extension of $T$ to ${^{\Bbb Z^+}}\Sigma$.

Now let $\preceq$ be the lexicographic order on ${^{\Bbb Z^+}}\Sigma$, and suppose that $u$ is a fixed point of $T$ such that $u\preceq w$; clearly $u(1)=0$. Since $T(u)=u$, it follows that $T(0)=w_1$ is an initial segment of $u$. More generally, if $w_n$ is an initial segment of $u$, then $w_{n+1}=T(w_n)$ is an initial segment of $u$, and it follows by induction that $u=w$. Thus, $w$ is the first non-empty fixed point of $T$ with respect to $\preceq$.

-
Thanks. If you don't mind I want to suggest a small correction. Please change $x_{n+1}=T(x_n)$ in the proposition to $w_{n+1}=T(w_n)$. – Shahab Oct 5 '12 at 3:01
@Shahab: I never saw a suggested edit; what did you have in mind? – Brian M. Scott Oct 5 '12 at 9:21
I edited that comment, (because the edit is too short so I could not suggest it myself). I believe in the last sentence of the proof of the proposition there is a typo. We must have $w_{n+1}=T(w_n)$. – Shahab Oct 5 '12 at 12:23
@Shahab: You’re absolutely right: my finger must have gone down instead of up. Thanks! – Brian M. Scott Oct 5 '12 at 12:27