4.  部分集合,冪集合,補集合

ある集合の要素すべてが,他の集合の要素であるような集合を部分集合と言います.

(defun subset-p (s1 s2)
  (every #'(lambda (e1) (member e1 (member-of s2) :test #'equals))
         (member-of s1)))

ですから,どんな集合でも自分自身の部分集合になりますし,空集合はどんな集合の部分集合にもなります.このとき,空リストについての every の定義がうまく働いていますね.

zf(4): (subset-p +empty+ +empty+)
t
zf(5): (subset-p +empty+ (set-of 1 2 3))
t
zf(6): (subset-p (set-of 1 2 3) (set-of 1 2 3))
t
zf(7): (subset-p (set-of 1 2) (set-of 1 2 3))
t
zf(8): (every #'(lambda (x) nil) '())
t
zf(9): (subset-p (set-of 1 2) +empty+)
nil

今まで集合の印刷ではCLOSの既定の印刷が用いられてきて,直接その中身を見ることはできませんでした.
CLOSのオブジェクトは構造体と同様に,その印刷をカスタマイズすることができます.ここで本当に集合のように見えるような印刷メソッドを定義してみましょう.この format 文での反復の書き方は,「実践Common Lisp」に説明があります.

(defmethod print-object ((object set) stream)
  (format stream "{~{~S~^,~}}" (member-of object)))

すると,システムは集合の印刷にこのメソッドを使うようになります.

zf(2): +empty+
{}
zf(3): (set-of 1)
{1}
zf(4): (set-of 1 2 3)
{1,2,3}

さて,いよいよ冪集合です.冪集合の公理では,任意の集合についてその集合の部分集合全体からなる集合の存在を主張します.冪集合を作るには,まず,任意の集合からそのすべての部分集合を作り出さなければなりません.ここでLisp の再帰をうまく使います.

(defun power-set (s)
  (cond ((empty-p s) (set-of s))
        ((singleton-p s) (set-of s +empty+))
        (t (set (cons s
                      (member-of
                       (apply #'union-of
                              (mapcar #'(lambda (e)
                                          (power-set (set (remove e (member-of s)))))
                                (member-of s)))))))))

空集合の冪集合は空集合のシングルトン(訂正)です.シングルトンの冪集合は自分自身と空集合の合併です.それ以上の大きな集合については,その要素からひとつ何かの要素を取り去ったものの冪集合の合併と自分自身の合併です.

zf(24): (power-set +empty+)
{{}}
zf(25): (power-set (set-of 1))
{{1},{}}
zf(26): (power-set (set-of 1 2))
{{1,2},{2},{1},{}}
zf(27): (power-set (set-of 1 2 3))
{{1,2,3},{3},{1,3},{2,3},{1,2},{2},{1},{}}

ある集合 a に対するある集合 b の補集合 a - b はCommon Lisp の set-difference で簡単に定義できます.

(defun complement-of (set for)
  (set (set-difference (member-of for) (member-of set) :test #'equals)))
zf(44): (complement-of (set-of 1 2) (set-of 1 2 3 4))
{4,3}

集合演算と論理演算の比較でいうと,合併集合が論理の and に相当し,共通集合が論理の or に相当します.そして補集合が実は論理の not に相当するのですが,これからわかるように not というのは,本当は何に対する補集合なのかがなければならないのです.もしそれが与えられないとすると,それは全体に対してということになるのですが,それが得てして問題なのです.以前に not を入れると途端に難しくなるって書いたことがありますが,なんとなく分かっていただけたでしょうか.