カントール集合

昨日、初めてフラクタルをプログラムで描画した。

実は、フラクタルは結構難しい。二次元の場合は正確かつ高度な実装能力が必要だ。

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

http://poj.org/problem?id=2876

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

カントール集合は、不可算集合の代表的な例らしい。

非加算集合とはその名の通り、『その要素に番号を割り振ることのできない集合』である。

なんじゃそりゃ！？って感じですね。

簡単に言うと、無限個の整数を使っても番号を割り振ることのできないくらい、濃度の濃い集合ということです。例えば、実数の集合も非加算集合です。

カントールさんは、この非加算集合の存在を数学的に示したそうです。

wikipedia（英語版）に、とても面白い内容がありました。

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

http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

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

0または、1のみから構成される無限長リストの集合を考える。

この無限長リストに番号をつけて、適当な要素列s_1、s_2、...を考える。

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

　　　...

とすると、対角成分（左上から右下にかけて）に移動しながら、通過した数字と異なる数字を選ぶ。

　　s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

すると、このs₀は、どのsiとも異なる。

ここで面白いことに、

• s₀は集合sに含まれる。（1, 0からなるリストなので）
• 同時に、s₀は集合sに含まれれない。（上記のような操作をすれば、集合に含まれないようなリストを作成できる。）

の両方が成立する。

これは矛盾なので、

この無限長リストに番号をつけて、適当な要素列s_1、s_2、...を考える。

という操作は不可能だということが分かる。

よって、集合sはs_1、s_2、s_3、s₄は数えることはできない。

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