Wörter/Lexikographische Ordnung/Beispiel

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es sei ein Alphabet und die Menge der Wörter über diesem Alphabet, also die Menge alle endlichen Ketten über oder eine Teilmenge davon, etwa die Menge der real existierenden Wörter. Auf sei eine totale Ordnung gegeben. Dann definiert man auf die sogenannte lexikographische Ordnung, indem für Wörter die Beziehung

( kommt im Lexikon vor ) genau dann gilt, wenn sie gleich sind oder wenn an der ersten Stelle von vorne gelesen, wo sich und unterscheiden, der Buchstabe von an dieser Stelle im Alphabet vor dem Buchstaben von an dieser Stelle kommt, was den Fall einschließen mag, dass an dieser Stelle keinen Buchstaben mehr hat („Vers“ kommt vor „Verstand“). Die lexikographische Ordnung ist eine totale Ordnung.