Search on the blog

2011年4月6日水曜日

カントール集合

昨日、初めてフラクタルをプログラムで描画した。
実は、フラクタルは結構難しい。二次元の場合は正確かつ高度な実装能力が必要だ。

ただし、カントール集合は一次元なので簡単。

始点、終点を引数にして再帰関数で処理をすればOK。

カントール集合は、不可算集合の代表的な例らしい。
非加算集合とはその名の通り、『その要素に番号を割り振ることのできない集合』である。
なんじゃそりゃ!?って感じですね。
簡単に言うと、無限個の整数を使っても番号を割り振ることのできないくらい、濃度の濃い集合ということです。例えば、実数の集合も非加算集合です。

カントールさんは、この非加算集合の存在を数学的に示したそうです。
wikipedia(英語版)に、とても面白い内容がありました。

Cantor's diagonal argument(カントールの対角線論法)です。

要約すると、以下のような感じ。

0または、1のみから構成される無限長リストの集合を考える。
この無限長リストに番号をつけて、適当な要素列s1、s2、...を考える。

s1 = (0, 0, 0, 0, 0, 0, 0, ...)
s2 = (1, 1, 1, 1, 1, 1, 1, ...)
s3 = (0, 1, 0, 1, 0, 1, 0, ...)
s4 = (1, 0, 1, 0, 1, 0, 1, ...)
s5 = (1, 1, 0, 1, 0, 1, 1, ...)
s6 = (0, 0, 1, 1, 0, 1, 1, ...)
s7 = (1, 0, 0, 0, 1, 0, 0, ...)
   ...
とすると、対角成分(左上から右下にかけて)に移動しながら、通過した数字と異なる数字を選ぶ。
  s0 = (1, 0, 1, 1, 1, 0, 1, ...)

すると、このs0は、どのsiとも異なる。
ここで面白いことに、
  • s0は集合sに含まれる。(1, 0からなるリストなので)
  • 同時に、s0は集合sに含まれれない。(上記のような操作をすれば、集合に含まれないようなリストを作成できる。)
の両方が成立する。
これは矛盾なので、
この無限長リストに番号をつけて、適当な要素列s1、s2、...を考える。
という操作は不可能だということが分かる。

よって、集合ss1s2s3s4は数えることはできない。

どういう頭の構造をしてたら、こんなこと考えつくんでしょうね・・。

0 件のコメント:

コメントを投稿