第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 ).