Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application

Resumen Técnico: "El teorema de Hindman no codifica $\emptyset^{(\omega)}$ en una sola aplicación"

Planteamiento del Problema
El artículo aborda la complejidad de la teoría de la computabilidad del Teorema de Hindman (HT), específicamente en lo que respecta a la fuerza de las soluciones que produce en relación con el coloreado de entrada. El Teorema de Hindman establece que para todo coloreado finito de los números naturales $\mathbb{N}$, existe un conjunto infinito $H$ tal que el conjunto de todas las sumas finitas de elementos distintos de $H$ (denotado como $FS(H)$) es monocromático.

Trabajos previos establecieron los siguientes límites:

1. Límite Superior: Blass, Hirst y Simpson (1987) demostraron que para todo coloreado computable, existe una solución computable a partir del salto $\omega$ del conjunto vacío, $\emptyset^{(\omega)}$.
2. Límite Inferior: Los mismos autores demostraron que existe un coloreado computable donde toda solución computa el conjunto de parada $\emptyset'$. Más tarde, Liao (2026) mejoró esto al mostrar que para algunos coloreados computables, no existe una solución $\Pi^0_3$.

La cuestión abierta central abordada por este artículo es si el límite superior de $\emptyset^{(\omega)}$ es óptimo para una sola aplicación del teorema. Específicamente, ¿admite cada instancia aritmética del Teorema de Hindman una solución que no computa $\emptyset^{(\omega)}$?

Metodología
Los autores emplean una técnica de forcing adaptada de la prueba combinatoria de Towsner para el Teorema de Hindman. La metodología consta de los siguientes componentes:

1. Reformulación: El problema se traduce al lenguaje del Teorema de la Unión Finita (FUT), que es computablemente equivalente a HT. Esto implica colorear el conjunto de los subconjuntos finitos no vacíos de $\mathbb{N}$, $P_{fin}(\mathbb{N})$, y buscar una secuencia de bloques infinita $H$ tal que el conjunto de las uniones finitas $FU(H)$ sea monocromático.
2. Árboles de Towsner y Coincidencias (Matching): Los autores utilizan los conceptos de "medio-match" (half-match) y "full-match" de Towsner. Un conjunto finito $F$ realiza un medio-match con una secuencia de bloques infinita $X$ si para cada unión finita $b \in FU(X)$, existe un $a \in F$ tal que $f(a \cup b) = f(b)$. Un full-match requiere que $f(a) = f(a \cup b) = f(b)$.
   • Construyen una "secuencia de Towsner", una secuencia anidada de medio-matches que induce una estructura de árbol (el árbol de Towsner).
   • Establecen que para un coloreado aritmético $f$, existe una secuencia de Towsner computable desde $f''$.
3. Noción de Forcing: Se define una nueva noción de forcing utilizando "condiciones-P", que son pares $(I, X)$ donde $I$ es un conjunto finito de secuencias de bloques y $X$ es un reservorio infinito. Una condición es "f-matching" si satisface una propiedad de extensión específica relacionada con el coloreado.
4. Control del Primer Salto (First-Jump Control): La innovación central es el diseño de una "pregunta de forcing" con propiedades de definibilidad específicas. Esto permite la construcción de un filtro genérico donde la solución resultante $G$ evita computar un conjunto no aritmético específico $C$. El proceso de forcing está diseñado para controlar el primer salto de la solución, asegurando que la solución permanezca dentro de un grado aritmético específico relativo al input, mientras evita el cono objetivo.
5. Diagonalización: Para asegurar que $C \not\leq_T G$, los autores satisfacen los requisitos $R^C_e: W^G_e \neq C$. Al analizar la pregunta de forcing para fórmulas $\Sigma^0_1$, demuestran que para cualquier conjunto no aritmético $C$ y coloreado aritmético, es posible extender las condiciones para forzar a que $G$ difiera de $C$ en algún elemento.

Contribuciones Clave y Resultados

1. Teorema Principal (Evitación de Conos/Cone Avoidance): El resultado principal (Teorema Principal 1.5) establece: Sea $C$ un conjunto de grado no aritmético. Para todo $\ell \geq 1$ y todo coloreado $f: \mathbb{N} \to \ell$ (o $P_{fin}(\mathbb{N}) \to \ell$) de grado aritmético, existe un conjunto infinito $H$ tal que $FS(H)$ es $f$-monocromático y $C \not\leq_T H$.

   • Corolario: Al establecer $C = \emptyset^{(\omega)}$, los autores demuestran que cada instancia aritmética del Teoremo de Hindman admite una solución que no computa $\emptyset^{(\omega)}$. Esto demuestra que el límite superior computacionalmente de $\emptyset^{(\omega)}$ no es óptimo para una sola aplicación.

2. Limitaciones de la Iteración: Los autores aclaran que este resultado no implica que el Teorema de Hindman sea más débil que $\text{ACA}^+_0$ en matemáticas reversas. La evitación de conos se mantiene para la reducibilidad de Turing ($C \not\leq_T H$) pero no necesariamente para la reducibilidad aritmética. Por lo tanto, el teorema no puede ser iterado para construir un modelo-$\omega$ del Teorema de Hindman que excluya $\emptyset^{(\omega)}$.

3. Coloreados Simples: El artículo investiga las restricciones de HT a "coloreados simples" (coloreados donde el color de una unión depende solo del color de los componentes y sus posiciones relativas).

   • Demuestran que la restricción del Teorema de la Unión Finita a coloreados simples es equivalente a $\text{ACA}_0$ sobre $\text{RCA}_0$.
   • Muestran que el coloreado específico utilizado por Blass, Hirst y Simpson para probar el límite inferior es un coloreado simple.

4. Complejidad de los Árboles de Towsner: Los autores demuestran (Proposición 2.24) que para el coloreado específico construido por Blass, Hirst y Simpson, toda secuencia de Towsner computa $\emptyset'$. Esto sugiere que, si bien los árboles de Towsner son una herramienta poderosa, su existencia para ciertos coloreados computables codifica intrínsecamente un poder computacional significativo, aunque esto no excluye la existencia de otras pruebas o full-matches que no dependan de tales árboles.

Significado
El artículo resuelve la cuestión de si el límite superior de $\emptyset^{(\omega)}$ es ajustado para aplicaciones únicas del Teorema de Hindman. Al demostrar que se pueden evitar conos no aritméticos, los autores muestran que el teorema no requiere inherentemente la fuerza total del salto $\omega$ para producir una solución para inputs aritméticos. Esto refina la comprensión de su contenido computacional, distinguiendo entre la complejidad requerida para encontrar una solución frente a la complejidad requerida para encontrar una solución que compute conjuntos de grados altos específicos. El trabajo también tiende un puente entre las pruebas combinatorias (de Towsner) y las técnicas de forcing para lograr un control preciso sobre los grados de Turing de las soluciones.