按年被提到
19942015 · 1 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:math/9405205 · math.LO

Seven Trees in One

七棵树合一
Andreas Blass · 1994

给出二叉树集合与七元组之间一个特别初等的双射

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2015-06-25 · 最近 2024-05-20发表于 Journal of Pure and Applied Algebra
4不同的人
4活跃月份
4讨论串
24被引(OpenAlex)

沿着 Lawvere 的一个评论,论文显式给出有限二叉树集合 T 与七元组集合 T^7 之间一个特别初等的双射:对七元组应用该双射时,只需做到固定深度(四层)的情形区分。作者阐明了这类双射与满足 X=1+X^2 的单生成元自由交换半环之间的关系;主要定理是,只要在直觉主义类型论中可证明存在任何双射,就能推出存在这样“特别初等”的双射。

HN 为什么提它

评论者反复引用它作为“二叉树类型与七元组同构”的显式构造(第 3 页给出具体做法),并称其为最喜欢的结果之一。

其他难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1二叉树与递归数据类型
2双射与集合基数
3自由交换半环(free commutative semiring)
4直觉主义类型论(intuitionistic type theory)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用gjm11 · 2015-06

“you can find an explicit construction for it on page 3 of Seven Trees in One if you like.”

指出论文第 3 页有七棵树等于一棵树的显式构造
The Algebra of Algebraic data types原评论 ↗
引用svat · 2022-10

“This can be used to give an explicit bijection: see Andreas Blass's paper”

引用 Blass 的论文,说明可由此给出显式双射
Calculus with types原评论 ↗
引用enricozb · 2023-01

“Seven trees in one [0], a paper showing a bijection between binary trees and seven-tuples of binary trees.”

列出这篇论文,展示二叉树与七元组二叉树之间的双射
Taking the derivative of an algebraic data type [pdf]原评论 ↗
引用cvoss · 2024-05

“One of my favorites is the result that the binary tree type is isomorphic to septuples of binary trees”

称自己最喜欢的结果之一:二叉树类型同构于七元组二叉树
Grothendieck’s use of equality原评论 ↗