セカイノカタチ

世界のカタチを探求するブログ。関数型言語に興味があり、HaskellやScalaを勉強中。最近はカメラの話題も多め

マーブルワーズ

デデキント切断は可能なのか?

デデキント切断というのは、こんな感じの手続きです。

デデキント切断 - Wikipedia

全順序集合Kを、条件「a<b」に従って、集合AとBに分断できる。という理屈です。

これを0から1までの実数を点pで切断したいとします。

点pは、0<p<1の無理数を適当に選んだものとします。(0.123456578910111213...チャンパーノウン定数とか)

切断には、関数f(x,y)を使用します。この関数は、何らかの計算の結果、与えられた2つの数字の間の実数を返します。 与えられた数が同じなら、同じ答えを返しますが、引数と結果の関係は予想できないものとします。

def g(x,y) = val n = f(x,y); if n < p then g(n, y) else g(x, n)
g(0,1)

この擬似コードはは停止しません。終了条件がないからです。っていうのは当然なのですが。(^^;;

注目して欲しいのは、"n < p"の部分です、xとyは、再帰する度にpに向かって追い込まれていくのがわかると思います。

そして、そのうち比較に非常に大きな時間がかかるようになり、ついには比較できなくなるでしょう。

実際のコンピュータでは資源が有限なので計算が打ち切られると思いますが、実数は無限の長さを持つため隣り合う実数同士の比較はできません。

さて、この時の点pとnは、どちらが大きのでしょうか?

ここでもう一度「全順序集合」の定義に戻ってみましょう。

順序集合 - Wikipedia

「順序集合で特に「比較不能」のケースを許容しないものを全順序集合(totally ordered set)という」とありますので、実数のうち無理数は、全順序集合とは呼べないですね。

ということは、実数は「デデキント切断できない(こともある)」という事になるのではないでしょうか。