Constraint satisfaction problems, compactness and non-measurable sets

El artículo demuestra que la compacidad de una estructura relacional finita de ancho uno es demostrable en ZF, mientras que la compacidad de estructuras de mayor ancho implica la existencia de conjuntos no medibles en el espacio tridimensional.

Lo esencial

Imagina que el universo de las matemáticas es como una inmensa biblioteca llena de rompecabezas. Algunos rompecabezas son fáciles de resolver, otros son imposibles, y algunos requieren reglas mágicas que no siempre tenemos a mano.

El artículo que nos ocupa, escrito por Claude Tardif, explora una conexión fascinante y sorprendente entre tres mundos que parecen no tener nada que ver: los problemas de lógica (rompecabezas), las reglas fundamentales de la realidad (la teoría de conjuntos) y la física de lo que podemos medir (la teoría de la medida).

Aquí te lo explico como si fuera una historia, usando analogías sencillas.

1. El Rompecabezas Infinito (Compactación)

Imagina que tienes un rompecabezas gigante e infinito. La pregunta es: ¿Es posible armarlo completo?

En matemáticas, hay una regla llamada "Compactación". Dice algo así: "Si puedes armar cualquier pedacito finito de este rompecabezas gigante, entonces puedes armar el rompecabezas entero".

• La analogía: Piensa en un muro infinito. Si puedes construir cualquier muro pequeño de 10 ladrillos, ¿significa que puedes construir el muro infinito?
• El problema: Para algunos rompecabezas, la respuesta es "sí" y no necesitas magia. Para otros, la respuesta es "sí", pero solo si aceptas una regla mágica llamada "Axioma de Elección". Esta regla te permite hacer infinitas elecciones a la vez (como elegir un zapato izquierdo de cada uno de un millón de cajas infinitas) sin tener que explicar cómo lo haces.

2. La Diferencia entre "Fácil" y "Difícil" (Ancho 1 vs. Complejidad)

El autor descubre que no todos los rompecabezas son iguales. Los divide en dos grupos:

• Grupo A (Ancho 1): Son rompecabezas "simples". Tienen una estructura tan ordenada (como un árbol) que puedes resolverlos paso a paso, como un algoritmo de computadora muy básico.
  • La magia: Para estos, la regla de "Compactación" funciona sin necesidad de magia. Puedes probarlo con las reglas normales de la lógica (sistema ZF). Es como si el rompecabezas te dijera: "No te preocupes, si los pedacitos encajan, el todo encajará".
• Grupo B (Complejos): Son rompecabezas con estructuras enredadas.
  • La magia: Para estos, la regla de "Compactación" NO funciona con las reglas normales. Si quieres que funcione, necesitas invocar la "magia" del Axioma de Elección.

3. El Giro Sorprendente: Medir lo Inmedible

Aquí es donde el artículo se pone realmente interesante. Tardif demuestra algo asombroso sobre el Grupo B (los rompecabezas complejos).

Dice: "Si aceptas que la regla de Compactación funciona para estos rompecabezas complejos, entonces estás obligado a aceptar que existen objetos en el espacio 3D que no se pueden medir".

• La analogía del "Paradoja Banach-Tarski": Imagina que tienes una bola de plastilina. Con la magia del Axioma de Elección, puedes cortarla en pedazos, moverlos y volver a unirlos para formar dos bolas del mismo tamaño que la original. ¡Es como duplicar la materia!
• El problema de la medida: Para que esto sea posible, esos pedazos de plastilina deben ser "no medibles". No tienen un volumen definido. Si intentas medirlos, la matemática se rompe.
• La conclusión del autor: El artículo dice que si crees que puedes resolver esos rompecabezas complejos infinitos (usando la Compactación), entonces debes creer en la existencia de esas "partículas de plastilina" que no tienen volumen definido.

Si, por el contrario, crees que todo en el universo 3D tiene un volumen medible (como creemos que lo tiene todo en la vida real), entonces no puedes usar la regla de Compactación para esos rompecabezas complejos.

4. El Mensaje Final: Un Mapa de la Realidad

El autor ha dibujado un mapa perfecto que conecta dos mundos:

1. Lógica y Computación: ¿Qué tan difícil es resolver un problema? (¿Es fácil o es un caos?)
2. Física y Realidad: ¿Qué reglas del universo aceptamos? (¿Aceptamos la magia de elegir infinitamente o creemos que todo se puede medir?)

La moraleja sencilla:

• Si tu problema es "fácil" (Ancho 1), la lógica funciona con las reglas normales. No necesitas magia, y todo es medible.
• Si tu problema es "difícil" (Complejo), para resolverlo necesitas aceptar reglas mágicas que, a su vez, te obligan a aceptar que existen cosas en el universo que no tienen tamaño ni volumen definidos.

Es como si el universo nos dijera: "No puedes tener lo mejor de los dos mundos. O tus problemas son simples y todo es medible, o tus problemas son complejos y debes aceptar que la realidad tiene partes que no puedes medir".

En resumen

Este papel nos dice que la dificultad de resolver un rompecabezas lógico está directamente ligada a qué tan "raro" debe ser nuestro universo para que ese rompecabezas tenga solución. Si el rompecabezas es muy enredado, la realidad debe ser un poco "mágica" y extraña (con objetos no medibles) para que la lógica tenga sentido.

Resumen técnico

Resumen Técnico: Problemas de Satisfacción de Restricciones, Compacidad y Conjuntos No Medibles

1. Planteamiento del Problema

El artículo explora la profunda conexión entre la complejidad algorítmica de los Problemas de Satisfacción de Restricciones (CSP, por sus siglas en inglés) y los axiomas de la teoría de conjuntos, específicamente la Axioma de Elección (AC) y sus consecuencias.

El problema central se define a través del concepto de compacidad en estructuras relacionales finitas. Una estructura finita $A$ se considera "compacta" si, para cualquier estructura infinita $B$ del mismo tipo, la existencia de un homomorfismo de $B$ a $A$ es equivalente a la existencia de homomorfismos desde todas las subestructuras finitas de $B$ hacia $A$.

La pregunta de investigación es: ¿Bajo qué condiciones axiomáticas se garantiza la compacidad de una estructura $A$?

• Se sabe que el Axioma de Elección implica la compacidad para todas las estructuras.
• Sin embargo, el autor busca determinar si la compacidad de estructuras específicas requiere axiomas fuertes (como la existencia de conjuntos no medibles) o si puede demostrarse únicamente dentro del sistema Zermelo-Fraenkel (ZF) sin elección.

2. Metodología y Marco Teórico

El autor utiliza una metodología que entrelaza tres áreas distintas:

1. Teoría de la Complejidad Computacional: Se basa en la dicotomía de Feder y Vardi (conjeturada) y demostrada por Bulatov y Zhuk, que clasifica los CSP($A$) como resolubles en tiempo polinomial (tractables) o NP-completos (intratables). Esta clasificación depende de la existencia de polimorfismos cíclicos en la estructura $A$.
2. Teoría de Conjuntos y Lógica: Se analiza la fuerza axiomática necesaria para probar la compacidad. Se contrasta ZF (sin elección) con sistemas que incluyen el Axioma de Ultrafiltro o la existencia de conjuntos no medibles.
3. Teoría de la Medida y Geometría: Se emplean construcciones basadas en la Paradoja de Banach-Tarski y el Teorema de Steinhaus en $\mathbb{R}^3$. El autor construye grafos infinitos específicos ("Grafos de Banach-Tarski") utilizando grupos de rotación libres sobre la esfera $S^2$.

Conceptos Clave:

• Ancho 1 (Width 1): Una estructura $A$ tiene ancho 1 (o dualidad arbórea) si su CSP puede resolverse mediante un algoritmo de "verificación de consistencia". Esto equivale a la existencia de un homomorfismo desde una estructura auxiliar $U(A)$ hacia $A$.
• Polimorfismos Totalmente Simétricos: La existencia de estos polimorfismos en todas las aridades es equivalente a tener ancho 1.

3. Contribuciones Clave y Resultados Principales

El artículo establece una dicotomía rigurosa entre la complejidad computacional y los fundamentos de la teoría de conjuntos:

A. El Teorema de la Dicotomía (Teorema 1.2)
El resultado principal es el siguiente teorema:

Sea $A$ una estructura relacional. Si $A$ no tiene ancho 1, entonces el axioma "$A$ es compacta" implica la existencia de un conjunto no medible en $\mathbb{R}^3$.

Esto significa que:

• Si $A$ tiene ancho 1 (problemas tractables), su compacidad es demostrable en ZF puro (sin necesidad de axiomas adicionales).
• Si $A$ no tiene ancho 1 (problemas potencialmente intratables), probar su compacidad requiere axiomas tan fuertes como la existencia de conjuntos no medibles (lo cual es más fuerte que ZF y está relacionado con el Axioma de Elección).

B. Construcción de Grafos de Banach-Tarski
Para probar el Teorema 1.2, el autor construye un grafo dirigido infinito $T$ (y una estructura $C$ asociada) basado en:

• Un grupo libre de rotaciones generado por matrices ortogonales.
• Un conjunto de puntos fijos contable ($F_G$) en la esfera $S^2$.
• La estructura de árbol de este grafo permite que todas sus subestructuras finitas admitan homomorfismos a $A$ (incluso sin elección), pero la existencia de un homomorfismo global requiere seleccionar elementos de manera coherente en un espacio infinito.

C. Uso de la Medida y la Paradoja
El autor demuestra que, si asumimos que todos los conjuntos en $\mathbb{R}^3$ son medibles (un postulado compatible con ZF + elección dependiente, como en el modelo de Solovay), se llega a una contradicción al intentar construir un homomorfismo global para estructuras sin ancho 1.

• Se define un conjunto "Fish" ($Fish_{f,D}$) basado en las diferencias entre funciones definidas por el homomorfismo.
• Utilizando una adaptación del Teorema de Steinhaus y la densidad del grupo de rotaciones, se prueba que si estos conjuntos son medibles, su medida debe ser cero.
• Esto fuerza la existencia de un punto $p$ en la esfera que no pertenece a ningún conjunto de medida cero, permitiendo definir un homomorfismo global $\omega: U(A) \to A$, lo cual contradice la premisa de que $A$ no tiene ancho 1, a menos que se acepte la existencia de conjuntos no medibles.

4. Significado e Implicaciones

1. Correspondencia Complejidad-Axiomas: El trabajo establece un puente formal donde los problemas de CSP más difíciles (NP-completos bajo la hipótesis $P \neq NP$) corresponden exactamente a los axiomas de compacidad más fuertes (que requieren conjuntos no medibles). Por el contrario, los problemas más simples (P) corresponden a resultados demostrables en ZF.
2. Apoyo a la Hipótesis $P \neq NP$: El autor sugiere que el marco de la teoría de conjuntos apoya la hipótesis $P \neq NP$. Si $P = NP$, la dicotomía se colapsaría, lo que implicaría que las estructuras "difíciles" también tendrían compacidad demostrable en ZF, contradiciendo los resultados sobre la necesidad de conjuntos no medibles.
3. Conexión con la Teoría de Conjuntos Descriptiva: El artículo discute cómo los grafos de Banach-Tarski pueden verse como estructuras de Borel. Se demuestra que, aunque un grafo puede ser 2-coloreable (si se asume compacidad), ningún coloreado con un número finito de colores puede ser un conjunto de Borel (medible), reforzando la idea de que las soluciones "construibles" (Borel) no existen para estos casos sin axiomas fuertes.
4. Problemas Abiertos: Se plantea la pregunta sobre la compacidad de grafos $n$-coloreables para $n \geq 6$, sugiriendo que la complejidad computacional podría predecir la fuerza axiomática necesaria para estos problemas de coloreado.

En conclusión, el artículo demuestra que la dificultad algorítmica de resolver un problema de satisfacción de restricciones está intrínsecamente ligada a la necesidad de axiomas de existencia de conjuntos no medibles para garantizar la compacidad de la estructura subyacente.