Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.