Formal Game Theory Proofs in Lean 4

ISEF Category: Mathematics

Subcategory: Other  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

A proof that looks right on paper can still hide a gap. Computers do not forgive that gap. In Lean 4, you have to spell out every step until the theorem either works or breaks. That makes formal game theory a great test of precision.

What Is It?

This project asks you to take a theorem from combinatorial game theory and write a machine-checked proof in Lean 4, the proof assistant used by many mathematicians and computer scientists. A proof assistant is a program that checks each logical step, almost like a spell-checker for mathematics. If your theorem involves a game, such as a Sprague-Grundy style result, you also get to model the rules of the game in a way the computer can understand.

Think of it like turning a handwritten recipe into code that a robot can follow exactly. In a normal proof, a skipped step can stay hidden. In Lean, the skipped step shows up fast. That makes this kind of project part math, part logic, and part software engineering.

Why This Is a Good Topic

This is a strong science fair topic because you can test a real mathematical claim, compare proof strategies, and measure how formalization changes the way you think about correctness. The project connects to logic, algorithmic proof checking, and combinatorial game theory, which all matter in modern math and computer science. You can realistically learn a lot without inventing new theory, because the challenge comes from formalizing a known result carefully and clearly.

Research Questions

• How does the time needed to formalize a combinatorial game theory proof change with the size of the theorem?
• What is the effect of different Lean proof styles on the length and readability of the final formal proof?
• Does breaking a theorem into small lemmas reduce the number of proof errors in Lean?
• To what extent does a computer-checked proof catch hidden assumptions in an informal combinatorial game theory argument?
• Which definitions of game state or move rules make the Lean formalization easiest to maintain?
• How does adding reusable helper lemmas affect the total number of lines needed for a Sprague-Grundy style proof?

Basic Materials

• Laptop or desktop computer with enough storage for Lean 4 and mathlib.
• Internet access for documentation and source papers.
• Text editor or IDE with Lean support, such as VS Code.
• Notebook for planning definitions, lemmas, and proof structure.
• Reference papers or notes on the chosen combinatorial game theory result.
• Version control system, such as Git, to track changes.

Advanced Materials

• Laptop or desktop computer with a recent CPU and at least 16 GB of RAM.
• Lean 4 installation with the current mathlib repository.
• Git and GitHub or another code host for version tracking.
• A curated set of source papers on combinatorial game theory and formal proof methods.
• A code editor with Lean language support and error navigation.
• Optional second computer or cloud workspace for comparing proof runs and build times.

Software & Tools

• Lean 4: Checks each proof step and lets you formalize the theorem in a precise way.
• mathlib: Gives you a large library of existing Lean theorems and definitions to build on.
• VS Code: Helps you edit Lean files and see errors as you work.
• Git: Tracks proof changes, versions, and failed attempts during development.
• GitHub: Stores your code and makes it easy to share a public proof repository.

Experiment Steps

1. Choose one theorem from combinatorial game theory that has a clear informal proof and a narrow scope for formalization.
2. Translate the game rules, game states, and winning conditions into Lean definitions that the computer can inspect.
3. Break the theorem into small lemmas so each part of the argument has a local proof target.
4. Compare at least two proof approaches, such as a direct proof and an induction-based proof, and record which one formalizes more cleanly.
5. Build the final Lean proof, then test it against edge cases and known examples to make sure the model matches the math.
6. Document the places where the informal proof needed extra assumptions, missing cases, or sharper definitions.

Common Pitfalls

• Trying to formalize a theorem before defining the game state precisely, which leaves the proof stuck later.
• Copying an informal proof step that depends on an unstated assumption, which Lean rejects immediately.
• Making the theorem too broad for a first project, which turns a manageable proof into a huge library search problem.
• Using a definition of legal moves that does not match the source paper, which changes the theorem you are proving.
• Skipping small helper lemmas, which forces the main proof to repeat the same logic and become hard to debug.

What Makes This Competitive

A strong version of this project does more than copy a proof into code. You can compare proof styles, explain why one formalization is cleaner, and show where the informal argument hid assumptions. You can also build reusable lemmas that help formalize a broader family of games, not just one example. That kind of structure and careful analysis makes the project much stronger than a simple transcription.

Project Variations

• Formalize a small impartial game and prove its winning positions in Lean 4.
• Compare a normal-play theorem with a misère-play variant and note where the logic changes.
• Formalize two different proofs of the same game theorem, then compare proof length, lemma count, and readability.

Learn More

• Lean community documentation: Search for the official Lean 4 docs and the mathlib documentation for proof syntax, tactics, and examples.
• MIT OpenCourseWare, Logic and Proofs: Find lecture notes and problem sets that build proof-writing habits and logic basics.
• Theorem Proving in Lean 4: Search for the official free Lean textbook, which explains the language and proof workflow.
• arXiv: Search for papers on formal verification, proof assistants, and combinatorial game theory formalization.
• Mathlib GitHub repository: Read existing Lean code and browse proofs, definitions, and issue discussions for examples.