# What is so special about Higman's Lemma?

Is there a motivational example of an application of Higman's Lemma that brings out the true beauty and importance of Higman's Lemma? What is the thing that made so many people care about it? For an example, I was thinking that given a singleton set $\{1\}$ with the linear order $\preceq$ such that basically $1\preceq1$. Now take the free monoid of this singleton and you get an infinite set $\{1,2,3,\cdots\}$ which is the positive natural numbers $\mathbb{N}_+$. If we define the same linear order $\preceq$ on the free monoid $\mathbb{N}_+$, we get $1\preceq2\preceq\cdots$. And therefore the order on the singleton set $\{1\}$ satisfies the free monoid $\mathbb{N}_+$ as well. I am not sure how important this example is but I remember that this is how I came to understand the lemma. I also thought of the huge range of flexibility to this lemma but could not come up with anything to fully encompass the true beauty behind this wonderful lemma. Like finding a generalization/construction in category theory, which is what I am currently working on, and thus opening new doors for discovery.

• you should read mathematik.uni-muenchen.de/~schwicht/papers/jaeger14/higman.pdf and en.wikipedia.org/wiki/Well-quasi-ordering, the lemma looks to be about the proof by induction : is it allowed to prove something by induction on a set $S$ using a well-quasiorder $\le$ on $S$ ? that is if "$P(x)$ is true and $x \le y$ implies $P(y)$ is true", is it enough to prove $P(x)$ for finitely many $x \in S$ to prove $P(x)$ is true for every $x \in S$ ? – reuns Feb 12 '16 at 2:57
• @user1952009 I already read those a long time ago and found nothing. In fact I have pretty much read most if not all Higman's-Lemma-related papers. So I need more. – Julian Rachman Feb 12 '16 at 3:17
• @JulianRachman If you are looking for more references you haven't seen, you're going to have to list what you have already read. At least, if you don't want to force everyone to play a rude guessing game that makes everyone hate you. Good luck – rschwieb Feb 12 '16 at 5:01
• this link has compelling stuff about quasi orders, which should in turn support Higman's lemma – rschwieb Feb 12 '16 at 5:13
• @rschwieb Ok. Well I am not asking for more references. I want to see motivational example(s) that bring out the beauty and importance of Higman's Lemma. It is all stated in my question with no mentioning of wanting "references." – Julian Rachman Feb 12 '16 at 7:39

Not sure this is the answer you expect, but here is an important application of Higman's lemma in formal language theory. Let $A$ be a finite alphabet and let $A^*$ be the free monoid on $A$. The shuffle product of two languages $U$ and $V$ over $A$ is the language \begin{multline*} U \operatorname{ш} V = \{ w \in A^* \mid w = \color{red}{u_1}\color{blue}{v_1} \cdots \color{red}{u_n}\color{blue}{v_n} \text{ for some words $\color{red}{u_1, \ldots, u_n}$} \\ \text{$\color{blue}{v_1, \ldots, v_n}$ of $A^*$ such that $\color{red}{u_1 \cdots u_n} \in U$ and $\color{blue}{v_1 \cdots v_n} \in V$} \}\,. \end{multline*} Note that in this definition, $\color{red}{u_1, \ldots, u_n}$ as well as $\color{blue}{v_1, \dots, v_n}$ can be empty words. The following result is a consequence of Higman's lemma.

Theorem. For each language $L$, the language $L \operatorname{ш} A^*$ is a regular language.

This gives examples of languages that are known to be regular, but for which there is no known finite automaton (or regular expression) representing them, a rather disturbing situation.

This result does not use the full strength of Higman's lemma, only the fact that the subword order on $A^*$ is a well-quasi-order.

Definition. A word $u = \color{red}{a_1a_2 \dotsm a_n}$ (where $a_1, a_2, \dots a_n \in A$) is a subword of a word $v$ if there exist $v_0, v_1, \dots, v_n \in A^*$ such that $v = v_0\color{red}{a_1}v_1\color{red}{a_2}v_2 \dotsm v_{n-1}\color{red}{a_n}v_n$.

By Higman's lemma, the subword order on $A^*$ is a well-quasi-order. Therefore, for each language $L$, the set $F$ of minimal words of $L$ (for the subword ordering) is a finite set $F$ and $L \operatorname{ш} A^* = F \operatorname{ш} A^*$. It is now easy to show that $F \operatorname{ш} A^*$ is a regular language.

• This is great. But you refer to this not bringing the "full strength" of the lemma. What do you think will bring out its "full strength"? – Julian Rachman Feb 13 '16 at 17:12
• I was thinking of an alphabet which is itself well-quasi ordered. – J.-E. Pin Feb 13 '16 at 17:18
• Go on. I think you are on to something. See I thought that the fact that Higman's Lemma is so usable in many areas of computation that if we bring out that aspect, it would be a good example. However I still think you are on to something. – Julian Rachman Feb 13 '16 at 19:23

In a vein similar to Pin's answer.

The set of all strings that include some string as a subword (or subsequence) is a called a (principal) Shuffle Ideal (SI). The class of stringsets that are Boolean combinations of a finite set of SIs is called the Piecewise Testable stringsets. If one restricts to intersections of the complements of SIs one gets the Strictly Piecewise stringsets.

Via a sequence of lemmas, all of them easy except Higman's lemma, this turns out to be exactly the class of stringsets that are closed under subsequence.

See:

@InCollection{, author = {James Rogers and Jeffrey Heinz and Gil Bailey and Matt Edlefsen and Molly Visscher and David Wellcome and Sean Wibel}, title = {On languages piecewise testable in the strict sense}, booktitle = {The Mathematics of Language: Revised Selected Papers from the 10th and 11th Biennial Conference on the Mathematics of Language}, publisher = {FoLLI/Springer}, year = 2010, editor = {Christian Ebert and Gerhard J{\"a}ger and Jens Michaelis}, volume = 6149, series = {LNCS/LNAI}, pages = {255-265}}

Jim Rogers