¿Qué tiene de especial el lema de Higman?

Question

¿Hay algún ejemplo motivador de una aplicación del Lemma de Higman que ponga de manifiesto la verdadera belleza e importancia del mismo? ¿Qué es lo que ha hecho que tanta gente se interese por él? Para un ejemplo, estaba pensando que dado un conjunto unitario $\{1\}$ con el orden lineal $\preceq$ de tal manera que básicamente $1\preceq1$ . Ahora toma el monoide libre de este singleton y obtienes un conjunto infinito $\{1,2,3,\cdots\}$ que son los números naturales positivos $\mathbb{N}_+$ . Si definimos el mismo orden lineal $\preceq$ en el monoide libre $\mathbb{N}_+$ obtenemos $1\preceq2\preceq\cdots$ . Y por lo tanto el orden en el conjunto de los singletons $\{1\}$ satisface el monoide libre $\mathbb{N}_+$ también. No estoy seguro de la importancia de este ejemplo, pero recuerdo que fue así como llegué a entender el lema. También pensé en el enorme rango de flexibilidad de este lema, pero no se me ocurrió nada que abarcara completamente la verdadera belleza detrás de este maravilloso lema. Como encontrar una generalización/construcción en la teoría de categorías, que es en lo que estoy trabajando actualmente, y así abrir nuevas puertas para el descubrimiento.

Answer 1

No estoy seguro de que sea la respuesta que esperas, pero aquí tienes una importante aplicación del lema de Higman en la teoría del lenguaje formal. Sea $A$ sea un alfabeto finito y que $A^*$ sea el monoide libre en $A$ . El producto barajado de dos idiomas $U$ y $V$ en $A$ es la lengua $$\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*}$$ Tenga en cuenta que en esta definición, $\color{red}{u_1, \ldots, u_n}$ así como $\color{blue}{v_1, \dots, v_n}$ pueden ser palabras vacías. El siguiente resultado es una consecuencia del lema de Higman.

Teorema . Para cada idioma $L$ La lengua $L \operatorname{ш} A^*$ es un lenguaje regular .

Esto da ejemplos de lenguajes que se sabe que son regulares, pero para los que no se conoce ningún autómata finito (o expresión regular) que los represente, una situación bastante inquietante.

Este resultado no utiliza toda la fuerza del lema de Higman, sólo el hecho de que el orden de las subpalabras en $A^*$ es un bien cuasi-ordenado.

Definición . Una palabra $u = \color{red}{a_1a_2 \dotsm a_n}$ (donde $a_1, a_2, \dots a_n \in A$ ) es un subpalabra de una palabra $v$ si existe $v_0, v_1, \dots, v_n \in A^*$ tal que $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$ .

Por el lema de Higman, el orden de las subpalabras en $A^*$ es un bien cuasi-ordenado. Por lo tanto, para cada lengua $L$ el conjunto $F$ de palabras mínimas de $L$ (para la ordenación de subpalabras) es un conjunto finito $F$ y $L \operatorname{ш} A^* = F \operatorname{ш} A^*$ . Ahora es fácil demostrar que $F \operatorname{ш} A^*$ es un lenguaje regular.

Answer 2

En una línea similar a la respuesta de Pin.

El conjunto de todas las cadenas que incluyen alguna cadena como subpalabra (o subsecuencia) se denomina Ideal de Barajado (principal). La clase de conjuntos de cadenas que son combinaciones booleanas de un conjunto finito de IS se denomina conjuntos de cadenas comprobables a trozos. Si se restringe a las intersecciones de los complementos de los IS, se obtienen los conjuntos de cadenas estrictamente fragmentables.

A través de una secuencia de lemas, todos ellos fáciles excepto el lema de Higman, resulta ser exactamente la clase de conjuntos de cadenas que son cerrados bajo subsecuencia.

Ver:

@InCollection{, author = {James Rogers y Jeffrey Heinz y Gil Bailey y Matt Edlefsen y Molly Visscher y David Wellcome y Sean Wibel}, title = {Sobre lenguajes comprobables a trozos en sentido estricto}, booktitle = {La matemática del lenguaje: Revised Selected Papers from the 10th and 11th Biennial Conference on the Mathematics of Language}, publisher = {FoLLI/Springer}, año = 2010, editor = {Christian Ebert y Gerhard J{"a}ger y Jens Michaelis}, volumen = 6149, serie = {LNCS/LNAI}, páginas = {255-265}}

Jim Rogers