重温简单类型的遗传置换:大学代数的一个婴儿案例
Hereditary permutations for simple types revisited: A baby case for University Algebra
Thorsten Altenkirch
AI 速读 基于摘要
在β-正规η-长类型项内重新证明简单类型λ演算的可定义同构恰为遗传置换,并证明这些同构的群胚由一组显式方程呈现,全部结果在Agda中形式化。
cs.LO · cs.PL
查看原文摘要
It is a classical result that the definable isomorphisms of the simply typed lambda-calculus with function types are exactly the hereditary permutations, and that they are generated by $A \to B \to C \cong B \to A \to C$ and congruence. We give a new proof of this result that stays inside beta-normal eta-long typed terms and uses no completeness theorem: an induction that descends through both components of an isomorphism at once. We then go one level up and prove a coherence theorem: two derivations of an isomorphism denote the same isomorphism if and only if they are equal modulo an explicit list of equations (groupoid laws, functoriality, involution, naturality and the braid equation), so these equations present the groupoid of isomorphisms, a hereditary version of the Coxeter presentation of the symmetric groups. All results are formalised in Agda, on intrinsically typed syntax with hereditary substitution, without postulates. The work is a case study for the syntactic completeness conjecture of University Algebra, a proposed solution of Tarski's high school algebra problem using dependent types, whose semantic counterpart is open. We explain the motivation and which parts of the method we expect to carry over.