跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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→B→C≅B→A→CA \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.

AI 论文解读

基于摘要 · 非全文审阅

在β-正规η-长类型项内重新证明简单类型λ演算的可定义同构恰为遗传置换,并证明这些同构的群胚由一组显式方程呈现,全部结果在Agda中形式化。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 A→B→C≅B→A→CA \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.

查看此版本解读 →查看此版本原文 ↗