← 研踪 PaperTrailarXiv:2611.26507 · v1
Hereditary permutations for simple types revisited: A baby case for University Algebra
重温简单类型的遗传置换:大学代数的一个婴儿案例
首次提交 2026-11-20 01:55
版本更新 2026-11-20 01:55
雷达观测 2026-11-20 12:52
摘要
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 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-20 01:55 · 最新观测版本
Hereditary permutations for simple types revisited: A baby case for University Algebra
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 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.
查看此版本解读 →查看此版本原文 ↗