2008-11-15 [長年日記]
λ. “Seven trees in one” by Andreas Blass
Following a remark of Lawvere, we explicitly exhibit a particularly elementary bijection between the set T of finite binary trees and the set T7 of seven-tuples of such trees. “Particularly elementary” means that the application of the bijection to a seven-tuple of trees involves case distinctions only down to a fixed depth (namely four) in the given seven-tuple. We clarify how this and similar bijections are related to the free commutative semiring on one generator X subject to X = 1 + X2. Finally, our main theorem is that the existence of particularly elementary bijections can be deduced from the provable existence, in intuitionistic type theory, of any bijections at all.
Seven Trees やっと解けた - ヒビルテ(2008-10-28) のツッコミと、Seven Trees：最後のヒント＋もっと面白い話 - 檜山正幸のキマイラ飼育記 から。 例の Seven Trees を詳しく扱った論文で、多項式P(X)とQ(X)に関して以下が同値だという話。
- Tを二分木の集合としたときに、P(T)とQ(T)の間に very explicit な全単射が存在する (combinatorial equivalence)
- 半環 N[X]/(X=1+X2) でP(X)=Q(X) が 成り立つ (algebraic equivalence)
- P(T) と Q(T) の間の全単射の存在を構成的に証明できる
t=1+t2 の複素数解 t = (1 + i√3)/2 の性質に関しては、P(t)を多項式P(X)の“Euler characteristic”と呼んでいて、それとP(ℵ0)を{0, 有限, 無限}の3値で解釈した「次元」とをあわせたものが、jointly injective だと言っている。つまり、両方とも等しければ P(X)=Q(X) 。
例えば、P(X)=X7 と Q(X)=X の場合には、P(t)=Q(t)=t でかつ P(ℵ0)=Q(ℵ0)=ℵ0 なので、P(X)=Q(X) 。 一方で、P(X)=X6 と Q(X)=1 の場合には、P(t)=Q(t)=1 だけど、P(ℵ0)=ℵ0≠1=Q(ℵ0) なので、P(X)≠Q(X) 。
最後の構成的集合論の話は面白そうだけど難しいね。一応グロタンディークトポスとか定義は調べて分かったけど、分類トポスやらグロタンディーク位相での強制法やらの話で挫折。
[ツッコミを入れる]
