第III章 演習問題 [1]

\[ \begin{gather} R(0)=0 \\ R(1)=\{0\} \\ R(2)=\{0,\{0\}\} \\ R(3)=\big\{\,0,\{0\},\{\{0\}\},\{0,\{0\}\}\,\big\} \end{gather} \] というところまでは何でもないし, 少しがんばれば \[ \begin{align} R(4) = \big\{\, & ~ \\ & 0, \\ & \{0\},~\{\{0\}\},~\{\{\{0\}\}\},~\{\{0,\{0\}\},\\ & \{0,\{0\}\},~\{0,\{\{0\}\}\},~\{\,0,\{0,\{0\}\}\,\},\\ & \{\{0\},\{\{0\}\}\},~\{\,\{0\},\{0,\{0,\{0\}\}\,\},~\{\,\{\{0\}\},\{0,\{0,\{0\}\}\,\}\\ & \{\,\{0\},\{\{0\}\},\{0,\{0\}\}\,\},~\{\,0,\{\{0\}\},\{0,\{0\}\}\,\},~\\ & \{\,0,\{0\},\{0,\{0\}\}\,\},~\{\,0,\{0\},\{\{0\}\}\,\} \\ & \{\,0,\{0\},\{\{0\}\},\{0,\{0\}\}\,\} \\ \big\} & \end{align} \] のように要素を列挙できる. ところが \(R(5)\) になると, 要素の個数は \(2^{|R(4)|}=2^{16}=65536\) 個にもなり, 手作業で間違えずに数えあげることは難しくなる.

そこで, コンピュータに \(R(5)\) の要素をリストアップさせたらどうかと考える. たとえば次のようなプログラムが考えられる:

#!/usr/bin/ruby

# -------------------------------------------------------------
# by 藤田 博司, 2011/06/03
# -------------------------------------------------------------
# キューネン『集合論〜独立性証明への案内』の第III章演習問題[1]
# 集合 R(5) の全要素をリストアップするプログラム
# -------------------------------------------------------------

# 同章演習問題[5]で定義された二項関係 E の モストフスキ収縮関数
def mostowski(n)
  x = n
  if (x == 0) # 空集合
    s = "0"
  else # 要素のリストを再帰的に作る
    s = "{"
    k = 0;
    while ( x >= 1 ) 
      if ( (x % 2) != 0 ) # n の k 番目のビットが立っていたら ...
        if ( s.length >= 2 ) # (ここから三行は数学的には蛇足)
          s += ", "
        end
        s = s + mostowski(k) # ... k 番目の集合を要素に追加する
      end
      k += 1
      x >>= 1
    end
    s = s + "}"
  end
end

# R(n) は 
# { mostowski(i) : i < |R(n)| } に一致し, 
# これはまた mostowski(|R(n+1)|-1) に等しい.
# しかしここで mostowski(2**65536 - 1) を計算させるのは
# (Rubyなら可能とはいえ) 得策でなかろう

(0..65535).each do |i|
  puts mostowski(i)
end
# プログラムのおわり

次のPythonプログラムは ツイッターID tooro1988 さんが送ってくださったもの:

#!/usr/bin/python

import sys

def pick(ls, n):
   if n == 0:
       return [[]]
   if len(ls) < n:
       return []
   else:
       head = ls[0]
       tail = ls[1:]
       return pick(tail, n) + prepend_all(head, pick(tail, n-1))

def prepend_all(head, lists):
   return [ [head] + ls for ls in lists ]

def power(ls):
   ans = [[]]
   for n in range(len(ls)):
       ans += pick(ls, n + 1)
   return ans

def R(n):
   if n == 0:
       return []
   else:
       return power(R(n-1))

n = int(sys.argv[1])
for a in R(n):
   print str(a).replace("[]", "0").replace("[", "{").replace("]", "}")

大阪府大の嘉田さんからは次のPrologコードを教えていただいた:

/* =============================================================
       R(n) に相当するリストを得る Prolog プログラム
       r( N, L ). で R(N) に相当するリストが L にマッチする
       write_r( N ). で R(N) に相当するリストを出力する.

       Mac OS X 10.6.7
       SWI-Prolog (Multi-threaded, 64 bits, Version 5.10.4)
       で R(5) まで動作確認しました.
       Windows XP (メモリ 1.5GB)のマシンでも,Prolog 処理系を
       SWI-Prolog (Multi-threaded, 32 bits, Version 5.10.4)
       にアップデートしたら,write_r(5). が走るようになりました.

       出力結果は括弧が {, } でなく [, ] で,空集合が [] なので,
       {, }, 0 を使った形の結果を得るには後処理が必要です.
       たとえば,
       ========
       s/\[\]/0/g
       s/\[/\{/g
       s/\]/\}/g
       ========
       という内容の sed スクリプトファイル wf.sed を用意しておいて,
       Prolog 処理系で
       tell( 'r5.txt' ), write_r( 5 ), told.
       を実行して出力結果を r5.txt に書き出してから,コマンドラインで
       sed -f wf.sed < r5.txt > r5a.txt
       を実行すれば,{, }, 0 を使った形の結果が r5a.txt に書き出されます.
   ============================================================= */

r( 0, [] ).
r( N, L )       :-
       N > 0,
       N1 is N-1,
       r( N1, Y ),
       powerset( Y, L ).

powerset( Y, Z )        :-
       findall( W, is_subset_of( W, Y ), Z ).

is_subset_of( [], _ ).
is_subset_of( [ E | Y ], X ) :-
       pick_split( X, E, R ),
       is_subset_of( Y, R ).

pick_split( [ E | X ], E, X ).
pick_split( [ _ | X ], E, Z )   :-
       pick_split( X, E, Z ).

write_r( N )    :-
       r( N, L ),
       write( L ).

それでも, \(R(5)\) の要素は65536個だったから, コンピュータを使ってなんとかなりました. これが \(R(6)\) となると, 要素の個数は \(2^{65536}\) 個. これは10進表示で19729桁の巨大な数であり, 一秒に \(10^{100}\) 個の要素を出力するスーパーコンピュータでもまだ \(10^{19000}\) 年もかかる ことになります. 現在わかっている宇宙の年齢はせいぜい \(10^{10}\) 年くらいだそうですから, \(R(6)\) の要素を書き出すことは, 物理的な制約から, 現実にはとても不可能でしょう.

プログラムを提供くださった tooro1988 さん, 嘉田さん, ありがとうございました. 他のプログラミング言語での実装や違った切り口のプログラムができたよ, という方, ぜひお知らせください.

解答者: 藤田 博司 (公開日: 2011年6月3日)
2011年6月11日更新: 大阪府立大の嘉田さんのPrologコードを掲載

この解答に不具合を発見した方はぜひご指摘ください.

演習問題一覧に戻る