七树合一定理 [seven-trees-in-one]
- September 24, 2024
- kokic
- nLab
七树合一定理 [seven-trees-in-one]
- September 24, 2024
- kokic
- nLab
Definition 1. 二叉树类型 [binary-tree]
- September 24, 2024
- kokic
Definition 1. 二叉树类型 [binary-tree]
- September 24, 2024
- kokic
二叉树意味树的每个结点最多两个子树. 其类型由两个构造器归纳给出
inductive Tree α | leaf : Tree α | node : α → Tree α → Tree α → Tree α
叶结点构造器 leaf
用于构造出一棵空树, 空树作为某个结点的所有子结点时, 该结点正是叶结点. 相应的, 二叉树的值存储在非叶结点中. 每个 (非空, 无标记) 二叉树类型的值要么是一个单结点 {pt}=1, 要么等价于二叉树的有序配对 B×B=B2. 即 B∼{pt}⊔B2.
换言之, 二叉树可定义为某种满足 B=1+B2 的 (代数) 结构. 回顾 6 次分圆多项式 Φ6(x) = x2−x+1 其复根 ζ6, ζ6−1 是所谓的 6 次本原单位根.
Theorem 2. Blass–Lawvere 定理 [blass-lawvere]
- September 24, 2024
- kokic
Theorem 2. Blass–Lawvere 定理 [blass-lawvere]
- September 24, 2024
- kokic
记 B 是二叉树类型, 则存在一个 “极精确的双射” B∼B7.
显然并非所有 ζ6 满足的等式都能提升到 B 之间的同构, 如 B6≆1. 自然的问题是, 哪些等式能提升到同构? 这个问题由下面的 Fiore–Leinster 定理 回答.
Theorem. Fiore–Leinster [fiore-leinster]
- September 24, 2024
- kokic
- https://arxiv.org/pdf/math/9405205
Theorem. Fiore–Leinster [fiore-leinster]
- September 24, 2024
- kokic
- https://arxiv.org/pdf/math/9405205
设 f,g1,g2∈N[x], 其中 f 有非零常数项且 degf≥2. 若 f(x)−x 整除非常值的 g1−g2 (在 Z[x] 中), 则在 N[x]/(x=f(x)) 中, g1(x)=g2(x).
特别的, 取 f(x)=1+x2, Fiore–Leinster 定理 表明, 若在 N[x]/(x=1+x2) 中成立 f(x)=g(x), 则存在 “极精确的双射” f(B)≅g(B). 在 N[x]/(x=1+x2) 中可以演绎得到 x=x7 但无法给出 1=x6. 对于前者 x7−x=(x2−x+1)(x5+x4−x2−x)=0. 再看 x4+x2+1=(x2+x+1)(x2−x+1), 这给出 B4+B2+1≆0, B4+B2+B+1=B.
这套想法亦可应用于其他树结构, 如有根平面树, 其每个结点有 0, 1 或 2 个子结点, 即 T≅1+T+T2. 由 Fiore–Leinster 定理, 存在 “极精确的双射” T≅T5.