Un nuevo puente conecta la extraña matemática del infinito con la informática

• Se reveló que la teoría descriptiva de conjuntos, un campo técnico que estudia la estructura de los conjuntos infinitos, puede reinterpretarse en el lenguaje de los algoritmos
• El matemático Anton Bernshteyn demostró que los problemas de grafos infinitos pueden reescribirse como problemas de comunicación en redes de computadoras
• Esta conexión muestra una correspondencia entre la medibilidad (measurability) y la eficiencia de los algoritmos distribuidos
• Los investigadores ya están usando este puente para transformar teoremas y problemas de ambos campos en ambas direcciones y obtener nuevos resultados
• Es un hallazgo que redefine la frontera entre infinito y computación y amplía las posibilidades de colaboración entre la matemática y la informática

---

Introducción: teoría de conjuntos y el mundo del infinito

• Los fundamentos de la matemática moderna se basan en la teoría de conjuntos, y la mayoría de los matemáticos abordan sus problemas dándola por sentada
• Sin embargo, los teóricos descriptivos de conjuntos (descriptive set theorists) son un pequeño grupo de investigadores que sigue explorando la naturaleza de los conjuntos infinitos
• En 2023, Anton Bernshteyn descubrió una conexión profunda entre la teoría descriptiva de conjuntos y la informática
  • Mostró que ciertos problemas de conjuntos infinitos pueden transformarse en problemas de comunicación en redes de computadoras
• Este resultado se considera un puente entre lenguajes opuestos: lógica y algoritmos, infinito y finito

Antecedentes de la teoría descriptiva de conjuntos

• El origen de la teoría de conjuntos se remonta a los estudios de Georg Cantor, de donde surgió la demostración de que existen distintos tamaños del infinito
• Entre los conceptos que expresan el tamaño de un conjunto están la cardinalidad (cardinality) y la medida (measure)
  • Ejemplo: el conjunto de números reales entre 0 y 1 y el conjunto de números reales entre 0 y 10 tienen la misma cardinalidad, pero sus medidas son 1 y 10, respectivamente
• La teoría descriptiva de conjuntos distingue entre conjuntos medibles y no medibles, y los clasifica en una jerarquía de complejidad (hierarchy)
• Esa jerarquía sirve en otras áreas de la matemática (por ejemplo, probabilidad, sistemas dinámicos y teoría de grupos) como criterio para elegir las herramientas adecuadas

Grafos infinitos y problemas de coloreado

• Bernshteyn estudió grafos infinitos, modelando los nodos y aristas de cada grafo como una estructura conectada de manera infinita
• Ejemplo: si se conectan puntos sobre un círculo a intervalos regulares, un intervalo racional forma un ciclo cerrado, mientras que un intervalo irracional genera una estructura de conexión infinita
• Al colorear los nodos de un grafo con dos colores, es posible hacerlo usando el axioma de elección (axiom of choice), pero el resultado es un conjunto no medible
• En cambio, si se usa un método de coloreado continuo, se necesitan tres colores, pero se obtiene un conjunto medible
• Esta diferencia actúa como un elemento clave para determinar la posición dentro de la jerarquía de complejidad de la teoría de conjuntos

El encuentro con los algoritmos distribuidos

• En 2019, Bernshteyn asistió a una charla de informática sobre algoritmos distribuidos (distributed algorithms) y detectó la similitud
  • Ejemplo: el problema de hacer que routers Wi‑Fi elijan frecuencias (colores) distintas para no interferirse entre sí
• Cada nodo decide su color usando un algoritmo local (local algorithm) que solo se comunica con nodos vecinos
• Con dos colores es ineficiente, pero si se permiten tres, el problema puede resolverse eficientemente
• Bernshteyn reconoció que este umbral (threshold) del número de colores coincide con el umbral del problema de coloreado medible en teoría descriptiva de conjuntos

Demostración de la equivalencia entre dos mundos

• Bernshteyn demostró matemáticamente la equivalencia entre algoritmos locales eficientes ↔ métodos de coloreado medible
• En grafos finitos se puede asignar un número único a cada nodo, pero en grafos infinitos no numerables eso no es posible
• Ideó un método de etiquetado sin superposición entre nodos adyacentes, lo que permite extender los algoritmos también a grafos infinitos
• Como resultado, quedó demostrado que todo algoritmo local corresponde a un método de coloreado medible de la teoría descriptiva de conjuntos
• Esto muestra una conexión matemática profunda entre la computabilidad y la definibilidad (definability)

Expansión de la investigación y aplicaciones

• Václav Rozhoň y otros usaron esta conexión para resolver problemas de coloreado en grafos tipo árbol (tree) y extraer herramientas para estudiar sistemas dinámicos
• En sentido inverso, también avanzan investigaciones que usan métodos de teoría de conjuntos para mejorar la estimación de la dificultad de problemas
• Este puente no es solo una herramienta para resolver problemas, sino que también contribuye a reformular el sistema de clasificación de la teoría de conjuntos
• Los teóricos descriptivos de conjuntos ahora pueden apoyarse en el método de clasificación sistemática de la informática para ordenar problemas aún no clasificados
• Bernshteyn espera que esta investigación ayude a que el concepto de infinito se reconozca como parte de la matemática práctica

[GN⁺]

Opinión de Hacker News

• Me pregunto si este tipo de resultado podría aplicarse a campos reales como la computación distribuida, o si solo existe como una curiosidad de la matemática pura

  • Para nada es una pregunta tonta. Una intuición técnica así podría llevar a nuevos teoremas de imposibilidad en algoritmos distribuidos o en teoría de la complejidad computacional. También suenan interesantes posibles aplicaciones como el mesh networking

• La frase “toda la matemática moderna se construyó sobre la teoría de conjuntos” es demasiado categórica. Herramientas modernas para matemáticas como Lean o Rocq están avanzando sobre la base de la matemática formalizada (formalized mathematics), y eso está construido sobre la teoría de tipos (type theory)

  • No soy matemático, pero creo que ZFC sigue siendo un sistema fundacional válido. Los tipos dependientes (dependent types) son útiles para gestionar demostraciones de teoremas, pero no hacen que puedas demostrar más teoremas. Isabelle/HOL de Lawrence Paulson no está basado en tipos y aun así puede demostrar la mayor parte de la matemática
  • Pero en la práctica, los matemáticos casi no usan matemática formalizada. Incluso si la conocen, no la usan como lenguaje fundacional por lo incómoda que resulta
  • No hay que confundir el lenguaje de la matemática con el lenguaje formal con el que se demuestra algo sobre ese lenguaje. El primero usa casi por completo conjuntos; el segundo, necesariamente, tipos
  • Dicho con más precisión, lo correcto sería decir que la crisis de fundamentos de la matemática se cerró provisionalmente con la formalización de la teoría de conjuntos

• “cons’es all the way down” es una broma que parodia una estructura recursiva

• Me emociona la idea de que “por fin podemos calcular el infinito”

  • El próximo mes habrá en el Bay Area la gira Calculating Infinity de The Dillinger Escape Plan. Link del evento. Lo comparto porque siento que hay superposición entre fans de las matemáticas, el hacking y el mathcore
  • Siguen el chiste respondiendo a “calcular el infinito” con “¡y más allá!”
  • En Haskell, dicen que puedes expresar una infinidad contable (countable infinity) con una sola línea: let x = x in x
  • Le agregan humor con el meme de que “Chuck Norris contó del 1 al infinito dos veces”
  • Y rematan con “esto de verdad tomó muchísimo tiempo /s”, en tono sarcástico

• No estoy de acuerdo con la afirmación de que “la informática solo trata con cosas finitas”. En realidad, la informática está profundamente involucrada con el infinito

  • Es muy típico de Quanta tratar los temas así. Tienden a enfocarse en historias centradas en personas, al estilo de la divulgación científica, y omiten los detalles
  • Dicho eso, a la informática le interesa menos el infinito no numerable (uncountable infinity). La teoría de la medida (measure theory) se ocupa más de eso
  • Yo también al principio pensaba que “CS aproxima el infinito”, pero en realidad la palabra clave es aproximación (approximation). Siempre trabajamos dentro de límites finitos. Aunque el universo fuera infinito, el rango que podemos observar sigue limitado por la velocidad de la luz
  • Frases como “la informática no usa lógica” son una forma demasiado floja de decir las cosas. La lógica booleana es prueba suficiente

• Estudié matemáticas durante mucho tiempo y terminé creyendo que el infinito (infinity) no existe. Pienso que las matemáticas quizá serían mejores sin él

  • Yo también solo estudié matemáticas a nivel ingeniería, pero veo el infinito no como un número, sino como un proceso (process). Los “...” de {1, 2, 3, ...} significan un proceso de expansión sin fin. No existe algo como “el enésimo primo infinito”; solo hay una regla generativa según la cual siempre existe un primo más grande
  • Pero si eliminas el infinito, las matemáticas se vuelven terriblemente complejas. Si no permites extender los números naturales sin límite, calcular se vuelve muy incómodo
  • A las matemáticas les importa más la utilidad conceptual que la existencia. Los círculos tampoco existen en la realidad y aun así son útiles. Si no hubiera infinito, al final habría que reinventarlo como algo tipo “el límite cuando x tiende a un número muy, muy grande”
  • Hacen el chiste de que basta con “parar en 8”, para burlarse de lo innecesario del infinito
  • El infinito no es más que un nombre para un proceso que no termina. Algunos procesos crecen más rápido, por eso existen infinitos más grandes. En lo personal, me gusta el concepto de infinito del modelo de la esfera de Riemann

• Bromean con que node_modules conectó las matemáticas del infinito a mi sistema de archivos, parodiando la explosión de dependencias

• Rebatiendo la frase “toda la matemática moderna se construyó sobre la teoría de conjuntos”, señalan que también existe la teoría de tipos (Type Theory)

  • La Type Theory es un sistema axiomático más poderoso que ZFC. Para una explicación relacionada, ver esta respuesta en MathOverflow
  • Pero todavía no existe un conjunto de axiomas de teoría de tipos tan influyente como ZF o ZFC
  • Técnicamente, la teoría descriptiva de conjuntos (descriptive set theory) es distinta de la teoría de conjuntos fundacional. Puede reconstruirse fácilmente con conceptos de tipos y espacios, y eso muchas veces resulta más ventajoso. Reinterpretar el infinito matemático desde una perspectiva computacional no es algo nuevo
  • La descripción de la teoría de conjuntos como “la disciplina que organiza conjuntos de objetos abstractos” simplifica demasiado lo que es. Aun así, sigue siendo cierto que la mayor parte de la matemática todavía se define a partir de los axiomas de conjuntos