Overlapping of admissible words

Question

Setting:

Self-learning model theory, I'm reading these lecture notes. On p. 18, the author gives the definition of words starting at position as:

Given words $v, w \in F^{*}$ and $i \in\{1, \ldots$, length $(w)\}$, we say that $v$ occurs in $w$ at starting position $i$ if $w=w_{1} v w_{2}$ where $w_{1}, w_{2} \in F^{*}$ and $w_{1}$ has length $i-1$. (For example, if $f, g \in F$ are distinct, then the word $f g f$ has exactly two occurrences in the word $f g f g f$, one at starting position $1$, and the other at starting position $3$; these two occurrences overlap, but such overlapping is impossible with admissible words, see exercise $5$ at the end of this section.)

The exercise $5$ that makes the last statement precise is as follows:

Let $w$ be an admissible word and $1 \leq i<i^{\prime} \leq$ length $(w)$. Let $v$ and $v^{\prime}$ be the admissible words that occur at starting positions $i$ and $i^{\prime}$ respectively in $w$. Then these occurrences are either nonoverlapping, that is, $i-1+$ length $(v)<i^{\prime}$, or the occurrence of $v^{\prime}$ is entirely inside that of $v$, that is, $$ i^{\prime}-1+\text {length}\left(v^{\prime}\right) \leq i-1+\text { length }(v) $$

Question:

Clearly there does not exist an admissible word that is a proper initial segment of another admissible word. To prove the statement in question, I would perhaps have to use Lemma 2.1.6., i.e. that there is a unique admissible word that occurs in $w$ at starting position $i$? I do not know how to really proceed with the proof and would appreciate any help.

Answer 1

Suppose we did have some non-contained overlapping: we would be able to write $w = a b c d e$, where $bc = v$ is admissible, $cd = v'$ is admissible, $c$ is nonempty, and $d$ is nonempty.

Consider the following characterization of admissible words:

We already have the arity map $A : F \to \mathbb{N}$. Define the "modified arity map" by $M : F \to \mathbb{Z}$, $M(f) = A(f) - 1$. Lift $M$ to a monoid homomorphism $M^* : F^* \to \mathbb{Z}$ - that is, where $M^*(f) = M(f)$ for all $f \in F$, $M^*(\epsilon) = 0$, and $M^*(ab) = M^*(a) + M^*(b)$ for all $a, b$. In other words, to compute $M^*(w)$, sum $M(c)$ for each character occurence $c$ in $w$.

Then $w \in F^*$ is an admissible word iff

1. $M^*(w) = -1$
2. For all proper prefixes $v$ of $w$, $M^*(v) \geq 0$.

For this proof, we only need the forward direction: that is, if $w$ is admissible, then (1) and (2) are satisfied. This is a straightforward structural induction on $w$.

In particular, since $c$ is a proper prefix of $cd$ and $cd$ is admissible, we have $M^*(c) \geq 0$. And since $b$ is a proper prefix of $bc$ and $bc$ is admissible, we have $M^*(b) \geq 0$. Then $-1 = M^*(bc) = M^*(b) + M^*(c) \geq 0$. Contradiction.

Answer 2

You'd better start from your reference's definition of admissible word:

A word on F is said to be admissible if it can be obtained by applying the following rules: (i) If $f ∈ F$ has arity $0$, then $f$ viewed as a word of length $1$ is admissible. (ii) If $f ∈ F$ has arity $m > 0$ and $t_1$, . . . , $t_m$ are admissible words on F, then the concatenation $ft_1 . . .t_m$ is admissible.

So your above example $fgfgf$ cannot be a single admissible word $w$ according to your reference from its inductive definition above since we must have $arity(f)=length(w)-1=4$, and obviously $f$'s arguments $t_1,...,t_m$ cannot be simply the same as $f$ syntactically...

And you're right that "there does not exist an admissible word that is a proper initial segment of another admissible word" which the author also mentioned earlier. So for your exercise with above understanding, it's easy to see that admissible words $v$ and $v'$ in a single admissible word $w$ can be either non-overlapping or the occurrence of $v′$ is entirely inside that of $v$ as a non-initial segment.

---

Appendum: I'll fill in more details for an elementary proof from the feedback of comment below since some users may not be totally clear.

A critical info is the first premise of your exercise:

Let w be an admissible word and $1 \leq i<i^{\prime} \leq$ length $(w)$. Let $v$ and $v^{\prime}$ be the admissible words that occur at starting positions $i$ and $i^{\prime}$ respectively in $w$.

So we must have $w=ft_1...t_n$ where $f \in F$ has arity $n > 0$ and $t_1,...,t_n$ are admissible words from its definition (ii) I've quoted above. From Lemma 2.1.6 we easily know $v, v'$ must be unique, and thus we only need to show they cannot overlap when $i' \leq i-1+ length(v) ~(*)$. As user @AlexKruckman pointed out below for a complete formal proof we need to apply induction on terms of the single admissible word $w$. The base case for 0 terms is obvious. For the inductive step per the remark below your Lemma 2.1.6, we define $l_j := 1 + length(t_1) + · · · + length(t_j), j = 0, . . . , n$ and w.l.o.g suppose $l_{j−1} < i ≤ l_j$, from the proof of Lemma 2.1.6 shows $v$ is entirely inside $t_j$, that is, $i − 1 + length(v) ≤ l_j$. And per inequality $(*)$ above we easily arrive at $i' ≤ l_j$, which just means if $v,v′$ overlap then they must both be entirely inside $t_j$. Done by the inductive hypothesis...