MathZero, The Classification Problem, and Set-Theoretic Type Theory

David McAllesterarXiv 2020 · OpenReview

Abstract: AlphaZero learns to play go, chess and shogi at a superhuman level through self play given only the rules of the game. This raises the question of whether a similar thing could be done for mathematics -- a MathZero. MathZero would require a formal foundation and an objective. We propose the foundation of set-theoretic dependent type theory and an objective defined in terms of the classification problem -- the problem of classifying concept instances up to isomorphism. The natural numbers arise as the solution to the classification problem for finite sets. Here we generalize classical Bourbaki set-theoretic isomorphism to set-theoretic dependent type theory. To our knowledge we give the first isomorphism inference rules for set-theoretic dependent type theory with propositional set-theoretic equality. The presentation is intended to be accessible to mathematicians with no prior exposure to type theory.

Introduction

The success of AlphaZero in mastering complex games like Go and Chess through reinforcement learning suggests a potential path for artificial intelligence in mathematics. However, translating the "game" of mathematics into a reinforcement learning framework requires two essential components: a formal foundation (the rules of the game) and a clear objective (the win condition).

This paper, authored by David McAllester, proposes a framework for "MathZero." It introduces a set-theoretic dependent type theory as the formal foundation and frames the objective of mathematics as the Classification Problem—the systematic enumeration of mathematical structures up to isomorphism.

A Foundation for Mathematical AI

While existing formal foundations like Martin-Löf type theory (MLTT) are powerful, they are often perceived as abstract and difficult for traditional mathematicians to adopt. Furthermore, a recurring challenge in formal mathematics is ensuring that properties are "isomorphism invariant." In many systems, proving that a property holds for all isomorphic instances of a structure requires manual, repetitive effort.

McAllester’s Set-Theoretic Dependent Type Theory bridges the gap between traditional set theory and modern type theory. By utilizing Tarskian Semantics based on a Grothendieck universe—a large set that serves as a domain for all other sets—the system provides a concrete model that is more intuitive for mathematicians. The primary goal is to create a language where any well-formed statement is guaranteed to respect isomorphism by design, effectively making the mathematics "isomorphism-safe."

The Classification Objective

In the MathZero framework, the "win condition" is defined by the Classification Problem. This involves identifying and enumerating instances of a concept (such as a Group, Ring, or Graph) up to isomorphism. For example, the natural numbers can be viewed as the solution to the classification of finite sets.

By framing mathematics as a classification game, the AI is tasked with discovering and proving theorems that organize mathematical structures. This objective provides a structured way for an agent to explore the mathematical universe, moving beyond simple theorem proving toward the discovery of fundamental structural relationships.

Inference Rules and Isomorphism Invariance

To ensure that the system handles isomorphisms correctly, the paper introduces two critical inference rules:

  1. The Congruence Rule: This rule states that isomorphic objects are inter-substitutable in any well-formed mathematical context. If two structures are isomorphic, any property proven for one must hold for the other.
  2. The Structure Rule: This is a generalization of Bourbaki’s definition of isomorphism, allowing the system to handle complex, dependent structures where the definition of one component depends on another.

To validate these rules, the author employs an "Extended Language" proof technique. By introducing an auxiliary language with a bijection constant (Bij) and proving a Conservative Extension Lemma, the paper demonstrates that reasoning within this extended language does not alter the fundamental meanings of the base language.

Key Theoretical Insights

  • Syntactic Isomorphism Invariance: The theory ensures that if a mathematical expression is well-formed according to the system's syntax, it automatically respects isomorphism. This removes the burden of manually proving invariance.
  • Cryptomorphism: The paper formalizes the concept of cryptomorphism—where different definitions describe the same underlying mathematical structure. McAllester proves that every "class" in this system is cryptomorphic to a "structure," simplifying how an AI might categorize and organize mathematical knowledge.
  • The Functor Lemma: A significant result of this work is the proof that any lambda expression (function) defined within the system behaves as a "functor." This means the function maps not only objects to objects but also isomorphisms to isomorphisms, preserving the structural integrity of the data.

Conclusion and Future Work

This paper provides the logical and semantic blueprint for MathZero, establishing Theorem 1 (Isomorphism Congruence) as a cornerstone for a new type of mathematical AI. By aligning formal type theory with the intuitive set-theoretic practices of mathematicians, it creates a more accessible and robust environment for automated discovery.

However, the work remains theoretical. Implementing the MathZero agent requires developing a reinforcement learning architecture capable of navigating an infinite and dense search space. While the "rules" and "win conditions" are now defined, the challenge of training an AI to find "interesting" mathematics—rather than trivial tautologies—remains the next frontier in the quest for a superhuman mathematical assistant.

Summary updated

Abstract

AlphaZero learns to play go, chess and shogi at a superhuman level through self play given only the rules of the game. This raises the question of whether a similar thing could be done for mathematics -- a MathZero. MathZero would require a formal foundation and an objective. We propose the foundation of set-theoretic dependent type theory and an objective defined in terms of the classification problem -- the problem of classifying concept instances up to isomorphism. The natural numbers arise as the solution to the classification problem for finite sets. Here we generalize classical Bourbaki set-theoretic isomorphism to set-theoretic dependent type theory. To our knowledge we give the first isomorphism inference rules for set-theoretic dependent type theory with propositional set-theoretic equality. The presentation is intended to be accessible to mathematicians with no prior exposure to type theory.
BibTeX
@misc{mcallester2020mathzero,
  author = {David McAllester},
  title = {{MathZero, The Classification Problem, and Set-Theoretic Type Theory}},
  year = {2020},
  eprint = {2005.05512},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.05512},
}

Loading related content...

Figure