data Natural = Zero - 数学＠ふたば保管庫

数学＠ふたば保管庫 [戻る]

2763 B


data Natural = Zero | Succ Natural ※haskell表記
と再帰的に定義される自然数に和と積を定義して
整数→有理数→実数と拡大させていったのだから
data BinaryTree = Leaf | Node BinaryTree BinaryTree
と定義された二分木に対しても同じことは可能なのだろうか
上手くすれば離散的にしか扱えなかった木構造を連続的に扱えないだろうか

2分木は、離散連続と無関係では？

とりあえず以下のように(*)を定義すればモノイドにはなる
t * Empty= t
t * (BinaryTree u v)= BinaryTree (t * u) (t * v)
自然数から二分木への準同型写像φも定義できるので自然数の拡張とも考えられる
φ Zero = Empty
φ (Succ n) = (BinaryTree Empty Empty) * (φ n)
でも可換則を満たしてくれない
二分木に対して結合則、単位元、可換則を満たすような二項演算は無いものだろうか

完全二分木でm+1個の葉を持つものを数え上げると、

(2m!)/{(m+1)!m!}

だから、m→ω（可算無限）としてもその集合全体の濃度は可算だね。

これを非可算にしようとすると、二分木を括弧で表現した時に例えば、

[[…[…]…]]　（…は可算無限個の正当な括弧の付け方を満たす）

のような、その括弧表記の「子」を取る操作が有限では終わらないものを無数に認める必要がある。
その類全体の要素には親と子が同じであるようなものも無数に現れるから、ラッセルのパラドクスに使われた集合（真の類）の類似物も現れることになるね。