Uma nova ponte liga a estranha matemática do infinito à ciência da computação

• Foi revelado que a teoria descritiva dos conjuntos, um campo técnico que estuda a estrutura dos conjuntos infinitos, pode ser reinterpretada na linguagem dos algoritmos
• O matemático Anton Bernshteyn provou que problemas de grafos infinitos podem ser reescritos como problemas de comunicação em redes de computadores
• Essa conexão mostra uma correspondência entre mensurabilidade (measurability) e eficiência de algoritmos distribuídos
• Pesquisadores estão usando essa ponte para converter teoremas e problemas entre as duas áreas e obter novos resultados
• A descoberta redefine a fronteira entre infinito e computação e amplia as possibilidades de colaboração entre matemática e ciência da computação

---

Introdução: teoria dos conjuntos e o mundo do infinito

• Os fundamentos da matemática moderna se baseiam na teoria dos conjuntos, e a maioria dos matemáticos trata problemas partindo desse pressuposto
• No entanto, os teóricos descritivos dos conjuntos (descriptive set theorists) são um pequeno grupo de pesquisadores que continua explorando a natureza dos conjuntos infinitos
• Em 2023, Anton Bernshteyn descobriu uma conexão profunda entre teoria descritiva dos conjuntos e ciência da computação
  • Mostrou que certos problemas de conjuntos infinitos podem ser convertidos em problemas de comunicação em redes de computadores
• O resultado é visto como uma ponte entre linguagens opostas: lógica e algoritmos, infinito e finito

Contexto da teoria descritiva dos conjuntos

• A origem da teoria dos conjuntos remonta aos estudos de Georg Cantor, que começaram ao provar a existência de diferentes tamanhos de infinito
• Entre os conceitos que expressam o tamanho de um conjunto estão a cardinalidade (cardinality) e a medida (measure)
  • Exemplo: o conjunto dos números reais no intervalo de 0 a 1 e o conjunto dos números reais no intervalo de 0 a 10 têm a mesma cardinalidade, mas medidas 1 e 10, respectivamente
• A teoria descritiva dos conjuntos distingue entre conjuntos mensuráveis e não mensuráveis e os classifica em uma hierarquia de complexidade (hierarchy)
• Essa hierarquia serve como critério para escolher ferramentas adequadas em outras áreas da matemática, como probabilidade, sistemas dinâmicos e teoria dos grupos

Grafos infinitos e problemas de coloração

• Bernshteyn estudou grafos infinitos, modelando os nós e arestas de cada grafo como uma estrutura infinitamente conectada
• Exemplo: se pontos sobre um círculo forem conectados em intervalos regulares, um intervalo racional forma um ciclo fechado, enquanto um intervalo irracional forma uma estrutura de conexões infinitas
• Ao colorir os nós de um grafo com duas cores, isso é possível usando o axioma da escolha (axiom of choice), mas o resultado é um conjunto não mensurável
• Já com uma coloração contínua, são necessárias três cores, mas obtém-se um conjunto mensurável
• Essa diferença funciona como um fator central para determinar a posição na hierarquia de complexidade da teoria dos conjuntos

O encontro com algoritmos distribuídos

• Em 2019, Bernshteyn assistiu a uma palestra de ciência da computação sobre algoritmos distribuídos (distributed algorithms) e percebeu a semelhança
  • Exemplo: o problema de fazer com que roteadores Wi‑Fi escolham frequências (cores) diferentes para não interferirem entre si
• Cada nó decide sua cor usando um algoritmo local (local algorithm) que se comunica apenas com os nós vizinhos
• Com duas cores, a solução é ineficiente, mas ao permitir três cores o problema pode ser resolvido com eficiência
• Bernshteyn percebeu que esse limiar (threshold) do número de cores era igual ao limiar do problema de coloração mensurável na teoria descritiva dos conjuntos

Prova da equivalência entre dois mundos

• Bernshteyn provou matematicamente a equivalência entre algoritmos locais eficientes ↔ esquemas de coloração mensuráveis
• Em grafos finitos, é possível atribuir um número único a cada nó, mas isso não é possível em grafos infinitos não enumeráveis
• Ele concebeu um método de rotulagem sem sobreposição entre nós adjacentes, permitindo estender algoritmos também a grafos infinitos
• Como resultado, foi provado que “todo algoritmo local corresponde a um esquema de coloração mensurável da teoria descritiva dos conjuntos”
• Isso mostra uma conexão matemática profunda entre computabilidade e definibilidade (definability)

Expansão da pesquisa e aplicações

• Václav Rozhoň e outros usaram essa conexão para resolver problemas de coloração em grafos do tipo árvore (tree) e derivar ferramentas para o estudo de sistemas dinâmicos
• Em sentido inverso, também avançaram pesquisas que usam métodos da teoria dos conjuntos para melhorar a estimativa da dificuldade de problemas
• Essa ponte vai além de uma simples ferramenta para resolver problemas e contribui para a reorganização do sistema de classificação da teoria dos conjuntos
• Os teóricos descritivos dos conjuntos agora podem usar como referência o modo sistemático de classificação da ciência da computação para organizar problemas ainda não classificados
• Bernshteyn espera que essa pesquisa ajude a fazer com que o conceito de infinito seja reconhecido como parte da matemática prática

[GN⁺]

Comentários do Hacker News

• Fico curioso se esse resultado pode ser aplicado em áreas reais como computação distribuída. Ou se existe apenas como interesse puramente matemático

  • Não é uma pergunta nada boba. O insight técnico pode levar a novos teoremas de impossibilidade em algoritmos distribuídos ou teoria da complexidade computacional. Aplicações como redes mesh também parecem interessantes

• Dizer que “toda a matemática moderna foi construída sobre a teoria dos conjuntos” é categórico demais. Ferramentas modernas de matemática como Lean e Rocq estão avançando com base em matemática formalizada (formalized mathematics), que é construída sobre teoria dos tipos (type theory)

  • Não sou matemático, mas acho que ZFC ainda é um sistema fundacional válido. Tipos dependentes (dependent types) são úteis para gerenciar provas de teoremas, mas não permitem provar mais teoremas. O Isabelle/HOL de Lawrence Paulson não é baseado em tipos dependentes, mas consegue provar a maior parte da matemática
  • Mas os matemáticos de fato quase não usam matemática formalizada. Mesmo quando conhecem, não a usam como linguagem fundamental por ser incômoda
  • Não se deve confundir a linguagem da matemática com a linguagem formal usada para provar coisas sobre essa linguagem. A primeira usa quase inteiramente conjuntos; a segunda inevitavelmente usa tipos
  • Mais precisamente, o correto seria dizer que a crise dos fundamentos da matemática foi encerrada com a formalização da teoria dos conjuntos

• Uma piada com a expressão “cons’es all the way down”, satirizando uma estrutura recursiva

• Fiquei emocionado com a frase “finalmente podemos calcular o infinito”

  • No mês que vem vai ter a turnê Calculating Infinity do The Dillinger Escape Plan na Bay Area. Link do show. Estou compartilhando porque parece haver uma sobreposição entre fãs de matemática, hacking e mathcore
  • Em resposta à frase “calcular o infinito”, alguém brinca: “E além!”
  • Em Haskell, dá para representar infinito contável (countable infinity) com uma única linha: let x = x in x
  • Complementam o humor com o meme “Chuck Norris contou de 1 até o infinito duas vezes”
  • E acrescentam a ironia: “Isso realmente demorou bastante /s”

• Não concordo com a afirmação de que “a ciência da computação lida apenas com o finito”. Na prática, ciência da computação está profundamente envolvida com o infinito

  • Esse tipo de abordagem da Quanta é comum. Eles tendem a focar em narrativas de divulgação científica centradas em pessoas e a omitir os detalhes
  • Ainda assim, a ciência da computação tem menos interesse em infinito incontável (uncountable infinity). Teoria da medida (measure theory) lida mais com isso
  • Eu também achava no começo que “CS aproxima o infinito”, mas na prática a palavra-chave é aproximação (approximation). Sempre trabalhamos dentro de limites finitos. Mesmo que o universo seja infinito, o alcance que podemos observar é limitado pela velocidade da luz
  • Frases como “ciência da computação não usa lógica” são preguiçosas demais. A própria lógica Booleana já prova o contrário

• Estudei matemática por muito tempo e passei a acreditar que infinito (infinity) não existe. Acho até que a matemática poderia ser melhor sem ele

  • Também só aprendi matemática em nível de engenharia, mas penso no infinito não como número, e sim como processo (process). O “...” em {1, 2, 3, ...} significa um processo de expansão sem fim. Não existe algo como o ésimo primo infinito; existe apenas uma regra de geração segundo a qual sempre há um primo maior
  • Mas remover o infinito tornaria a matemática terrivelmente complicada. Se não pudermos estender os números naturais indefinidamente, os cálculos ficam muito inconvenientes
  • A matemática se interessa mais pela utilidade conceitual do que pela existência real. Círculos também não existem no mundo real, mas são úteis. Se não houvesse infinito, no fim teríamos de reinventá-lo como algo do tipo “o limite quando x vai para um número muito, muito grande”
  • Fazem a piada de que “dá para parar no 8”, satirizando a desnecessidade do infinito
  • Infinito é apenas o nome dado a um processo que não termina. Como alguns processos crescem mais rápido, existem infinitos maiores. Pessoalmente, gosto da noção de infinito no modelo da esfera de Riemann

• Uma piada dizendo que node_modules conectou a matemática do infinito ao meu sistema de arquivos, satirizando a explosão de dependências

• Contestam a frase “toda a matemática moderna foi construída sobre a teoria dos conjuntos”, apontando que também existe Teoria dos Tipos (Type Theory)

  • Type Theory é um sistema axiomático mais forte que ZFC. Veja esta explicação na resposta do MathOverflow
  • Mas ainda não existe um conjunto de axiomas de teoria dos tipos com influência comparável à de ZF ou ZFC
  • Tecnicamente, a teoria descritiva dos conjuntos (descriptive set theory) é separada da teoria dos conjuntos fundacional. Ela pode ser reconstruída com facilidade usando conceitos de tipos e espaços, o que muitas vezes é mais vantajoso. Reinterpretar o infinito matemático de um ponto de vista computacional não é uma tentativa nova
  • A descrição “a disciplina que organiza conjuntos de objetos abstratos” simplifica demais a teoria dos conjuntos. Ainda assim, é verdade que a maior parte da matemática continua sendo definida a partir dos axiomas dos conjuntos