アルゴリズムと数学 - ウルトラへの道

今日仕事で触れた話で、久しぶりに「学問的に面白い」と感じたエピソードがあったのでメモ。

可変長のレコードをソートしたいのならば、インデックスソートが妥当*1。
インデックスソートの妥当性を数学的に表現すると非常に面白いです。具体的には

「全順序集合｛ $X, \leq$ ｝と集合 $Y$ 、それらの間の全単射 $Y \rightar X$ が存在する場合、 $f$ が $Y$ に誘導する自然な全順序｛ $Y,f^{-1}(\leq)$ ｝を考える。このとき、あるソート $g :$ ｛ ${1,2,...,}$ ＃ $Y$ ｝ $\rightar Y$ が存在し、 $\forall~x \leq y \in$ ｛ ${1,2,...,}$ ＃ $Y$ ｝に対し $x f^{-1}(\leq) y$ が成立すれば、合成写像 $g \compos f$ が $X$ のソートを与えることを示せ。」

という命題の証明が

（証明）
明らか。（証明終わり）

の一言で終わってしまうところが。

…書いていて自分で思いましたが、これが「面白い！」と思える人間って相当限定される気がします*2ね…（汗）。普段は「誰が読んでもとりあえず理解はできる」文章を心がけているので、たまには「誰が読んでも共感できない文章を書いてみよう」と思ったらこんなことになってしまいました（汗）。まあ、たまにはこういう日もあってもいいですかね*3。

*1:５月３０日追記：各レコードに対してＯ（１）でアクセスできることも、インデックスソートが妥当となるために必要でした。そりゃそうですね。

*2:アルゴリズムと数学、どちらか片方だけの理解では楽しめないので。

*3:まあ実は、全部理解できたとしても面白くない可能性もあるのが困ったものです。（死）