## Diagram: Proof Search and Tactic Generation ### Overview The image illustrates a proof search process coupled with a tactic generation system. It shows how a proof is explored through different cases and how a language model is used to suggest tactics based on the local context and a formal math library. ### Components/Axes * **Title:** Proof search (top-left), Tactic generation (bottom-right) * **Proof Search Tree:** * Root Node: `n : N`, `⊢ add 0 n = n` * Branches: `induction n`, `cases n`, `exfalso` * Intermediate Nodes: `⊢ add 0 0 = 0`, `n' : N`, `ih: add 0 n' = n'`, `⊢ add 0 (n'+1) = n'+1`, `n : N`, `⊢ false` * **Tactic Generation System:** * Input: `n' : N`, `ih: add 0 n' = n'`, `⊢ add 0 (n'+1) = n'+1`, `Local context + goal`, `Formal math library` * Process: `Language model` (represented as a neural network) * Output: `Tactic suggestions` (containing `simp [add, ih]`, `rw [ih]`, `linarith`) ### Detailed Analysis **Proof Search Tree:** * The proof starts with the goal `add 0 n = n` where `n` is a natural number (`N`). * The proof branches based on three tactics: `induction n`, `cases n`, and `exfalso`. * The `induction n` and `cases n` branches lead to nodes with the following structure: * `⊢ add 0 0 = 0` * `n' : N` * `ih: add 0 n' = n'` (induction hypothesis) * `⊢ add 0 (n'+1) = n'+1` * The `exfalso` branch leads to a node with `n : N` and `⊢ false`. * The first branch after the first `induction n` leads to a node with an orange border. From this node, three tactics are suggested: `rft`, `...`, `...` * The top-most branch after the first `induction n` leads to a node with an orange border. From this node, three tactics are suggested: `simp [add, ih]`, `rw [ih]`, `linarith`. The `simp [add, ih]` tactic has a green checkmark next to it. **Tactic Generation System:** * The system takes the local context and goal as input, along with a formal math library. * A language model (represented as a neural network) processes this information. * The output is a set of tactic suggestions: `simp [add, ih]`, `rw [ih]`, and `linarith`. These tactics are displayed in blue text within a dashed-line box. ### Key Observations * The diagram illustrates a connection between proof search and tactic generation. * The language model is used to suggest tactics based on the current state of the proof. * The green checkmark next to `simp [add, ih]` suggests that this tactic was successfully applied. ### Interpretation The diagram demonstrates an automated approach to mathematical proof. The proof search explores different paths, while the tactic generation system provides suggestions to guide the search. The use of a language model allows the system to learn from a formal math library and suggest relevant tactics based on the local context and goal. This approach has the potential to automate and accelerate the process of mathematical proof. The orange boxes highlight specific states in the proof search where tactic suggestions are being generated. The green checkmark indicates a successful tactic application, suggesting a feedback loop where the system learns from its successes.