用几何方法量化选择公理对证明的影响,发现其与自动定理证明性能直接相关。
Geometric Measurements of the Axiom of Choice in Neural Proof Embeddings

- 通过追踪数学库中47万条声明的依赖关系,构建基于操作序列的证明嵌入空间。
- 距离选择公理越远的证明,其几何异常度、重建误差等指标越低,9步外几乎无法区分。
- 该几何信号可预测定理证明器失败,尤其适用于改进神经引导的混合证明策略。
选择公理自百年来一直分裂数学基础,但经典与构造性证明的区别仍停留在哲学层面。本文利用 Lean 4 内核对公理依赖的精细追踪,揭示选择公理在证明空间中具有可量化的几何特征,遵循单参数混合规律,并对神经定理证明器有实际影响。我们对 Mathlib 中 471,260 个声明按对选择公理的传递依赖进行划分,将其中 42,355 个可追溯定理表示为战术调用序列。使用这些构造性证明训练自监督证明编码器后发现:当用于测量经典证明时,异常分数、重构损失和密度超水平包含三个指标随与选择公理在依赖图中的距离衰减,浅层边界处(距离2)分类效果显著(AUC 0.847),距离9以上则完全无法区分。鲁棒性检验显示该特征在长度、文件、作者、主题控制下仍稳定存在,且在归一化源码训练的完整编码器中可复现。实证表明,在251个 Mathlib 定理上,Lean 的 aesop 战术对构造性证明的解决率是经典证明的13倍;采用 ReProver 战术生成器的神经引导混合策略将其差距缩小至5倍。几何异常得分能预测 aesop 在长证明上的失败,建立几何特征与求解器性能之间的操作关联。
原文摘要 · Abstract (English)
The axiom of choice has divided the foundations of mathematics for over a century, but the distinction between classical and constructive proofs has remained a philosophical and methodological one. We use Lean 4's kernel-level tracking of axiom dependence to show that the axiom of choice has a measurable geometric correlate in proof space that obeys a one-parameter mixture law and has operational consequences for neural theorem provers. To do this, we partition $471{,}260$ declarations of Mathlib by transitive dependence on the axiom of choice and represent a filtered population of $42{,}355$ traced theorems by their sequences of tactic invocations. We use the constructive proofs in this dataset to train a self-supervised proof encoder and show that when using it to measure classical proofs, three complementary measurements (anomaly score, reconstruction loss, and density-superlevel containment) exhibit a common decline with the proof's distance from the axiom in the dependency graph, from sharp separation at the shallow boundary (AUC $0.847$ at distance $2$) to indistinguishability at distance~$9{+}$. Robustness controls show that the signature survives length, file, author, and topic controls, and replicates under full-source encoders trained on normalised proof source. Operationally, we show that on an evaluation sample of $251$ Mathlib theorems, Lean's \texttt{aesop} tactic solves constructive theorems at $13\times$ the rate of classical ones, and a neural-guided hybrid using the ReProver tactic generator compresses the gap to $5\times$. The geometric anomaly score predicts \texttt{aesop} failure beyond proof length, providing an operational link between the geometric signature and prover performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。