Pesquisador do Instituto Modal participa de pesquisa internacional sobre fundamentos da teoria dos conjuntos

[latexpage]

A Teoria dos Conjuntos é uma linguagem e uma ferramenta importante para o raciocínio. É uma base para a Matemática — praticamente toda a Matemática pode ser formalizada na Teoria dos Conjuntos. Tudo a que você se refere em Matemática e, como conseqüência em todas as outras ciências, é formalizado na Teoria dos Conjuntos.

Em particular, a Teoria dos Conjuntos é uma ferramenta útil para formalizar o raciocínio sobre a computação e sobre os objetos da computação. A Teoria dos Conjuntos é inseparável da Lógica, onde a Ciência da Computação tem suas raízes. A Ciência da Computação tem muitas de suas ideias inspiradas em conjuntos: estruturas de dados e bancos de dados relacionais são relações sobre conjuntos. Na teoria formal da linguagem, uma linguagem é um conjunto de strings complementado pelo estudo de certas operações, e tais operações são baseadas em conjuntos. Algoritmos, igualmente, seriam impossíveis sem conjuntos: de fato, algoritmos são conjuntos ou sequências (conjuntos ordenados) de funções recursivas, que por sua vez são relações computáveis entre conjuntos. Basta contar quantas vezes a palava “conjunto” aparece nesse parágrafo para se convencer que sem conjuntos não há algoritmos.

A famosa Teoria dos Conjuntos de Zermelo-Fraenkel ($\mathbb{ZF}$), batizada em homenagem aos matemáticos Ernst Zermelo e Abraham Fraenkel, é um sistema axiomático proposto no início do século XX para tornar a Teoria dos Conjuntos livre de paradoxos como o paradoxo de Russell. Existem muitas formulações equivalentes dos axiomas da teoria dos conjuntos de Zermelo-Fraenkel.

O problema…

Mas há um problema: ninguém sabe se $\mathbb{ZF}$ (e suas extensões como $\mathbb{ZFC}$, obtida adicionando o Axioma da Escolha) é consistente ou não. O célebre segundo teorema da incompletude de Gödel implica, entre outras coisas, que a consistência de $\mathbb{ZF}$ não pode ser provada dentro de $\mathbb{ZF}$ propriamente dito (a menos que a teoria seja realmente inconsistente). Assim, na medida em que $\mathbb{ZF}$ é identificada com a Matemática comum, a consistência de $\mathbb{ZF}$ não pode ser demonstrada na Matemática.

Este é um limite importante do poder da Matemática, um limite que também reflete na Ciência da Computação e na Inteligência Artificial, aprendizagem de máquina e desenvolvimento de software.

Caminhos para solução

Tudo isso justifica o interesse de Alfredo Freire, nosso colega do Instituto Modal, que recentemente obteve seu doutorado em Filosofia e Lógica pela Universidade de Campinas, e que está colaborando com o Prof. Joel David Hamkins (Universidade de Oxford) em uma importante pesquisa em Teoria dos Conjuntos . Alfredo Freire e Joel Hamkins acabaram de ter o aceite para publicação de um artigo no prestigiado Journal of Symbolic Logic: J. D. Hamkins e A. R. Freire, “Bi-interpretation in weak set theories”.

Uma versão preliminar do artigo (bastante profundo e técnico) está disponível em Mathematics arXiv, 2020 e no Research Gate.

Joel Hamkins comenta a importância do trabalho em seu blog.

Além disso, recentemente, o Prof. Joel Hamkins fez uma palestra de 90 minutos intitulada Bi-interpretation in weak set theories, no Seminário de Matemática em Oxford, explicando os principais resultados do trabalho conjunto, com base na tese de doutorado de Alfredo Freire, orientada pelos professores Walter Carnielli (Unicamp / Instituto Modal) e Rodrigo Freire (UnB).

A enorme importância da Teoria dos Conjuntos para a Matemática e a Ciência da Computação, juntamente com a ausência de uma prova de consistência, justifica o interesse da investigação em modelos e interpretações da Teoria dos Conjuntos. Os principais resultados do trabalho de Alfredo Freire e Joel Hamkins são explicados abaixo.

$\mathbb{Z}$ (uma versão mais fraca da teoria dos conjuntos sem o axioma de substituição) não é sólido e não é rígido. Em linguagem especializada, isso significa que $\mathbb{Z}$ possui modelos não isomórficos (ou seja, modelos com “personalidades distintas”) que são muito “similares”, ou seja, os modelos são bi-interpretáveis. Eles mostram que o fenômeno da biinterpretabilidade ocorre apenas em teorias de conjuntos fracas, como $\mathbb{ZFC^{-}}$ (sem o axioma do conjuntos-potência) e $\mathbb{Z}$. Mas eles também provaram que $\mathbb{ZF}$ possui apenas um modelo a menos de bi-interpretação, ou seja, $\mathbb{ZF}$ é sólido. Isso dá uma caracterização importante para $\mathbb{ZF}$.

O impacto

Existem várias consequências fundacionais e filosóficas importantes desses resultados, que ainda estão sendo investigadas; uma delas é que os resultados indicam que $\mathbb{ZF}$ é uma teoria mínima onde existe um tipo de acordo universal: mesmo que não possamos provar a consistência de $\mathbb{ZF}$, a teoria é suficientemente segura para evitar discordâncias. De fato, existem várias extensões ou modificações dos axiomas da teoria dos conjuntos, como o Axioma de Martin, o Axioma da Determinação, enfraquecimento do Axioma da Escolha para o Axioma das Escolhas Dependentes etc., mas essas propostas não tocam $\mathbb {ZF}$.

Embora existam muitos modelos de $\mathbb{ZF}$, cada um deles é determinado exclusivamente por bi-interpretações. Isso dá um pouco mais de garantia a $\mathbb{ZF}$, apesar da impossibilidade de provar sua consistência, e a fortiori um pouco mais de garantia à ciência em geral, e à Ciência da Computação em particular. Atividades como, por exemplo, a verificação de modelos (model checking) que se refere ao problema de testar se um modelo atende a uma dada especificação, e atende a requisitos de segurança como a ausência de pontos de travamento (deadlocks) perderiam completamente o sentido se uma inconsistência fosse descoberta na teoria de conjuntos. Dentro da impossibilidade de uma prova de consistência, uma garantia relativa adicional de consistência vale ouro.

A pesquisa sobre os fundamentos da Matemática é algo de excepcional importância, não apenas para Ciências e Computação, mas também para todo o futuro da humanidade. O trabalho de Alfredo Freire e Joel Hamkins contribui com uma peça, e com bela jogada, neste jogo profundo. Nossos parabéns!