Un amigo me acaba de hacer esta misma pregunta. Aunque tengo cierta formación en combinatoria, nunca he oído hablar del "Enigma de Seetapun", que, supuestamente, está relacionado con el teorema de Ramsey. Una búsqueda rápida en Google no proporciona nada útil, ni tampoco Math.StackExchange me ha ayudado. ¿Alguien sabe qué es y qué importancia tiene su solución/prueba/refutación?
Respuestas
¿Demasiados anuncios?
La pregunta parece referirse a la siguiente forma especial del Teorema de Ramsey:
$\mathsf{RT}^2_2$ para cada $2$ -coloración de los pares desordenados de $\mathbb{N}$ hay un subconjunto infinito de $\mathbb{N}$ para el que todos los pares desordenados reciben el mismo color.
que es un caso especial de
$\mathsf{RT}^n_k$ para cada $k$ -coloración del desordenado $n$ -tuplas de $\mathbb{N}$ hay un subconjunto infinito de $\mathbb{N}$ para el que todos los desordenados $n$ -tuplas reciben el mismo color.
La fuerza computable del teorema de Ramsey infinito fue estudiada por primera vez por Jockusch (1972). Cuando se interpreta en una terminología moderna que no existía entonces, el resultado de Jockusch es que $\mathsf{RT}^n_k$ equivale a $\mathsf{ACA}_0$ siempre que $n \geq 3$ y $k \geq 2$ . La equivalencia es sobre el sistema base estándar $\mathsf{RCA}_0$ que se asume en el resto de este post. Como corolario, $\mathsf{ACA}_0$ prueba $\mathsf{RT}^2_k$ para todos $k \geq 2$ .
Posteriormente, Hirst (1987) caracterizó la fuerza de los principios de la forma $\mathsf{RT}^1_k$ . Los resultados separados de Jockusch y Hirst dejan un hueco para el exponente $2$ y, en particular, para $\mathsf{RT}^2_2$ . La fuerza matemática inversa exacta de $\mathsf{RT}^2_2$ es algo misterioso, aunque no sé si alguien lo llama "enigma". Ha resultado ser un problema abierto especialmente difícil.
El primer resultado se debe a Seetapun (publicado como Seetapun y Slaman (1995)), que demostró que $\mathsf{RT}^2_2$ no implica $\mathsf{ACA}_0$ . El hecho de que este resultado, aparentemente débil, fuera el único que se pudo obtener, indica la dificultad de encontrar la fuerza exacta de $\mathsf{RT}^2_2$ con métodos conocidos. La prueba de Seetapun utilizó un intrincado argumento de forzamiento. Las ideas que subyacen a este argumento se han ido aclarando y ampliando progresivamente, y ahora se entienden bien; el documento más reciente sobre esto es el de Dzhafarov y Jockusch (2009).
El principio $\mathsf{WKL}_0$ dice que todo subárbol infinito de $2^{<\mathbb{N}}$ tiene un recorrido infinito. $\mathsf{WKL}_0$ es uno de los "cinco grandes" sistemas de matemáticas inversas, y es el punto de comparación natural para los principios más débiles que $\mathsf{ACA}_0$ como $\mathsf{RT}^2_2$ .
Cholak, Jockusch y Slaman (2001) realizaron el siguiente avance significativo en $\mathsf{RT}^2_2$ . Entre otros muchos nuevos resultados, demostraron que $\mathsf{RT}^2_2$ no es demostrable en $\mathsf{WKL}_0$ porque $\mathsf{WKL}_0$ no demuestra el principio $\mathsf{COH}$ que es demostrable a partir de $\mathsf{RT}^2_2$ . El principio $\mathsf{COH}$ es un enunciado formalizado de un teorema de la teoría de la recursión sobre la existencia de $r$ -conjuntos cohesivos.
Los resultados que he mencionado dejan abierta la cuestión de si $\mathsf{RT}^2_2$ implica $\mathsf{WKL}_0$ . Esto fue resuelto recientemente por Liu en 2011. Liu demostró en un artículo aún no publicado que $\mathsf{RT}^2_2$ no implica $\mathsf{WWKL}_0$ que es la restricción de $\mathsf{WKL}_0$ a los árboles de medida positiva, y que es estrictamente más débil que $\mathsf{WKL}_0$ . Así, combinando los resultados, $\mathsf{RT}^2_2$ y $\mathsf{WKL}_0$ son mutuamente independientes.
Según tengo entendido, Liu demostró esto de forma independiente mientras era estudiante en la Universidad Central del Sur (China), sin un asesor en lógica ni ninguna formación de posgrado en lógica. Liu presentó su resultado en el Taller de matemáticas inversas en la Universidad de Chicago en septiembre de 2011. La página web diapositivas de esa charla están disponibles en Internet, pero son bastante técnicas. La prueba utiliza otro intrincado argumento de forzamiento.
Según tengo entendido, el artículo de Liu se presentó a una revista algún tiempo antes del taller, los resultados han sido verificados por los árbitros, y el artículo se publicará una vez que esté en su forma final.
Citas
-
Cholak, Peter A.; Jockusch, Carl G.; Slaman, Theodore A. Sobre la fuerza del teorema de Ramsey para los pares . J. Symbolic Logic 66 (2001), nº 1, 1-55. MR1825173 (2002c:03094)
-
Dzhafarov, Damir D.; Jockusch, Carl G., Jr. Teorema de Ramsey y evasión de conos . J. Symbolic Logic 74 (2009), nº 2, 557-578. MR2518811 (2010e:03052)
-
Hirst, Jeffry Lynn. Combinatoria en subsistemas de aritmética de segundo orden . Tesis doctoral, Universidad Estatal de Pensilvania. 1987. 153 pp.
-
Jockusch, Carl G., Jr. Teorema de Ramsey y teoría de la recursión . J. Symbolic Logic 37 (1972), 268-280. MR0376319 (51 #12495)
-
Seetapun, David; Slaman, Theodore A. Sobre la fuerza del teorema de Ramsey . Número especial: Modelos de aritmética. Notre Dame J. Formal Logic 36 (1995), no. 4, 570-582. MR1368468 (96k:03136)
Andrew Kennan
Puntos
8221
ha sido resuelto (se ha demostrado que es erróneo) por un estudiante universitario chino. Puede que quieras consultar su artículo que viene en http://www.aslonline.org/journals-journal.html
