This installment in a series on ordinal numbers explores 'productive' programs (ones that will eventually print every item in an infinite set) and the difference between lexicographic and shortlex string ordering. It shows why lexicographic order fails to be well-founded for certain infinite string sets (no productive program can enumerate them, and some sets lack a lexicographically first element), while shortlex order (comparing by length first, then lexicographically) is always well-founded, guaranteeing a first element for any set of strings and enabling productive, decidable enumeration programs. The piece sets up a following article on shortlex order applied to sequences of ordinals.
Questions this post answers
Why can't lexicographic order be used to enumerate an infinite set of strings with a program?
Because lexicographic order is not well-founded for strings, meaning some infinite sets of strings have no first element in that order. For example, the set {11, 101, 1001, 10001, ...} in lexicographic order has no smallest string, so a program can never even decide what to print first, and other sets get stuck endlessly printing one prefix family without ever reaching strings that should logically come later. Anyone reasoning about enumeration algorithms can find deeper ordinal theory explainers curated on daily.dev.
What is shortlex order and why is it useful for enumerating strings?
Shortlex order compares strings by length first, using shorter strings before longer ones, and only falls back to standard lexicographic comparison when two strings have equal length. This ordering is well-founded, meaning every set of strings has a definite first element, since only finitely many strings exist at or below any given length, which makes it possible to write a productive program that prints every string in the set eventually. Developers exploring ordering algorithms and string enumeration can track related deep dives on daily.dev.
What does it mean for a program that prints an infinite list to be 'productive'?
A productive program is one guaranteed to eventually print every item in its target infinite set, no matter how long that takes, even though it never actually finishes running. A counterexample is a program that tries to print all odd numbers before switching to even numbers: it never gets to print any even number because it never finishes the odd ones, so it is not productive despite running forever. Those digging into computability and enumeration theory can follow more explainers like this on daily.dev.