Sei \(A\) ein Alphabet, \(A^*\) die Menge aller Wörter mit Buchstaben aus \(A\) und \(\leq_{AFS}\) eine Relation auf \(A^*\) definiert durch \(x\leq_{AFS} y \Leftrightarrow \text{x ist ein Anfangsstück von y} \Leftrightarrow \text{Für } x=x_1...x_n \text{ und } y=y_1...y_m \text{ mit } x_1,...,x_n,y_1,...,y_m\in A \text{ folgt } n\leq m \text{ und } y_1=x_1 \land ... \land y_n=x_n\).
z.Z.: \(\leq_{AFS}\) ist eine (Halb-)Ordnung.
Reflexivität: Für ein Wort \(x=x_1...x_n\) gilt offensichtlich \(x\leq_{AFS} x\) (jedes Wort ist Anfangsstück von sich selbst).
Antisymmetrie: Seien \(x=x_1...x_n\) und \(y=y_1...y_m\) sowie \(x\leq_{AFS} y\) und \(y\leq_{AFS} x\).
Dann folgt wegen \(x\leq_{AFS} y\), dass \(n\leq m\) und wegen \(y\leq_{AFS} x\) folgt \(m\leq n\), d.h. insgesamt \(n=m\), die Wörter sind also gleichlang.
Aus \(x\leq_{AFS} y\) folgt weiter \(y_1=x_1 \land ... \land y_n=x_n\), d.h. alle Buchstaben beider Wörter stimmen überein, sodass insgesamt \(x=y\).
Transitivität: Seien \(x=x_1...x_n\), \(y=y_1...y_m\) und \(z=z_1...z_k\) mit \(x\leq_{AFS} y\) und \(y\leq_{AFS} z\).
Dann folgt wegen \(x\leq_{AFS} y\), dass \(n\leq m\) und wegen \(y\leq_{AFS} z\) folgt \(m\leq k\), insgesamt also \(n\leq m\leq k\) und damit \(n\leq k\). Das Wort \(z\) ist also mindestens so lang wie \(x\).
Wegen \(x\leq_{AFS} y\) folgt weiter \(y_1=x_1 \land ... \land y_n = x_n\) und wegen \(y\leq_{AFS} z\) mit \(n\leq k\) zusätzlich auch \(z_1=y_1\overset{!}{=}x_1 \land ... \land z_n=y_n \overset{!}{=} x_n \land ... \land z_k=y_k\).
Es folgt also \(z_1=x_1 \land ... \land z_n=x_n\), weshalb insgesamt \(x\leq_{AFS} z\).
Die Halbordnung ist insbesondere nicht total, denn z.B. folgt für \(A=\{a,b\}\), dass weder \(a\leq_{AFS} b\), noch \(b\leq_{AFS} a\).
Minimale Elemente sind alle Wörter in \(A^*\) mit genau einem Buchstaben (für jedes Wort \(x\in A^*\) mit \(x=x_1...x_n\) und \(n>1\) gäbe es das einbuchstabige Wort \(x_1\) mit \(x_1\leq_{AFS} x\), \(x\) wäre also insbesondere nicht minimal).
