順序数の説明を空集合からの冪集合の生成で説明した.すなわち,空集合を=0 と表記したとき,=1 は (power-set =0),=2 は (power-set =1),=3 は (power-set =2),等々である.

zf(2): (setq =0 +empty+)
{}
zf(3): (setq =1 (power-set =0))
{{}}
zf(4): (setq =2 (power-set =1))
{{{}},{}}
zf(5): (setq =3 (power-set =2))
{{{{}},{}},{{}},{{{}}},{}}

ところが,=4 までは楽に計算できるが,=5 になるといつまでたっても答えは返ってこない.ちなみに,=0 の要素数は0,=1 は1,=2 は2 ,=3 は4,=4 は16 となる.一般に冪集合の要素数は元の集合の要素数を n とすると 2n 個になる.すなわち =5 の要素数はいきなり 65536 個になってしまうのである.

今,簡単のために集合を要素とするのではなく,(power-set (set-of 0 1 2 3)) のように数字を要素とする冪集合について,計算時間を調べてみると,私の持っている最高級のPC,intel core i5,2.67GHz×2,4GB,Windows7 で次のようになる.

powerset-time

横軸が要素数(カージナリティ),縦軸が対数目盛でms単位である.要素数11のときに,およそ13分であるが,これが要素数16になると,対数目盛を単純に外挿して,なんと2年半の計算時間になる.これには正直びっくりした.なるほどいつまでたっても計算が終わらないわけだ.

順序数を定義するのに,冪集合を用いるのではなく,successor を用いる方法がある.すなわち,=0 を空集合としたとき,=1 は (union-of =0 (set-of =0)),=2 は (union-of =1 (set-of =1)),のようにする方法だ,これだと要素数は1ステップで一つしか増えない.しかも,冪集合において成立した重要な性質,低位の集合は高位の集合の部分集合でもあるし要素でもあるという性質が成立している.

zf(25): (setq =1 (union-of =0 (set-of =0)))
{{}}
zf(26): (setq =2 (union-of =1 (set-of =1)))
{{},{{}}}
zf(27): (setq =3 (union-of =2 (set-of =2)))
{{{}},{},{{},{{}}}}
zf(28): (setq =4 (union-of =3 (set-of =3)))
{{{},{{}}},{},{{}},{{{}},{},{{},{{}}}}}
zf(29): (setq =5 (union-of =4 (set-of =4)))
{{{{}},{},{{},{{}}}},{{}},{},{{},{{}}},{{{},{{}}},{},{{}},{{{}},{},{{},{{}}}}}}
zf(30): (setq =6 (union-of =5 (set-of =5)))
{{{{},{{}}},{},{{}},{{{}},{},{{},{{}}}}},{{},{{}}},{},{{}},{{{}},{},{{},{{}}}},{{{{}},{},{{},{{}}}},{{}},{},{{},{{}}},{{{},{{}}},{},{{}},{{{}},{},{{},{{}}}}}}}
zf(31): (in =5 =6)
t
zf(32): (subset-p =5 =6)
t
zf(33): (in =2 =6)
t
zf(34): (subset-p =2 =6)
t

というわけで,以後ここではブルバキ流に,順序数の導入をsuccessor を用いて行うことにする.(まだまだ続く)